如何用代入法求解递推式T(n)=2T(n/2)+nlogn？原式是否有误？

原递推式的问题分析 #

原递推式T(n)=2T(n)(n/2)+nlogn存在核心逻辑错误：

• 等式右侧的2T(n)*(n/2)化简后为n*T(n)，导致等式变为T(n) = n*T(n) + nlogn，移项后得到T(n)*(1-n) = nlogn。当n>1时，计算出的时间复杂度为负数，完全违背算法时间复杂度的非负性定义。
• 该式子不符合分治递推式的基本结构：分治递推式应将原问题拆分为更小的子问题（如T(n/2)），而非重复出现原问题的解T(n)，无法体现分治算法“拆分-求解子问题-合并”的流程。

正确递推式的代入法求解 #

正确的分治递推式应为T(n)=2T(n/2)+nlogn，我们用代入法证明其解为Θ(n log²n)，最紧的大O表示为O(n log²n)。

步骤1：猜测解的形式 #

结合递推式的分治结构（2个规模为n/2的子问题+线性对数级合并代价），猜测解的形式为T(n) = Θ(n log²n)，需分别证明上界O(n log²n)和下界Ω(n log²n)。

步骤2：证明上界O(n log²n) #

假设对于所有k < n，存在常数c ≥ 1，使得T(k) ≤ c k log²k成立。将其代入递推式：

T(n) = 2T(n/2) + n logn
≤ 2 * c*(n/2) * log²(n/2) + n logn
= c n (logn - 1)² + n logn
= c n (log²n - 2logn + 1) + n logn
= c n log²n - 2c n logn + c n + n logn

要使T(n) ≤ c n log²n，需满足：

-2c n logn + c n + n logn ≤ 0

两边除以n（n>0）并整理：

logn(1-2c) + c ≤ 0

取c=1，当n≥2时，logn≥1，代入得-logn +1 ≤0，显然成立。因此上界得证。

步骤3：证明下界Ω(n log²n) #

假设对于所有k <n，存在常数d ≤ 1/4，使得T(k) ≥ d k log²k成立。代入递推式：

T(n) = 2T(n/2) + n logn
≥ 2*d*(n/2)*log²(n/2) + n logn
= d n (logn -1)² + n logn
= d n (log²n -2logn +1) + n logn
= d n log²n -2d n logn +d n +n logn

要使T(n) ≥ d n log²n，需满足：

-2d n logn +d n +n logn ≥0

两边除以n并整理：

logn(1-2d) +d ≥0

取d=1/4，当n≥2时，logn≥1，代入得(1/2)logn + 1/4 ≥ 3/4 >0，显然成立。因此下界得证。

综上，T(n)=Θ(n log²n)，最紧的大O表示为O(n log²n)。

内容的提问来源于stack exchange，提问作者吳承祐