三层嵌套循环时间复杂度分析请求（内层依赖外层变量）

问题分析与解答 #

你的判断不正确，这个算法的时间复杂度是O(kⁿ)（当k>1时），具体推导过程如下：

1. 跟踪每轮外层循环的执行细节 #

初始时exp = 1，我们逐轮分析外层i循环的执行情况：

• 第0轮（i=0）：
  中层j循环执行k次，每次内层q循环执行exp=1次，q循环总执行次数为k*1 = k次，之后exp更新为k。
• 第1轮（i=1）：
  j循环执行k次，每次q循环执行exp=k次，总执行次数为k*k = k²次，exp更新为k²。
• 第2轮（i=2）：
  q循环总执行次数为k*k² = k³次，exp更新为k³。
• ...
• 第m轮（i=m，0≤m<n）：
  此时exp的值为kᵐ，q循环总执行次数为k*kᵐ = k^(m+1)次，exp更新为k^(m+1)。

2. 计算总执行次数 #

总执行次数是每一轮q循环执行次数的总和，即：

总次数 = k¹ + k² + k³ + ... + kⁿ

这是首项为k、公比为k的等比数列，求和公式为：

总次数 = k*(kⁿ - 1)/(k - 1)

3. 确定时间复杂度 #

当k>1时，kⁿ是这个和的主导项，其他项相对于kⁿ可以忽略，因此时间复杂度为O(kⁿ)。

• 特殊情况：当k=1时，每一轮q循环仅执行1次，总次数为n，时间复杂度为O(n)。

你之前猜测的O(n*k*kⁿ)错误在于，把最后一轮的执行次数直接乘以外层循环次数n，但实际上前面轮次的执行次数呈指数增长，等比数列的总和量级与最后一项同阶，不需要额外乘以n。

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