Временная сложность вложенного цикла для (i = n; i> 0; i / = 2) VS для (i = n; i> 0; i / = 2) для (j = 0; j <i; j ++)

Question

Я не могу выяснить сложность времени Алго А и Алго Б. Пожалуйста, помогите мне, ребята !!!

Алго A:

for(int i=n; i>=1; i/=2)
    some statement  

Если я не ошибаюсь,

i = n;
i = n / 2 to the power of 1;
i = n / 2 to the power of 2;
i = n / 2 to the power of 3;
i = n / 2 to the power of 4;
.................
.................
i = n / 2 to the power k;

Algo A terminate when,

n / 2 to the power of k < 1
Therefore k = log n, Algo A take logn time;

Алго B:

for(i=n; i>=1; i/=2)
   for(j=0; j<i; j++)
      some statement

Ребята, я не могу выяснить сложность времени Алго Б, так как рассчитать это и исправить меня, если я ошибаюсь с Алго А

Answer 1

Краткий ответ : если " какое-то утверждение " выполняется в постоянное время, то алгоритм B выполняется в O (n) .

Давайте сначала проанализируем внутренний цикл:

for(j=0; j<i; j++)
    some statement

Поскольку j повторяется от 0 (включительно) до i (исключительно), это означает, что он будет таким образом выполнятьi операций.

Теперь мы можем проанализировать внешнюю часть:

for(i=n; i>=1; i/=2)
    // i operations

Здесь i, таким образом, начинается с n, каждый раз делится на 2, и каждыйитерация, мы выполняем i задач.

Таким образом, это означает, что общее количество задач составляет:

 n + n/2 + n/4 + n/8 + ... + 1

Выше приведена известная последовательность:

 m
---
\          -k           -m
/     n * 2     = (2 - 2  ) n
---
k=0

Здесь k, таким образом, варьируется от 0 до log ₂ n , и, таким образом, общее количество инструкций составляет (2-2 ^{).log ₂ n} ) × n или (2 - 1 / n) × n и, следовательно, 2 × n - 1 .Мы можем упростить это до O (n) .