如何分析该C++三重循环函数的时间复杂度？n为2^m时复杂度是多少？

该函数的实际时间复杂度为 O(n²)，你最初估算的O(n² log n)多了一个冗余的对数因子，问题出在对后两层循环的总执行次数的估算上。

分步推导过程 #

• 第一步：分析最外层循环
  最外层for (int i = n; i > 0; i--)共执行n次，且i的取值不影响内层循环的执行逻辑，因此只需先算出单次外层循环中内层两层的总执行次数，再乘以n即可得到全局总执行次数。
• 第二步：分析内层两层循环的总执行次数
  中间层j的取值序列为1, 2, 4, 8,...，直到j >=n为止，确实共有*O(log n)次循环，但每次最内层k循环的执行次数等于当前j的取值，不是固定的O(n)。
  把所有j对应的k循环次数求和，得到等比数列：
  S = 1 + 2 + 4 + 8 + ... + 2^t（其中2^t < n ≤ 2^(t+1)）
  根据等比数列求和公式，S = 2^(t+1) - 1 < 2n，即内层两层循环的总执行次数为O(n)*级别。
• 第三步：合并得到全局复杂度
  外层n次 × 单次内层O(n) = 总复杂度 O(n²)。

针对n=2^m场景的验证 #

当n为2的m次方时，j的最大取值为2^(m-1)，代入求和公式可得：
S = 2^m - 1 = n - 1
完全符合O(n)的结论，此时全局总执行次数为n*(n-1)，量级完全匹配O(n²)。

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