求解指定嵌套循环代码的最佳与最坏时间复杂度

待分析代码 #

A(n):
  for (int i = 1; i < n; i*=2) {
     for (int j = 0; j < i; j++) {
        if (i == j) return; // does nothing
        for (int k = n; k > 0; k--)
           if (f(n)) 
              return g(n);
     }
  }

已知函数复杂度边界 #

f(n)：时间复杂度上界O(n)，下界Ω(log⁷(n))
g(n)：时间复杂度为紧界Θ(n² * log⁶(n))（上界、下界均为该值）

前置关键结论 #

代码中if (i == j) return;是不可达死代码：中层j循环的终止条件为j < i，j的最大取值为i-1，永远不可能等于i，该分支永远不会触发，不影响执行流程。所有退出路径只有两种：

1. 所有循环执行完毕（f(n)始终返回false）
2. 某次k循环中f(n)返回true，执行g(n)后返回

最坏情况时间复杂度 #

第二种推导思路正确，最坏时间复杂度为O(n³)，推导过程如下：

1. 外层i循环：i按2的幂次递增（取值为1,2,4,8...直到小于n），共迭代log₂n次。
2. 中层j循环：对每个取值为2^m的i，j循环共执行i=2^m次。所有i对应的j循环总次数为等比数列求和：1+2+4+...+2^floor(log₂(n-1)) = 2*2^floor(log₂(n-1)) -1 ≤ 2n-1 = O(n)，不存在O(n log n)的总次数，第一种思路错误将单次i对应的最大j迭代数n直接乘以外层循环次数logn，属于重复计算。
3. 内层k循环与f(n)调用：最坏情况下f(n)始终返回false，每次进入k循环都会完整执行n轮迭代，每轮迭代调用1次f(n)，单轮k循环的最坏开销为n * O(n) = O(n²)。
4. 总开销计算：中层j循环总次数为O(n)，对应所有k循环的总开销为O(n) * O(n²) = O(n³)；即使g(n)在最后一轮迭代才触发，其复杂度O(n² log⁶n)远低于O(n³)，不改变最终上界。

最好情况时间复杂度 #

你的推导成立，最好时间复杂度为Θ(n² log⁶(n))，推导过程如下：
最早触发退出的路径为：第一次进入循环（i=1、j=0）后，k循环第一轮迭代调用f(n)就返回true，直接执行g(n)返回。此时仅执行1次f(n)调用和1次g(n)调用：

• f(n)单次调用的最好开销为Ω(log⁷n)，远低于g(n)的开销
• g(n)的时间为紧界Θ(n² log⁶n)，是该路径的主导开销
  不存在更早的退出路径（死代码无法触发），因此最好情况复杂度由g(n)决定。

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