如何用归纳法证明递推式T(n)=x^k T(n/x)+Cn^k的时间复杂度为O(n^k logn)

首先明确递推关系：

• 基础情况：T(1) = 1
• 递推式：T(n) = x^k * T(n/x) + Cn^k，其中C、k、x为常数（默认x>1，符合分治递推的常见场景）

我们的目标是证明：存在常数M>0和n₀≥1，当n≥n₀时，T(n) ≤ M n^k log n，即T(n) = O(n^k log(n))。

步骤1：先针对n为x的幂次做简化分析 #

先考虑n = x^m（m为非负整数），后续再扩展到一般n：

• 当m=0时，n=1，T(1)=1。只要选取M≥1，就能满足1 ≤ M*1^k*(log1 + 1)（因为log1=0，式子右侧为M），基础情况成立。

步骤2：归纳假设 #

假设对于所有n' = x^t（t < m，即n' < n=x^m），均有T(n') ≤ M n'^k log n'。

步骤3：归纳步骤 #

计算T(n)=T(x^m)：

T(x^m) = x^k * T(x^(m-1)) + C*(x^m)^k

将归纳假设代入T(x^(m-1))：

T(x^m) ≤ x^k * [M*(x^(m-1))^k * (m-1)logx] + C x^(mk)

化简第一项：x^k * x^(k(m-1)) = x^(km)，代入后整理得：

T(x^m) ≤ M x^(mk) (m-1)logx + C x^(mk)
= x^(mk) [ M(m-1)logx + C ]

我们希望上式 ≤ M x^(mk) * m logx，只需满足：

M(m-1)logx + C ≤ M m logx

整理不等式得：

C ≤ M logx

由于x>1，logx>0，只要选取M ≥ C / logx，该不等式就成立。此时：

T(x^m) ≤ M x^(mk) * m logx = M n^k logn

（因为n=x^m，logn = m logx），归纳步骤得证。

步骤4：扩展到一般n #

对于任意n≥1，存在整数m使得x^m ≤ n < x^(m+1)。由于递推式中各项均为正，T(n)是单调递增函数，因此：

T(n) ≤ T(x^(m+1)) ≤ M (x^(m+1))^k log(x^(m+1))

又因为x^(m+1) ≤ x*n，且当n≥x时，log(x^(m+1)) = (m+1)logx ≤ log(xn) = logx + logn ≤ 2logn，代入后得：

T(n) ≤ M x^k n^k * 2logn = (2M x^k) n^k logn

令M' = 2M x^k，则当n≥x时，T(n) ≤ M' n^k logn，结合基础情况，可确定T(n)=O(n^k logn)。

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