如何根据含3输入的代码推导递推关系？附算法与解法疑问

给定算法伪代码 #

ALGO(A,s,d)
    m=d-s+1
    if m>=2 then
        q=⌊m/2⌋
        return 2ALGO(A, s, s+q-1) + 3ALGO(A, s+q, d);
    else
        return 1
    endif

问题描述 #

初始调用为ALGO(A, 1, n)（A是大小为n的数组，s、d为整数，q是m/2的向下取整），需要推导以n为变量的递推关系。

你的推导与疑问 #

自行推导的递推关系 #

T(n) = 1 当 n<2
T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + Θ(1) 当 n>=2

推理逻辑 #

初始调用时m=n，q=⌊n/2⌋；第一个递归调用对应规模⌊n/2⌋，第二个对应规模⌈n/2⌉，加上计算q的常数时间Θ(1)，得到上述式子。

疑问点 #

1. 该递推关系是否正确？
2. 如何求解这个递推关系？
3. 是否可以认为T(⌊n/2⌋) + T(⌈n/2⌉) = T(n)？

解答 #

1. 递推关系正确性判断 #

递推关系的正确性取决于T(n)的定义：

• 如果T(n)表示算法的返回值：你的推导错误。原算法返回的是2*ALGO(...) + 3*ALGO(...)，因此返回值的递推式应为：

  T(n) = 1, 当 n < 2
  T(n) = 2*T(⌊n/2⌋) + 3*T(⌈n/2⌉), 当 n >= 2
  

  这里不需要加Θ(1)，因为计算q的常数时间不影响返回值结果。

• 如果T(n)表示算法的时间复杂度：你的推导正确。时间复杂度统计执行步骤数，递归调用了两次子过程，加上计算m、q、判断条件的常数时间，因此递推式符合你的推导（n<2时的时间也是Θ(1)，写1等价）。

2. 递推关系求解 #

情况1：返回值递推关系求解

• 当n是2的幂（n=2^k）时，⌊n/2⌋=⌈n/2⌉=n/2，递推式简化为T(n)=5*T(n/2)，结合初始条件T(1)=1，解得：
  T(n)=5^k=5^(log₂n)=n^(log₂5)≈n^2.32
• 当n不是2的幂时，通过数学归纳法可证明T(n)=Θ(n^(log₂5))，增长趋势与2的幂情况一致。

情况2：时间复杂度递推关系求解

• 当n是2的幂（n=2^k）时，递推式简化为T(n)=2*T(n/2)+c（c为常数），用主定理求解：a=2，b=2，f(n)=Θ(1)，满足主定理第一种情况，得T(n)=Θ(n)。
• 当n不是2的幂时，通过递归树或数学归纳法可证明T(n)=Θ(n)：递归树每一层时间开销为c*2^i，总层数为log₂n，总和为c*(n-1)=Θ(n)。

3. 关于T(⌊n/2⌋) + T(⌈n/2⌉) = T(n)的判断 #

这个等式不成立，仅当T(n)是线性函数时例外：

• 比如时间复杂度的T(n)=Θ(n)，T(⌊n/2⌋)+T(⌈n/2⌉)=Θ(n)，渐近意义上等价于T(n)，但严格等式仅在T(n)为线性函数（如T(n)=n）时成立。
• 对于返回值的T(n)=n^(log₂5)，T(⌊n/2⌋)+T(⌈n/2⌉)≈(2/5)*T(n)，显然不等于T(n)。

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