如何使用代入法求解T(n)=2T(n/2)+n*log2(n)递推式并求其大O阶？

前置说明 #

为简化计算，默认边界条件为T(1)=1，且n为2的幂（即n=2^k，k为非负整数，该假设不影响最终复杂度量级）。

步骤1：迭代展开找规律 #

我们先通过逐层展开递推式定位待证明的上界猜想：

• 初始层：T(n) = 2T(n/2) + n log₂n
• 展开1次：代入T(n/2)=2T(n/4) + (n/2)log₂(n/2)，得
  T(n) = 2²T(n/2²) + n log₂(n/2) + n log₂n
• 展开2次：代入T(n/4)=2T(n/8) + (n/4)log₂(n/4)，得
  T(n) = 2³T(n/2³) + n log₂(n/4) + n log₂(n/2) + n log₂n
• 展开到第k层：此时n/2^k = 1，即k=log₂n，得
  T(n) = 2^k T(1) + n·Σ（i从0到k-1）log₂(n/2^i)

步骤2：化简展开式 #

• 第一项化简：2^k = n，T(1)=1，因此第一项为n
• 求和项化简：

  Σ（i从0到k-1）log₂(n/2^i) = Σ（i从0到k-1）(log₂n - i)
  = k·log₂n - k(k-1)/2
  

  代入k=log₂n，得：

  = (log₂n)² - (log₂n (log₂n - 1))/2
  = [(log₂n)² + log₂n]/2
  

• 合并整体：
  T(n) = n + n·[(log₂n)² + log₂n]/2
  可以看出最高阶项为n(log₂n)²。

步骤3：代入法（归纳证明）验证上界 #

代入法的核心是先猜上界，再用数学归纳法证明：

1. 上界猜想：存在正常数c，当n足够大时，T(n) ≤ c·n(log₂n)²
2. 归纳基础：取n=2，原式计算得T(2)=2T(1)+2log₂2=4，代入猜解得c·2*(log₂2)²=2c，取c≥2即可满足2c≥4，基础成立。
3. 归纳假设：假设对于所有m <n（尤其m=n/2），均满足T(n/2) ≤ c·(n/2)(log₂(n/2))²
4. 归纳推导：
   将归纳假设代入原式：

T(n) = 2T(n/2) + n log₂n
≤ 2*[c·(n/2)(log₂(n/2))²] + n log₂n
= c·n(log₂n - 1)² + n log₂n
= c·n(log₂n)² + n(-2c log₂n + c + log₂n)

要让上式 ≤ c·n(log₂n)²，只需后一项括号部分≤0：
当c≥2，n≥2（即log₂n≥1）时：
log₂n(1-2c) + c ≤ 1*(1-2c) + c = 1 - c ≤ -1 < 0
满足条件，归纳成立。

最终时间复杂度 #

忽略低阶项和常数系数，该递推式的时间复杂度为 O(n(log n)²)

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