Пример расчета временной сложности циклов с помощью цикла in

Question

привет, я работал с анализом итеративного решения, вот одна проблема, которую я не могу рассчитать наихудшее время выполнения

void function(int n)
{
    int count = 0;
    for (int i=0; i<n; i++)
    {
        for (int j=i; j< i*i; j++)
        {
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }
        }
    }
}

Вот ссылка на вышеуказанную проблему, https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/

Пожалуйста, смотрите проблему № 7.

Какова временная сложность вышеуказанной функции? В задаче они говорят, что это O (n ^ 5), но у меня есть некоторые сомнения по этому поводу, может кто-нибудь предоставить мне какое-то математическое доказательство

Answer 1

Прежде всего, ваша программа потерпит крах, потому что if(j % i == 0), i и j равны 0
немного изменив код

void function(int n)
{
    int count = 0;
    for (int i=1; i<n; i++) // runs O(n) times
        for (int j=i; j< i*i; j++)  
            if (j%i == 0) // runs O(i) times
            {
                for (int k=0; k<j; k++) // runs j times, whenever j is factor of i
                    //that is when j = i, j = 2i ... j = i* i
                    printf("*");
            }
}

взять пример, когда i = 5

Это означает, что общая сложность составляет

for (int j=5; j< 25; j++)  
     if (j%i == 0) // runs O(i) times
     {
      // runs j times when j = 5, 10, 15, 20
            for (int k=0; k<j; k++) {
                printf("*"); // runs j times when j =  5(1 + 2 + 3+ 4)
               // runs  j times which is i*i*(i*(i-1)/2) times
               // runs i^4 times
            }
     }

это означает, что общая сложность равна O (n ^ 4)

Answer 2

Я думаю, что это может быть O (N ^ 5). Первый цикл for имеет диапазон до n, второй имеет n ^ 2 (учитывая член с наибольшим коэффициентом), а последний совпадает со вторым. Таким образом, их умножение n ^ 5.