算法时间复杂度求助：递推方程推导与O(k^n)验证

递推方程建立 #

设T(n)表示输入参数为n时算法的时间开销：

• 当n < 1时，仅执行打印错误的常数时间操作，因此T(n) = C（C为固定常数）。
• 当n ≥ 1时，算法会执行k次循环：每次循环包含1次O(1)的赋值A[n] = i，再递归调用Algorithm(n-1, k)。因此递推方程为：

  T(n) = k * (T(n-1) + C₁)
  

  其中C₁是赋值操作的常数时间开销，简化后可写成：

  T(n) = k·T(n-1) + k·C₁
  

递推方程求解 #

展开递推式逐步推导：

T(n) = k·T(n-1) + k·C₁
= k·(k·T(n-2) + k·C₁) + k·C₁ = k²·T(n-2) + k²·C₁ + k·C₁
= k³·T(n-3) + k³·C₁ + k²·C₁ + k·C₁
...
= kⁿ·T(0) + C₁·(kⁿ + kⁿ⁻¹ + ... + k² + k)

代入基准情况T(0)=C，并对等比数列求和（k≠1时）：

T(n) = C·kⁿ + C₁·k·(kⁿ - 1)/(k-1)

时间复杂度评估 #

当k > 1时，kⁿ是表达式中的主导项，其余低阶项和常数系数可忽略，因此算法的时间复杂度为O(kⁿ)。
若k = 1，递推式简化为T(n) = T(n-1) + 1，解为T(n) = n + C，时间复杂度为O(n)，这是特殊场景。

你的预期验证 #

你给出的时间复杂度**O(kⁿ)**是完全正确的（针对k>1的常规场景，这是算法的主导时间复杂度）。

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