algorithm - Order Of Growth 复杂的循环

Question

对于下面的代码片段，N 的增长顺序是什么？

int sum = 0;
for (int i = 1; i <= N; i = i*2)
  for (int j = 1; j <= N; j = j*2)
    for (int k = 1; k <= i; k++)
        sum++;

我认为有 lgN 项，但我一直在评估这部分:lgN(1 + 4 + 8 + 16 + ....)。序列的最后一项是什么？我需要最后一项来计算总和。

Answer 1

你的外循环有一个几何级数，所以有一个封闭的形式，你想对它求和:

1 + 2 + 4 + ... + 2^N = 2^(N+1) - 1

准确的说，你的总和是

1 + ... + 2^(floor(ld(N))

ld 表示以 2 为底的对数。

最外面的两个循环相互独立，而最里面的循环只依赖于i。最内层循环只有一次操作(自增)，也就是说最内层循环的访问次数等于求和结果。

  \sum_i=1..( floor(ld(N)) ) {
      \sum_j=1..( floor(ld(N)) ) {
          \sum_k=1..2^i { 1 }
      }
  }

    // adjust innermost summation bounds   
= \sum_i=1..( floor(ld(N)) ) {
      \sum_j=1..( floor(ld(N)) ) {
          -1 + \sum_k=0..2^i { 1 }
      }
  }

    // swap outer summations and resolve innermost summation
= \sum_j=1..( floor(ld(N)) ) {
      \sum_i=1..( floor(ld(N)) ) {
          2^i
      }
  }

   // resolve inner summation
= \sum_j=1..( floor(ld(N)) ) {
      2^(floor(ld(N)) + 1) - 2
  }

   // resolve outer summation
= ld(N) * N - 2 * floor(ld(N))

在 Big-Oh 表示法中，这相当于 O(N log N)(表达式中的第二项逐渐消失到第一项)。