循环的增长顺序复杂

小编典典

循环的增长顺序复杂

algorithm

对于以下代码片段，以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 + ....）。序列的最后一项是什么？我需要最后一项来计算总和。

阅读 287

2020-07-28

共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))

这相当于O(N log N)Big-Oh表示法（表达式中的第二个术语渐渐消失到第一个术语）。

2020-07-28