如何为递归求解的代入法选择基准情况？含实例疑问

问题1：递归式T(n) = 2T(floor(n/2)) + Θ(n)的基准情况为何选n=2/3而非n=1？ #

首先明确：基准情况的核心要求是让递归终止，且为常数时间复杂度，n=1本身完全可以作为合法的基准情况，选n=2或3更多是推导时的便利性选择，而非必须。

在渐近分析（代入法要证明的是渐近界，比如O(nlogn)）中，只要基准情况是常数规模的输入（n=1、2、3都满足），最终的渐近复杂度结论不会改变。举个例子：

• 若设T(1)=c（常数），则T(2)=2c + Θ(2)，显然满足T(2)=O(2log2)；
• 若设T(2)=d（常数），推导时可以直接跳过n=1的计算，避免处理floor(n/2)=1时的微小细节，但本质上和选n=1的基准没有渐近差异。

很多资料选择n=2/3，是因为当推导到这些规模时，递归展开的步骤更简洁，且能直接匹配我们要证明的渐近式形式，但这并不意味着n=1不是合法基准。

问题2：递归式T(n) = T(n-1) + n的基准情况设为n=1是否正确？ #

是正确的，原因如下：

• 这个递归是线性递减型，n每次减1，要让递归终止，必须选一个最小的正整数输入（通常我们讨论的问题中n为正整数），n=1就是最自然的终止点；
• 当设T(1)=c（常数）时，可直接推导得T(n)=c + 2+3+...+n = Θ(n²)，符合渐近分析的逻辑；
• 若场景中允许n=0（比如空输入），设T(0)=c也可行，但绝大多数算法场景下，n=1是默认的合理基准。

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