Временная сложность вложенного цикла

Question

Какова будет временная сложность этого следующего блока функции void кода (int n).

Моя попытка состояла в том, чтобы внешний цикл работал n / 2 раза, а внутренний два - 2 ^ q раза.Затем я уравнял 2 ^ q с n и получил q как 1/2 (log n) с базой 2. Умножая временные сложности, я получаю свое значение как O (nlog (n)), в то время как ответ O (nlog ^ 2 (n).)).

void function(int n) { 
    int count = 0; 
    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2) 
                count++; 
} 

Answer 1

Время применять золотое правило понимания гнезд цикла:

Если есть сомнения, работайте наизнанку!

Давайте начнем с оригинального гнезда цикла:

    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2) 
                count++; 

Этот внутренний цикл будет выполняться Θ (log n) раз, поскольку после m итераций цикла мы видим, что k = 2 ^m , и останавливаемся, когда k ≥ n = 2 * 1012.* LG N .Итак, давайте заменим этот внутренний цикл на более простое выражение:

    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            do Theta(log n) work;

Теперь посмотрим на самый внутренний оставшийся цикл.С тем же рассуждением, что и раньше, мы видим, что этот цикл также выполняется Θ (log n).Поскольку мы выполняем Θ (log n) итераций, каждая из которых выполняет Θ (log n), мы видим, что этот цикл можно заменить на этот более простой:

    for (int i=n/2; i<=n; i++)
        do Theta(log^2 n) work;

И здесь этот внешний цикл выполняется Θ (n), поэтому общее время выполнения составляет Θ (n log ² n).

Я думаю, что, основываясь на том, что вы сказали в своем вопросе, вы имели правильные представления, но просто забылиумножьте на две копии лог-термина, по одному для каждого из двух внутренних циклов.

Answer 2

В вашем коде есть 3 вложенных циклов.

1. Первый цикл выполняется n/2 раз, что почти эквивалентно n при расчете сложности.
2. Второй цикл выполняется logn раз.
3. Третий цикл запускается logn раз.

Итак, наконец, сложность времени будет O( n * logn * logn ) == O(nlog^2n).
Теперь можно задаться вопросом, как регистрируется сложность во время выполнения двух внутренних циклов.Это можно обобщить следующим образом:
Так как мы умножаем на 2 в каждой итерации, нам нужно значение q такое, что:
n = 2 ^ q.

Принимая базу журнала 2 на

log2 n = log2 (2^q)
log2 n = q log2(2)
log2 n = q * 1 [ since, log2(2) is 1 ]

Итак, q равно logn.
Итак, общая сложность времени: O(n*log^2n).

Answer 3

Первый цикл занимает: n / 2

Второй цикл: log (n)

Третий цикл: log (n)

Обратите внимание, потому что шаг внутреннегочисло циклов умножается на два, их соответствующие счетчики растут экспоненциально, достигая n в log(n), с точки зрения сложности времени.

Затем также обратите внимание, что константы типа 1/2 можно безопасно игнорировать в этомрегистр, который приводит к O(n * log(n) *log(n)), таким образом:

O (nlog ² n)