Большой O: Это цикл FOR O (n log (n)) или O (log (n) ^ 2)? - PullRequest
Новая
       26

Большой O: Это цикл FOR O (n log (n)) или O (log (n) ^ 2)?

0 голосов
/ 28 мая 2019

У меня есть общая функция 

for i from 1 to n; i = 2i; {
    for j from 1 to i; {
        (constant time stuff)
    }
}

Для этой функции первая строка for i from 1 to n; i = 2i;, которую я знаю, это O (log (n)). Строка (constant time stuff) не имеет значения, так кого это волнует, так как это O (1).

Но средняя линия for j from 1 to i; - вот где у меня проблемы.

Я предполагаю, что Big O этой строки совпадает с первой, поскольку она следует тому же шаблону, что и первая, где i удваивается после каждой итерации, что делает его O (log (n)) , но это также может быть O (n)?

Кроме того, если это действительно O (log (n)) * O (log (n)), это просто O (log (n) ^ 2) правильно?

Извините, я только начал эту игру Big O, и, к сожалению, до сих пор мне приходилось полагаться на Интернет, так как мой учитель не очень хорош: (

Ответы [ 2 ]

1 голос
/ 28 мая 2019

Является ли это циклом FOR O (n log (n)) или O (log (n) ^ 2)?

Ни то, ни другое.

Итерация внешнего циклаlog n раз.Если бы внутренний цикл каждый раз имел одинаковое количество итераций, мы могли бы просто умножить количество итераций внешнего цикла на количество операций внутреннего цикла.Но это не так, поэтому мы не можем.

Вместо этого нам действительно нужно суммировать количество итераций внутреннего цикла: в первый раз он повторяется один раз.Второй раз, два раза.Затем четыре, затем восемь и так далее, пока, наконец, не достигнет n.Таким образом, у нас есть сумма 1 + 2 + 4 + ... + n, где мы знаем, что сумма имеет log n слагаемых, другими словами, сумма от k=0 до n из 2^k.Эта сумма равна 2n-1.2n-1 явно в O(n), так что это ваш ответ.

0 голосов
/ 28 мая 2019

Немного злоупотребляя обозначениями, у вас есть 

  sum_{i=1..log n} ( sum_{j=1..2^i} O(1) )
= sum_{i=1..log n} (2^i * O(1))
= O(2^(log n + 1))
= O(n)

Вторая, но последняя эквивалентность может быть доказана простой индукцией: 

  2^(n+1) 
= 2 * 2^n
= 2 * (sum_{i=0..n-1} (2^i) + 1)
= sum_{i=1..n} (2^i) + 2
= sum_{i=0..n} (2^i) + 1

с базовым корпусом n=1: 2^1 = 1+1 = 2^0+1.

...