如何用代入法求解含平方根的递推关系及绘制递归树

一、代入法求解步骤 #

1. 猜测解的形式 #

先通过展开递推式观察规律：

• 顶层（原问题）：代价为 √n
• 第1层：4个T(n/2)子问题，每个附加代价 √(n/2)，总代价为 4*√(n/2) = 2√2·√n
• 第2层：16个T(n/4)子问题，每个附加代价 √(n/4)，总代价为 16*√(n/4) = 8√n
• 第k层：4^k个T(n/2^k)子问题，每个附加代价 √(n/2^k)，总代价为 4^k·√(n/2^k) = 2^(3k/2)·√n

递归终止于n=1（设T(1)为常数c），此时k=log₂n。将各层代价求和，求和项是首项为√n、公比为2√2的等比数列，最终求和结果为O(n²)；终止层总代价为4^log₂n·c = n²·c，同样是O(n²)。因此猜测解为T(n) = Θ(n²)。

2. 归纳证明上界 #

假设T(n) ≤ cn² - d√n（引入-d√n是为了抵消递推中的附加项）：

• 基例：当n=1时，取c ≥ T(1) + d，则T(1) ≤ c·1 - d·1成立。
• 归纳步骤：假设对所有m < n，T(m) ≤ cm² - d√m成立。则：

  T(n) = 4T(n/2) + √n
       ≤ 4·[c·(n/2)² - d·√(n/2)] + √n
       = cn² - (4d/√2)√n + √n
       = cn² - d√n·2√2 + √n
  

  令-2√2 d + 1 ≤ -d，解得d ≥ 1/(2√2 - 1)。取该d值，上式可简化为T(n) ≤ cn² - d√n，归纳成立。因此T(n) = O(n²)。

3. 归纳证明下界 #

假设T(n) ≥ cn²：

• 基例：当n=1时，取c ≤ T(1)，则T(1) ≥ c·1成立。
• 归纳步骤：

  T(n) = 4T(n/2) + √n
       ≥ 4·c·(n/2)² + √n
       = cn² + √n ≥ cn²
  

  显然成立，因此T(n) = Ω(n²)。

综上，T(n) = Θ(n²)。

二、递归树绘制方法 #

递归树以层级结构展示子问题分解和代价分布：

• 第0层（顶层）：单个节点，标注代价√n，对应原问题T(n)。
• 第1层：顶层节点分裂为4个节点，每个节点对应子问题T(n/2)，标注附加代价√(n/2)；该层总代价为4·√(n/2)。
• 第k层：包含4^k个节点，每个对应子问题T(n/2^k)，标注附加代价√(n/2^k)；该层总代价为4^k·√(n/2^k)。
• 终止层（第log₂n层）：当n/2^k=1时，共4^log₂n = n²个节点，每个标注常数代价T(1)；该层总代价为n²·T(1)。

绘制时可简化为：画出前2-3层节点并标注代价，用省略号表示中间层级，最后标注终止层的节点数量和总代价，同时在每层旁标注该层总代价，直观展示求和规律。

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