这些特定的常数没有什么特别的(除了在某个n
值的上下文中它们将满足 的 theta的事实f
)。没有魔法。如果您可以找到其他正常数,从而使关系成立,那也同样有效(实际上,c1
可以ka
适用于 any 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)
. 所以我们可以从sqrt(...)
with内部的上方绑定4b^2
,并且 requiren > 2/3 * [sqrt(4b^2)-b]/a
可以在上面绑定2/3 * 3|b|/a = 2|b|/a
。
第二种情况,我们假设|b|/a < sqrt(|c|/a)
。所以我们可以从sqrt(...)
with内部的上方绑定4a|c|
,并且 requiren > 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
。