如何分析兼具指数与对数特性的双递归函数时间复杂度？

先给出待分析的函数代码：

def recurse(n: int, k: int) -> int:
    if n <= 0 or k <= 0:
        return 1
    return recurse(n//2, k) + recurse(n, k//2)

复杂度推导思路 #

我们用T(n,k)表示输入为n和k时的函数总调用次数（因为每次递归除了调用子问题无其他耗时操作，时间复杂度等价于调用次数）。

边界条件

当n ≤ 0或k ≤ 0时，函数直接返回，仅1次调用，即T(n,k) = 1。

递推关系

当n > 0且k > 0时，当前函数会触发两次递归调用，加上自身的1次调用，因此递推式为：
T(n,k) = T(n//2, k) + T(n, k//2) + 1

具体分析 #

为了简化计算，先假设n=2^a、k=2^b（即n和k都是2的幂），此时n//2=2^(a-1)，k//2=2^(b-1)，递推式可转化为：
T(2^a, 2^b) = T(2^(a-1), 2^b) + T(2^a, 2^(b-1)) + 1

令S(a,b) = T(2^a, 2^b)，则S(a,b) = S(a-1,b) + S(a,b-1) + 1，边界条件为a≤0或b≤0时S(a,b)=1。

进一步变形，令U(a,b) = S(a,b) + 1，则递推式变为U(a,b) = U(a-1,b) + U(a,b-1)，边界条件为a≤0或b≤0时U(a,b)=2。这个递推式的解是组合数形式：U(a,b) = 2 * C(a+b, a)（C(n,m)表示从n个元素中选m个的组合数），因此S(a,b) = 2*C(a+b,a) - 1。

复杂度的上下界 #

• 上界：组合数C(a+b,a)的最大值不超过2^(a+b)，而a=log2(n)、b=log2(k)，因此2^(a+b)=nk，代入得T(n,k) ≤ 2*nk -1，即T(n,k) = O(nk)。你之前提到的O(2^(nk))确实是一个上界，但过于宽松，实际紧上界是O(nk)。
• 下界：当n和k都很大且相等时（比如n=k=2^m），根据斯特林公式，C(2m,m) = Ω(4^m / sqrt(m))，而4^m = n²、m=log2(n)，因此T(n,n) = Ω(n² / sqrt(log n))，即此时复杂度为Ω(nk / sqrt(log n))；当其中一个参数为常数时（比如k固定），递归树的节点数仅和log n成正比，即T(n,k)=Θ(log n)。

补充：n=2、k=4时的递归调用树 #

当输入n=2、k=4时，递归调用的结构如下：

• 根节点：recurse(2,4)
  • 左分支：recurse(1,4)
    • 左子节点：recurse(0,4) → 返回1
    • 右子节点：recurse(1,2)
      • 左子节点：recurse(0,2) → 返回1
      • 右子节点：recurse(1,1)
        • 左子节点：recurse(0,1) → 返回1
        • 右子节点：recurse(1,0) → 返回1
        • recurse(1,1)返回1+1=2
      • recurse(1,2)返回1+2=3
    • recurse(1,4)返回1+3=4
  • 右分支：recurse(2,2)
    • 左子节点：recurse(1,2) → 返回3
    • 右子节点：recurse(2,1)
      • 左子节点：recurse(1,1) → 返回2
      • 右子节点：recurse(2,0) → 返回1
      • recurse(2,1)返回2+1=3
    • recurse(2,2)返回3+3=6
• recurse(2,4)最终返回4+6=10

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