Почему этот алгоритм работает в O (n log n)?

Question

Предполагается, что «мы рассмотрим следующий алгоритм, который работает с массивом A [1.. N] целых чисел».

for i in [1 . . n] do
A[i] ← 0
for i in [1 . . n] do
    j ← i
    while j ≤ n do
        A[j] ← A[j] + 1
        j ← j + i

Присвоение просит нас продемонстрировать, что этот алгоритм работает вO (n log n).

Первый цикл довольно явно собирается добавить n во время выполнения, которое просто будет отброшено.

Вторые вложенные циклы будут выполняться быстрее, чем чистый алгоритм O (n ^ 2), поскольку цикл while не всегда выполняется n раз.Когда i = 1, он идет n раз, i = 2 он будет работать n-1 раз, вплоть до i = n, где он будет выполняться один раз.

Но, используя тот же метод, что и суммирование по Гауссуцелые числа от 1 до 100, мы видим, что цикл while будет работать в среднем (n + 1) / 2 раза.Умножьте на n для цикла for, и мы получим (n ^ 2 + n) / 2, которое можно упростить до O (n ^ 2), а не O (n log n)

Какэтот результат во время выполнения O (n log n)?

Answer 1

Учитывая следующее:

for i in [1 . . n] do
    j ← i
    while j ≤ n do
        A[j] ← A[j] + 1
        j ← j + i

Каждый раз, j увеличивается с +i, а не +1.Таким образом, сначала while loop пока повторяется n раз, затем n/2, затем n/3 ... до n/n.

Игнорируя округление целых чисел, мы можем записать это вследующий формат: n(1 + 1/2 + 1/3 + ... + 1/n).

Похоже, мы имеем дело с гармонической серией с дополнительным умножением на n.Еще некоторые подробности здесь и здесь .Это будет O(n log n).