расчет Сложность

Question

Какова сложность:

int f4(int n) 
{ 
    int i, j, k=1, count = 0; 

    for(i = 0; i < n; i++) 
    { 
     k *= 3; 

     for(j = k; j; j /= 2) 
     count++; 
    } 

    return count; 
} 

Я знаю, что это O (N^2), но как рассчитать это? и почему это не n * log n?

Answer 1

Существует n внешних петель. В любой момент, k = 3i. Есть log2(k) внутренние петли (потому что мы вдвое j на каждой итерации.)

log2(3i) = log3 (3i)/log3(2) = i/(constant)

Таким образом, сложность внутреннего цикла является i. Другими словами, эта программа имеет ту же сложность (но не точно такой же число итераций) как

int f4changed(int n) 
{ 
    int i, j, count = 0; 

    for(i = 0; i < n; i++) 
    { 
     for(j = 0; j < i; j++) 
     { 
      count++; 
     } 
    } 
} 

Это O(n2)as you've already seen.

Answer 2

= 1 приводит к 3-х итераций (внутреннего контура) (3, 1, 0)
я = 2 8 (5, то 3)
я = 3 13 (7 + 5 + 3)

То, что у вас есть, относится к arithmetic series, то есть O (n).

Для полноты (и чтобы объяснить, почему точное число итераций не имеет значения), обратитесь к Plain english explanation of Big O (это больше для других читателей, чем для вас, для плаката, так как вы, кажется, знаете, что случилось).

Answer 3

Сложность Log (Pow (3, n)) ~ O (N). Если внутренний цикл был k * = 2, то число итераций также было бы n.
Для вычисления O (~) используется старший член мощности, а остальные - пренебречь. Log (Pow (3, n)) может быть ограничено как:
Log (Pow (2, n)) < = Log (Pow (3, n)) < = Log (Pow (4, n))
Теперь Log (Pow (4, n)) = 2 * Log (Pow (2, n)).

Самый высокий член мощности здесь равен n (as 2 является константой).