递归替换法分析递推式：验证T(n)=Ɵ(n²)是否正确

嘿，咱们先把递推式里的36n/2简化成18n，看着更清楚——也就是T(n) = 4T(18n) + cn²。先直接给结论：你猜测的T(n) = Ɵ(n²)是不正确的，因为这是个膨胀递归（子问题规模比原问题还大），时间复杂度远高于多项式级别。咱们用递归替换法一步步拆解看看：

1. 递归展开过程 #

咱们逐层展开递归式：

• 第0层（原问题）：T(n) = 4T(18n) + cn²
• 第1层：把T(18n)代入原式子，得到：

  T(n) = 4[4T(18*18n) + c*(18n)²] + cn² = 4²T(18²n) + 4*c*(18²n²) + cn²
  

• 第k层：归纳一下，第k层的展开式是：

  T(n) = 4ᵏT(18ᵏn) + cn² * Σ(i=0到k-1) (4*18²)ⁱ
  

  这里的求和项是等比数列，公比是4*18² = 4*324 = 1296，明显大于1。

2. 求和项的增长趋势 #

等比数列Σ(i=0到k-1) 1296ⁱ的和是(1296ᵏ - 1)/(1296 - 1)，当k增大时，这个和会指数级爆炸增长，因为公比远大于1。

3. 递归终止条件的矛盾 #

常规的分治递归是子问题规模不断缩小，最终达到终止条件（比如T(1)=O(1)），但这个递推式里，子问题规模是18ᵏn，每一层都比上一层大18倍——也就是说，递归永远不会自然终止（除非你设定一个非常大的边界值，但即便如此，到达边界时k的值会让4ᵏ和1296ᵏ都变成天文数字）。

4. 结论：时间复杂度是指数级 #

从展开式能看出来，T(n)的主导项是指数级的1296ᵏ，而不是多项式级别的n²。所以这个递推式的时间复杂度是指数级，完全不可能是Ɵ(n²)。

如果你的递推式是笔误（比如应该是T(n) = 4T(n/18) + cn²），那用递归替换法确实能证明T(n)=Ɵ(n²)——但就当前给出的递推式而言，你的结论不对。

内容的提问来源于stack exchange，提问作者S. jubair