算法导论中二次函数为Θ(n²)的证明为何选取特定c1、c2、n0常量

首先明确：这几个参数不是随意指定的，是为了满足Θ记号定义凑出来的一组可行解，且不是唯一解，推导逻辑完全基于Θ的核心要求：

对f(n)=Θ(g(n))，需要找到正的常量c₁、c₂、n₀，使得所有n≥n₀时，满足 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)

我们把二次函数的不等式两边同时除以n²，待证明的式子就简化为：
c₁ ≤ a + b/n + c/n² ≤ c₂ 对所有n≥n₀成立
核心就是要让随n增大不断变小的低阶项b/n和c/n²的波动，不会突破c₁和c₂划定的范围。 #

c₁、c₂的选取逻辑 #

这两个值只要和最高次项系数a拉开足够的缓冲空间，抵消低阶项的影响就可以，原书选c₁=a/4、c₂=7a/4只是诸多合法选择中的一种，你选c₁=a/3、c₂=2a这类组合只要范围合理也完全成立，原书选分母为4的数值只是为了后续计算n₀的时候更方便凑整。 #

n₀的选取逻辑 #

n₀的取值完全是匹配前面选的c₁、c₂来定的：

• 我们需要低阶项的绝对值之和不超过3a/4，这样下限a - 3a/4 = a/4刚好等于c₁，上限a + 3a/4 =7a/4刚好等于c₂
• 要满足|b|/n ≤ a/2，就需要n ≥ 2|b|/a
• 要满足|c|/n² ≤ a/4，就需要n ≥ 2·√(|c|/a)
• 把两个条件合并，取最大的那个作为n₀，就是原书给出的n₀ = 2 · max(|b|/a, √(|c|/a))

简单说，这些参数都是为了刚好凑出符合Θ定义的不等式的可行解，数值本身没有特殊含义，只要能满足要求，你完全可以自己定另一组参数完成证明。

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