выполнения сложность функции

Question

Я должен найти временную сложность следующей программы:

function(int n) 
{ 
    for(int i=0;i<n;i++)     //O(n) times 
     for(int j=i;j<i*i;j++)    //O(n^2) times 
      if(j%i==0) 
      { //O(n) times 
       for(int k=0;k<j;k++)  //O(n^2) times 
        printf("8"); 
      } 
} 

Я проанализировал эту функцию следующим образом:

i : O(n) : 1  2  3   4    5 
j :  : 1  2..3  3..8  4..15   5..24   (values taken by j) 
    O(n^2): 1  2  6   12   20    (Number of times executed) 
j%i==0 : 1  2  3,6  4,8,12  5,10,15,20  (Values for which the condition is true) 
    O(n) : 1  1  2   3    4 
k   : 1  2  3,6  4,8,12  5,10,15,20  (Number of times printf is executed) 
    Total : 1  2  9   24   50    (Total) 

Однако я не могу привести какие-либо выводы так как я не нашел никакой корреляции между $ i $, которая по существу равна O (n) и Total k (последняя строка). На самом деле я не понимаю, нужно ли нам смотреть на временную сложность с точки зрения количества раз printf, так как это будет пренебрегать выполнением цикла j-for O (n^2). Ответ дал O (n^5), который, я полагаю, ошибочен, но тогда что правильно? Чтобы быть более конкретным о моем замешательстве, я не могу понять, как это условие if(j%i==0) влияет на общую сложность выполнения функции.

Answer 1

Ответ, безусловно, не O (n^5). Это можно увидеть очень легко. Предположим, что ваш второй внутренний цикл всегда работает n^2 раз, и ваш самый внутренний цикл всегда работает n раз, даже тогда общая временная сложность будет O (n^4).

Теперь посмотрим, что такое фактическая сложность времени.

. Самая внешняя петля всегда работает O (n) раз.

.Теперь давайте посмотрим, сколько раз второй внутренний цикл выполняется для одной итерации внешнего цикла:

Цикл будет выполняться

0 время i = 0

0 время i = 1

2 раз за i = 2 ....

i*i - i раз для j = i.

i*i - i является O(i^2)

. Приступая к самому внутреннему контуру, он работает только тогда, когда j делится на i и j варьируется от i to i*i-1.

Это означает, что j проходит через i*1, i*2 , i*3 ..... до последнего кратного i менее i*i. Очевидно, что O (i). Следовательно, для одной итерации второй внутренней петли внутренней петли внутреннего цикла O (i) раз это означает, что полные итерации двух внутренних петель составляют O (i^3).

Подведение итогов O(i^3) для i = 0 до n-1 определенно даст термин, который равен O (n^4).Таким образом, правильная временная сложность O (n^4).