две петли, но тета (n)?

Question

i = n 
while (i >= 1) 
{ 
    for j = 1 to i 
    { 
    Function() <- (O(1)) 
    } 
i = i/2 
} 

Ответ: Theta (n), но я не понимаю, почему это Theta (n).

Из моего понимания внутренний цикл выполнит n + n/2 + n/4 + ... + 1, так что сумма будет равна O (n), а внешний цикл будет выполнен по времени входа в систему, поэтому ответ должно быть nlogn. Но почему это Тета (n) вместо Тета (nlogn)?

Answer 1

Ваши расчеты частично верны. Вы просто пропускаете небольшую деталь, в которой вы уже вычислили сложность внешнего цикла. В вашем случае вы решили рассчитать сложность времени, просто вычислив время, когда каждая итерация во внешнем цикле принимает. И это:

for i=n : O(n) 

for i=n/2: O(n/2) 

. 
. 
. 

for i=1: O(1) 

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

Умножение, на которое вы ссылались, является методом, используемым, когда вы знаете, сколько раз выполняется внешний цикл и сколько раз выполняется внутренний цикл, и вы умножаете их, чтобы получить общую временную сложность.Вы могли бы использовать альтернативу, добавив количество раз, когда внутренний цикл запускается до себя n раз, тогда как n - это количество циклов, выполняемых внешним циклом (простая математика: k * n = k + k + ... + k n раз).

Итак, в вашем случае вы просто используете второй метод, так как n + n/2 + n/4 + ... + 1 - это не количество циклов, в течение которых выполняется внутренний цикл, это сумма сколько раз он запускается на каждой итерации внешнего цикла.

Answer 2

Из моего понимания, внутренний цикл будет выполняться п + п/2 + п/4 + ... + 1, так что общая будет O (п)

Это все, что вам нужно. Вы уже учли эффект умножения, который внешний цикл имеет на количество циклов, выполняемых во внутреннем цикле. Тот факт, что сама внешняя петля равна O(n), может быть добавлена ​​ к общей сложности внутреннего цикла. Сумма не n * log n, это n + log n, что составляет O(n).

Answer 3

Вы правы относительно полного внутреннего цикла, выполняющего n + n/2 + n/4 + ... + 1, который является O (n). Вам не нужно умножать время выполнения внутреннего цикла на O (log (n)), поскольку, поскольку внешний цикл имеет время выполнения O (log (n)), время выполнения внутреннего цикла также уменьшается на log (n), поскольку вы разделить на 2 I, таким образом, среда выполнения является просто только о (п)

Answer 4

сумма n + n/2 + n/4 ... + 1 всегда меньше или равно, чем 2*n, потому что геометрическая серия для q = 0.5 сходится к этому.

Следовательно, функция никогда не будет называться более 2n раз, поэтому сложность Θ(n).

Answer 5

Как вы правильно отметили, внутренний цикл будет выполнен n + n/2 + n/4 + ... + 1 ≈ 2*n раз.

Посмотрим, сколько раз будет выполняться каждая строка кода.

i = n     // Executed 1 time 
while (i >= 1)   // Executed approximately log(n) times 
{ 
    for j = 1 to i  // Executed approximately 2*n times 
    { 
     Function()  // Executed approximately 2*n times 
    } 
    i = i/2   // Executed approximately log(n) times 
} 

Таким образом, общее время сложность алгоритма:

Θ(1) + Θ(log(n)) + Θ(n) + Θ(n) + Θ(log(n)) 

что эквивалентно Θ(n).