Для петель время сложность

Question

Для данного кода, какова сложность времени в нотации Big-O?

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j = j + i)
             some_constant_statement

Если я не ошибаюсь

First loop take  n times
Second loop n.long(n) time
For Second loop :

n + n/2 + n/3 + n/4 +...................n/n times
n(1 + 1/2 + 1/3 + ..............1/n) times means
n(long(n)) time
So, time complexity of entire piece of code is n.n.long(n)

Пожалуйста, поправьте меня, ребята, если я ошибаюсь.

Answer 1

Короткий ответ : сложность времени составляет O (n log n) .

Внутренний цикл каждый раз принимает n шагов.Действительно:

for(int j = 1; j <= n; j = j + i)
         some_constant_statement

Здесь j всегда повторяется от 1 (включительно) до n (включительно), поэтому будет выполняться n/i константных операторов.

Итогоколичество операций, таким образом:

    n
   ---
   \     1
n  /    ---
   ---   i
   i=1

Сумма составляет гармонических рядов [wiki] .Мы можем приблизить это с помощью приближения Стирлинга [wiki] .Таким образом, мы знаем, что:

     n                  n
    ---                ---
    \     1            \    1
    /    ---  ≤ ln n ≤ /   ---
    ---  i+1           ---  i
    i=1                i=1

Это означает, что мы можем утверждать, что общее количество операций имеет временную сложность O (n × ln n) .Поскольку log _a (b) = log a / log b , мы можем сформулировать это как O (n log n)