递归式中“n<2/n≤2时T(n)为常数”的含义解析

一、先把这个边界条件说清楚 #

当递归式里写“当n≤2时，T(n)为常数”，你可以把它理解成递归的**“终止开关”**：

• 当问题规模小到n=1或者n=2的时候，我们不需要再把问题拆分成更小的子问题了，直接用固定的几步操作就能解决，这几步操作的时间开销是固定的，不会随着n变化而增长——也就是我们常说的Θ(1)时间。
• 这里的“常数”不是某个特定数字（比如不是必须等于3），而是说不管n是1还是2，求解时间都在一个固定的小范围内，不会出现n越大耗时越长的情况。比如你写个找数组最大值的递归函数，当数组长度≤2时，直接比一下（或者直接返回唯一元素），这就是典型的常数时间操作。

二、推导T(n)上下界的实用思路 #

既然明确了终止条件，推导渐近上界（O）和下界（Ω），咱们通常用这三种方法：

1. 代入法（Substitution Method） #

这是最“手动”的方法，步骤很清晰：

• 先根据递归式的形式猜一个可能的上下界（比如猜T(n)=O(n log n)）；
• 然后用数学归纳法验证这个猜测，归纳基例就用n=1和n=2的情况——因为这时候T(n)是常数，很容易验证猜测的不等式是否成立；
• 归纳步骤里，把递归式代入猜测的表达式，整理后看是否能满足渐近界的定义。

2. 递归树法（Recursion Tree Method） #

这个方法更直观，适合可视化递归的开销：

• 把递归式展开成一棵树，每个节点代表一次递归调用的时间开销；
• 树的叶子节点就是n≤2的情况，每个叶子的开销都是常数；
• 计算每一层的总开销，再把所有层次的开销加起来，就能得到T(n)的渐近界。比如如果递归树有log n层，每层总开销是O(n)，那最终结果就是O(n log n)。

3. 主方法（Master Method） #

如果你的递归式是《算法导论》里最常见的形式：T(n) = aT(n/b) + f(n)（n>2），那主方法就是“一键解决”的神器：

• 直接套用主方法的三个判定规则，对比f(n)和n^log_b a的阶数关系；
• 主方法默认已经包含了“n足够小时T(n)为常数”的边界条件，所以你不用额外处理边界，直接套公式就行。

举个例子：假设递归式是T(n) = 2T(n/2) + n（n>2），n≤2时T(n)为常数。用主方法的话，a=2，b=2，n^log_b a = n，和f(n)=n同阶，所以T(n)=Θ(n log n)——这就同时给出了上下界。

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