如何计算CoeffBin递归函数的T(n)方程与时间复杂度

待分析的递归函数实现如下：

Function CoeffBin(n,k)
if (n=1) or (k=0) then return(1)
else return (CoeffBin(n-1,k) + CoeffBin(n-1,k-1))

顺带说明：这段代码的基准条件并不完整，缺少了k=n时返回1的判断，会导致k≥n时的计算结果不符合二项式系数的定义，但不影响我们分析其递归结构的复杂度增长趋势。

递推方程推导 #

我们用T(n,k)表示输入为n、k时函数的运行时间，按执行逻辑拆分：

• 基准情况：当触发n=1或k=0的判断条件时，函数直接返回常量值，没有递归调用，除了判断逻辑外没有额外开销，属于常数级时间：
  T(n,k) = O(1)，满足n=1 或 k=0时成立
• 递归情况：当不触发基准条件时，函数会先后发起两次递归调用，参数分别为(n-1,k)和(n-1,k-1)，除此之外的条件判断、加法运算、返回操作都是常数级开销，因此递推关系为：
  T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)，满足n>1 且 k>0时成立

时间复杂度求解 #

因为每次函数调用的非递归操作都是常数开销，总运行时间和递归调用的总次数呈线性正相关，我们可以通过统计调用次数推导复杂度：

1. 当输入为合法的二项式系数取值范围0 ≤ k ≤ n时，通过数学归纳可以证明，补全k=n的基准条件后，总调用次数为2*C(n,k) - 1，其中C(n,k)是二项式组合数，因此时间复杂度和C(n,k)的量级一致。
2. 不同输入下的复杂度表现：
   • 如果k是固定常数（或n-k为固定常数，比如k=1、k=n-1这类场景），递推式会退化为线性递推，比如k=1时T(n,1) = T(n-1,1) + O(1)，最终时间复杂度为O(n)。
   • 最坏情况出现在k = n/2时，此时二项式系数C(n,k)取到最大值，用斯特林公式近似可以得到C(n, n/2) ≈ 2^n / sqrt(πn/2)，因此最坏时间复杂度为O(2^n)，属于指数级复杂度。
3. 这个实现效率极低的核心原因是存在大量重复计算：比如子问题CoeffBin(n-2, k-1)会同时被上层的CoeffBin(n-1,k)和CoeffBin(n-1,k-1)调用，相同入参的子问题会被反复计算多次。工程上如果要计算二项式系数，通常会用记忆化搜索或者动态规划的方式，把时间复杂度优化到O(nk)级别。

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