Вложено для сложности цикла

Question

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

for(i = 1; i <= n; i *= 2)
    for(j = 0; j <= i; j++)
          some_constant_statement 

Первый цикл занимает время входа в систему, но как насчет второго цикла? Я в замешательстве, пожалуйста, помогите мне понять это.

Answer 1

Внешний цикл равен O(log n), так как он выполняется несколько раз пропорционально log (некоторое число n).

Внутренний цикл (взятый только сам по себе) равен O(n), поскольку он выполняется несколько раз пропорционально некоторому числу n. Это верно для каждой итерации внешнего цикла, потому что сложность времени остается неизменной, то есть она всегда пропорциональна значению n на момент ее вызова.

Весь кусок кода O(n log(n)). Обычно используется для обозначения «порядка некоторого числа n, умноженного на log (n)».

Обозначение Big O предназначено для классификации, а не для количественной оценки. Это дает некоторое представление о том, как обсуждаемая функция будет работать с наборами данных различных размеров. Две функции, описанные как имеющие O(n log(n)) производительность, могут существенно различаться для заданных значений n.

Answer 2

Сложность по времени будет O (nlog (n)), но это асимптотическая сложность. Если вы хотите, чтобы фактический счетчик выполнялся, он был бы немного меньше, чем верхняя граница. Что вы можете сделать, чтобы визуализировать это, так это отследить все для небольших значений N.

В этом случае, скажем, если N = 8

i = 1: j = 0  => 2 times
       j = 1
i = 2: j = 0  => 3 times
       j = 1
       j = 2
i = 4: j = 0  => 5 times
       j = 1
       j = 2
       j = 3
       j = 4
i = 8: j = [0,8] => 9 times

и т. Д. Для больших значений N ...

Таким образом, оно не увеличивается линейно, а в некотором виде экспоненциально, и при построении графика для больших значений и поиске функции верхней границы вы докажете, что у нее есть верхняя граница O (nlog (n)), если вы математически склонен доказать это.