具有不同内部循环的嵌套循环的复杂性

Question

非常相似的复杂性示例。我试图了解这些问题有何不同。明天考试 :( 在这里找到复杂问题的任何捷径。

案例 1:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

案例 2:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 4) {}
   N = N / 2;   
   }
}

案例 3:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 2) {}
   N = N / 2;   
   }
}

非常感谢!

Answer 1

void doit(int N) { 
   while (N) {
     for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

要找到它的 O()，请注意我们在每次迭代中将 N 除以 2。所以，(不是侮辱你的智慧，而是为了完整性)通过循环的最终非零迭代我们将有 N=1。在那之前的时间我们将有 N=a(2)，然后在那之前 N=a(4)... 其中 0< a < N(注意那些是非包容性边界)。所以，这个循环将执行总共 log(N) 次，这意味着我们看到的第一次迭代 N=a2^(floor(log(N)))。

我们为什么要关心这个？好吧，这是一个几何级数，具有很好的封闭形式:

Sum = \sum_{k=0}^{\log(N)} a2^k = a*\frac{1-2^{\log N +1}}{1-2} = 2aN-a = O(N). 

如果有人能弄清楚如何让 latexy 符号正确显示给我，我将不胜感激。