基于回代法求解递推关系式T(n)=√n T(n/2)+√n的结果

已知递推关系：

当 ( n=2^{2k} )（( k≥0 )）时，( T(n)=\sqrt{n}·T(n/2)+\sqrt{n} )，初始条件 ( T(1)=1 )

步骤1：简化递推式 #

对递推式两边同时除以 ( \sqrt{n} )，消去系数简化形式：
[
\frac{T(n)}{\sqrt{n}} = \frac{T(n/2)}{\sqrt{n/2}} + 1
]
令 ( S(n) = \frac{T(n)}{\sqrt{n}} )，则递推式转化为线性非齐次递推：
[
S(n) = S(n/2) + 1
]
代入初始条件 ( T(1)=1 )，可得 ( S(1) = \frac{T(1)}{\sqrt{1}} = 1 )

步骤2：迭代求解 ( S(n) ) #

对简化后的递推式进行迭代回代：

• 第1次迭代：( S(n) = S(n/2) + 1 )
• 第2次迭代：( S(n) = [S(n/4) + 1] + 1 = S(n/4) + 2 )
• 第3次迭代：( S(n) = [S(n/8) + 1] + 2 = S(n/8) + 3 )
• ...
• 第 ( m ) 次迭代：( S(n) = S(n/2^m) + m )

当迭代到初始条件时，需满足 ( n/2^m = 1 )，即 ( m = \log_2 n )。结合 ( n=2^{2k} )，可得 ( m = 2k )。

代入初始条件 ( S(1)=1 )：
[
S(n) = S(1) + m = 1 + \log_2 n
]

步骤3：还原得到 ( T(n) ) #

根据 ( S(n) = \frac{T(n)}{\sqrt{n}} )，反向推导：
[
T(n) = \sqrt{n} · S(n) = \sqrt{n} (\log n + 1)
]
注：若题目中 ( \log n ) 指定非2为底的对数，仅需调整对数底数，核心形式保持一致。

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