algorithm - 二次函数的渐近紧界

Question

在 CLRS(Cormen、Leiserson、Rivest 和 Stein 的 Introduction to Algorithms)中，对于一个函数

f(n) = an² + bn + c

他们说

Suppose we take the constants c₁ = a/4, c₂ = 7a/4, and n₀ = 2·max(|b|/a, √(|c|/a)).
Then 0 ≤ c₁n² ≤ an² + bn + c ≤ c₂n² for all n ≥ n₀.
Therefore f(n) is Θ(n²).

但是他们没有说明这些常量的值是怎么来的？
我试图证明它但不能。
请告诉我这些常量是怎么来的？

Answer 1

这些特定常量没有什么特别之处(除了在某个 n 值的上下文中它们将满足 f 的 theta 度之外)。没有魔法。如果你能找到其他正常数，据此关系成立，那也是有效的(事实上，c1 可以是 ka 对于任何 0<k<1 )。虽然既然他们在那里，让我们分析一下c1 :

我们需要它来满足以下不等式:

c1*n^2 <= an^2 + bn + c

让我们取它们的值:c1 = a/4 .为了什么n我们能保证不等式成立吗？我们可以解决:

a/4*n^2 <= an^2 + bn + c
<==> 0 <= 3a/4*n^2 + bn + c

二次方程在 (-b +- sqrt(b^2-3ac)) / (3a/2) 处有解，因为我们有一个正的前导系数多项式，所以只有它的正数是有意义的，所以我们需要 n > 2 * (sqrt(b^2-3ac) - b) / 3a这是明确定义假设 b^2 >= 3ac (如果不是，则二次方程是正定的，这更好，因为它处处 >=0 并且不等式对所有 n 都成立)。我应该指出，这是一个有效的解决方案，尽管在我们得出书中的表示之前我们会做更多的工作。

我们可以将分析分为两种情况。首先，我们假设 |b|/a >= sqrt(|c|/a) .所以我们可以从上面绑定(bind)sqrt(...)里面与 4b^2 , 并要求 n > 2/3 * [sqrt(4b^2)-b]/a上限可以是 2/3 * 3|b|/a = 2|b|/a .

第二种情况，我们假设|b|/a < sqrt(|c|/a) .所以我们可以从上面绑定(bind)sqrt(...)里面与 4a|c| , 并要求 n > 2/3 * [sqrt(4a|c|)-b]/a上限可以是 2/3 * 3*sqrt(a|c|)/a = 2sqrt(|c|/a) .

所以在每种情况下，当我们取 max(|b|/a, sqrt(|c|/a)) 时，我们都会看到当 n > 2 * max 时我们的不平等成立

同样适用于 c2 .