划分函数T(n)递推式推导及主定理求解的O(n)工作量疑问

嘿，咱们一步一步来拆解这个问题，先从递推式的简化分析开始，再验证它的渐近复杂度是不是O(n)：

1. 递推式的渐近简化 #

首先，当n足够大时，n/2 + 1和n/2 - 1这两个子问题规模的渐近量级都是Θ(n/2)——常数项±1在n趋向无穷时可以忽略，因为它们和n的比例趋近于0。所以我们可以先把递推式近似为：
T(n) ≈ 2T(n/2)

不过严谨起见，我们可以通过替换法来严格证明它的复杂度。

2. 用替换法证明T(n) = Θ(n) #

我们先假设T(n)的上界是O(n)，即存在常数c > 0和足够大的n，使得T(n) ≤ c·n。将其代入递推式：

T(n) = T(n/2 + 1) + T(n/2 - 1)
     ≤ c·(n/2 + 1) + c·(n/2 - 1)
     = c·(n/2 + 1 + n/2 - 1)
     = c·n

刚好满足上界的假设，说明O(n)是成立的。

再看下界，假设T(n) ≥ d·n（d > 0为常数），代入递推式：

T(n) = T(n/2 + 1) + T(n/2 - 1)
     ≥ d·(n/2 + 1) + d·(n/2 - 1)
     = d·n

同样满足下界假设，所以T(n) = Θ(n)，自然也属于O(n)的工作量范畴。

3. 主定理的应用 #

主定理标准形式是T(n) = aT(n/b) + f(n)，这里虽然子问题规模不是严格的n/2，而是n/2 ±1，但由于n/2 ±1 = Θ(n/2)，我们可以把它适配到主定理的框架中：

• a=2（每次递归拆分成2个子问题）
• b=2（子问题规模渐近为原问题的1/2）
• log_b a = log₂2 = 1

基础情况中，假设T(1)、T(2)都是常数，即f(n)=O(1)=O(n^(1-ε))（取ε=1即可），符合主定理的第一种情况，因此T(n)=Θ(n^1)=Θ(n)。

总结 #

不管是替换法还是适配主定理分析，都能得出这个递推式的渐近复杂度是Θ(n)，也就是你关心的O(n)工作量是成立的——递归拆分的子问题总规模每次都是线性的，没有指数级增长的情况。

内容的提问来源于stack exchange，提问作者mj-go