嵌套循环时间复杂度是否一定为各层循环复杂度的乘积？

• 嵌套循环的时间复杂度并不始终等于各层循环单独计算所得复杂度的乘积。两层循环复杂度直接相乘的适用前提是：内层循环的迭代次数完全独立于外层循环的迭代变量，和外层当前执行到哪一步没有关系。如果内层循环的执行次数受外层循环变量约束，直接相乘会得到错误的结果。

示例代码 #

for (int i = 1; i < n; i*=2)
  for (int j = 0; j < i; j +=2)
  {
    // some constant time operations
  }

错误判定的问题所在 #

题中提到的「外层O(logn)、内层O(n)，相乘得O(nlogn)」的判定是错误的，问题出在对内层循环复杂度的计算上：内层循环的上界是外层变量i，不是固定值n，不能把内层循环单独拿出来取最坏情况的O(n)，套用到每一次外层迭代中。

正确复杂度推导 #

我们逐轮统计迭代次数即可：

1. 外层循环的i从1开始，每次乘以2，直到不满足i < n，因此i的取值序列为1,2,4,8,...,2^k，满足2^k < n ≤ 2^{k+1}，外层总迭代次数为k+1，确实是O(logn)量级。
2. 对每一轮固定的i，内层循环j从0开始每次加2，直到j >=i，单轮内层的迭代次数为ceil(i/2)：步长为2的情况下，遍历0到i-1区间的整数，总次数就是i/2向上取整。
3. 把所有轮次的内层迭代次数加总，得到总操作数：
   当i=1时，迭代1次；i=2时，迭代1次；i=4时，迭代2次；i=8时，迭代4次……直到i=2^{k时，迭代2}{k-1}次。
   这是首项为1、公比为2的等比数列，求和结果为2^k，结合之前的约束2^k <n，可得总操作数严格小于n，因此整段代码的时间复杂度是O(n)，而非O(nlogn)。

计算规则总结 #

• 只有内层循环迭代次数和外层变量完全无关时，才可以直接将两层循环的复杂度相乘得到总复杂度，比如外层遍历1到n、内层固定遍历1到n的场景，总复杂度就是O(n)*O(n)=O(n²)。
• 只要内层循环的边界、步长和外层循环变量存在绑定关系，就必须按外层迭代的轮次逐次累加内层操作数，再推导最终的复杂度量级，不能直接套用乘法规则。

内容的提问来源于stack exchange，提问作者Adi Wiesel