如何计算递推关系时间复杂度？求解T(n)=n*T(n-1)的大O记法

该递推式对应的正确时间复杂度为O(n!)，O(n^n)是过于宽松的非紧上界，不属于该递推的标准复杂度结果。

递推展开求解过程 #

从给定边界条件T(1)=1出发，逐层代入展开递推关系即可得到闭式解：

• T(n) = n * T(n-1)
• T(n-1) = (n-1) * T(n-2)
• T(n-2) = (n-2) * T(n-3)
• ...
• T(2) = 2 * T(1) = 2 * 1 = 2
  将所有层级的表达式逐层回代，最终得到：
  T(n) = n * (n-1) * (n-2) * ... * 2 * 1 = n!
  既然T(n)的精确值就是n!，其自然满足大O记法下的O(n!)上界。

为什么O(n^n)不是正确结果 #

大O记法的核心要求是给出和实际运行时间增长阶匹配的渐近紧上界，而非随便找一个增长更快的函数作为结果。
我们可以通过斯特林公式直观对比n!和n^n的增长差距：
n! ≈ sqrt(2πn) * (n/e)^n
可以看到n!的增长阶等价于(n/e)^n，和nn之间差了e^{n的量级，n!的增长速度远慢于n}n。如果用O(n^{n)描述这个递推的复杂度，就相当于把O(n)的算法说成O(2}n)，虽然数学上满足上界要求，但完全没有反映算法的实际增长速度，是错误的复杂度表述。

这类递推的大O推导核心规则 #

• 优先通过逐层展开、递归树、主定理等方法得到递推式的闭式解或者精确渐近增长阶
• 选择和实际增长阶同阶的、最紧致的简单初等函数作为大O结果，不选增长速度远高于实际值的宽松上界
• 验证上界合理性的标准：当n足够大时，存在常数c>0使得T(n) ≤ c*f(n)，且不存在增长速度慢于f(n)的简单初等函数能满足该不等式，此时O(f(n))才是符合要求的复杂度结果。

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