big-o - 计算一段代码的大 O 符号复杂度

Question

您能否解释一下如何计算以下部分的 Big O 复杂度：

i := n;
while i > 1 do
  begin
    for j:= i div 2 + 1 to i do
      begin
        k := 2;
        while n >= k do
          k := k * k
      end;
    i := i div 2
  end;

（这是 Pascal，但语言在这里并不重要。）正确答案是n*log(log(n))，但我不知道如何到达那里。

Answer 1

从内部循环开始：

    k := 2;
    while n >= k do
      k := k * k

这会将值 2, 2 ² , 2 ⁴ , 2 ⁸ , .. 分配给k直到达到n. 这是 O(log(log(n))，因为如果我们调用迭代次数 m，它会迭代直到

2 2 m > n → log(2 2 m ) > log(n) → log(log(2 2 m )) > log(log(n)) →

→ m > log(log(n)) → m = log(log(n)) + 1

然后

for j:= i div 2 + 1 to i do
  begin
    //O(log(log(n))
  end;

这有 i / 2 次迭代，所以它是 O( (i / 2) log(log(n)))

i := n;
while i > 1 do
  begin
    // (i / 2) log(log(n))
    i := i div 2
  end;

这有 O((i / 2) log(log(n))) 的 O(log(n)) 次迭代，总和为

  O( (n/2) log(log(n)) + (n/4) log(log(n)) + (n/8) log(log(n)) + (n/16) log(log( n)) + ... ) =
= O( (1/2 + 1/4 + 1/8 + 1/16 + ...) n log(log(n)) ) =
= O( 0.1111111…<sub>2 n log(log(n)) ) =
= O(n log(log(n)))

（0.11111…<sub>2 = 1，就像 0.999…<sub>10 = 1，但无论如何在 O() 中都没有关系）