二次函数的渐近紧束缚

Question

在CLRS(Cormen,Leiserson,Rivest和Stein的算法导论)中,用于函数

˚F(Ñ)= 一个² + BN + Ç

他们说

假设我们取常数c ₁ = a/4,c ₂ = 7 a/4,并且n ₀ = 2·max(| b |/a,√(| c |/a)).
然后0≤ c ^ ₁ ñ ² ≤ 的² + BN + c ^ ≤ c ^ ₂ Ñ ²对于所有Ñ ≥ Ñ ₀.
因此f(n)是Θ(n ²).

但他们没有具体说明这些常数的价值是如何产生的？
我试图证明它但不能.
请告诉我这些常数是怎么来的？

Answer 1

这些特定的常数没有什么特别之处(除了在特定n值的上下文中它们将满足theta-ness 的事实f).没有魔法.如果你能找到其他正常数,那么关系就是有效的(事实上,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的不等式都成立.我应该指出这是一个有效的解决方案,尽管在我们到达本书的代表之前我们会做更多的工作.

我们可以将分析分为2个案例.首先,让我们假设|b|/a >= sqrt(|c|/a).所以我们可以从sqrt(...)with 的内部上方绑定4b^2,并且需要n > 2/3 * [sqrt(4b^2)-b]/a哪个可以在上边界2/3 * 3|b|/a = 2|b|/a.

第二种情况,让我们假设|b|/a < sqrt(|c|/a).所以我们可以从sqrt(...)with 的内部上方绑定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.

Answer 2

这个想法是（对于足够大的n）将感兴趣的函数“捕获”在两个“纯”增长函数（只有一个比例常数）之间。在此图中，两个二次函数（以红色和蓝色绘制）被限制在两个纯增长函数（以黑色绘制）之间，并且指示了每种情况下n _{0的最小可能值。}

\n\n

\n\n

因此，一旦选择了c ₁和c ₂的值，您就可以通过将函数与两个纯增长函数相交并取最右边的交点来找到n ₀的值。

\n\n

但是你不关心n _{0 \xe2\x80\x94 的}最小可能值，我们在这里做渐近，所以任何足够大的值都会做 \xe2\x80\x94 所以你可以使用近似值来得到其上界。

\n\n

请参阅 davin's 答案，了解如何将n ₀的上限转换为 CLRS 中给出的形式。

\n

Answer 3

c1和c2可以任意选择，只要0 < c1 < a和a < c2 < infinity。 n0然后据此计算，使得0 <= c1*n^2 <= an^2 + bn + c <= c2*n^2所有 都满足不等式n>=n0。