嵌套循环的时间复杂度：O(NlogN)还是O(N)？

先看你给出的代码：

for (i=1;i<=n;i*=2){
  for (j=1;j<=i;j++) {
    // some O(1) operation
  }
}

你的同行结论正确，这个算法的时间复杂度是O(n)，而非你认为的O(nlogn)。

具体计算过程 #

外层循环中，i的取值依次是1、2、4、8……直到不超过n的最大2的幂（设为2^k，满足2^k ≤n <2^(k+1)）。内层循环每次执行i次O(1)操作，因此总操作次数是一个等比数列的和：
1 + 2 + 4 + 8 + ... + 2^k

根据等比数列求和公式，这个和等于2^(k+1) - 1。由于2^k ≤n，可得2^(k+1) ≤2n，因此总操作次数2^(k+1)-1 ≤2n-1，显然这个规模是和n线性相关的，属于O(n)级别。

直觉逻辑解释 #

你之前的错误在于误用了嵌套循环复杂度的计算方式——通常“外层O(logn)×内层O(n)”的结论，是建立在内层循环每次都执行n次的前提下，但这里内层循环的执行次数是随外层i指数增长，且外层循环的次数是对数级的。

可以直观理解为：把总操作次数看成是不断翻倍的累加，1+2+4+…的总和永远不会超过最后一项的2倍，而最后一项不超过n，所以总和最多接近2n，和n是线性关系。比如n=8时，总操作是15（接近2×8）；n=10时，总操作还是15（小于2×10）。整个累加过程的总和始终和n处于同一量级，而非n乘以logn。

内容的提问来源于stack exchange，提问作者Divyadeep Singh