为何不能用乘法计算时间复杂度？嵌套循环复杂度求解困惑

先纠正一个误解：你的代码实际复杂度是O(n) #

先把你给出的伪代码贴出来：

count = 0;
for (i = 1; i < n; i *= 2) 
    for (j = 0; j < i; j++) 
        count++;

我们一步步拆解总执行次数：

• 外层循环的i取值是1、2、4、8……直到i < n。假设n=2^k，那么i会取到2^{k-1}，外层循环一共执行k次，而k=log₂n。
• 对应每一次外层循环，内层循环的执行次数等于当前的i值：第一次1次，第二次2次，第三次4次……最后一次2^{k-1}次。
• 总执行次数是等比数列求和：1+2+4+…+2^{k-1} = 2^k -1。因为n=2^k，所以总次数是n-1，时间复杂度为O(n)。

你之前误以为是O((logn)²)，是错误套用了“嵌套循环次数相乘”的规则；而你听到的“正确答案是logn”也不对，实际复杂度是O(n)。

什么时候能直接用“循环次数相乘”？ #

只有当内层循环的执行次数和外层循环的变量完全无关时，才能直接相乘。举两个典型例子：

• 固定次数的内层循环：

  for (i=0; i<n; i++)
      for (j=0; j<m; j++)
          // 操作
  

  内层循环每次都执行m次，和i无关，总执行次数是n*m，复杂度为O(n*m)。
• 两层都遍历n次的循环：

  for (i=0; i<n; i++)
      for (j=0; j<n; j++)
          // 操作
  

  内层循环次数固定为n，和i无关，总次数是n*n，复杂度为O(n²)。

什么时候不能直接相乘？ #

当内层循环的执行次数依赖于外层循环的变量时，绝对不能直接乘，必须把每一次内层循环的次数累加起来，再分析总和的渐近复杂度。除了你给出的例子，再举一个常见场景：

for (i=1; i<=n; i++)
    for (j=1; j<=i; j++)
        // 操作

总执行次数是1+2+3+…+n = n(n+1)/2，复杂度为O(n²)——这里虽然结果和n*n的复杂度级别一样，但计算逻辑是求和，不是直接相乘。

再举一个可以相乘的反例：

for (i=n; i>=1; i/=2)
    for (j=0; j<n; j++)
        // 操作

这里内层循环次数固定为n，和i无关，所以总次数是log₂n * n，复杂度为O(nlogn)，这时候就可以直接相乘。

通用计算步骤 #

1. 先分析外层循环的所有变量取值，确定外层循环的总次数。
2. 对每一次外层循环，计算内层循环的执行次数。
3. 若内层次数与外层变量无关：直接用外层次数×内层次数，再取渐近复杂度；若有关：把所有内层次数求和，再分析这个和的渐近复杂度。

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