18

在 CLRS（Cormen、Leiserson、Rivest 和 Stein的算法简介）中，对于一个函数

f ( n ) =一个2 + bn + c

他们说

假设我们采用常数c 1 = a /4、c 2 = 7 a /4 和n 0 = 2·max(| b |/ a , √(| c |/ a ))。
那么 0 ≤ c 1 n 2 ≤ an 2 + bn + c ≤ c 2 n 2对于所有n ≥ n 0。
因此f ( n ) 是 Θ( n 2 )。

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

4

6 回答 6

14

这些特定的常数没有什么特别的（除了在某个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。

于 2011-07-14T15:11:11.360 回答
6

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

在此处输入图像描述

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

但是你并不关心获得n 0的最小可能值——我们在这里做渐近，所以任何足够大的值都可以——所以你可以使用近似值来获得它的上限。

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

于 2011-07-14T14:06:12.460 回答
0

那么它很容易 1.c1<=a + b/n + c/n^2 现在这里 a >0 而 b,c 要么是正的要么是负的 现在我们必须选择 n 的值使得 b/n + c/n ^2 永远不会超过上述方程的 RHS 中的 a，否则它将变为负数，c1 也是如此。但根据定义 c1 是一个正常数

所以我们要确保 a>b/n+c/n^2

如果我们选择 n=2*max(|b|/a, sqrt(|c|/a) ) 我们将得到 b/n + c/n^2 作为表达式，其值小于 a/2+a/ 4.

因此 a+b/n+c/n^2 将具有最大值为 a+a/2+a/4 和最小值为 a-(a/2+a/4) 这只是 c2 和 c1 的值.

c1=aa/2-a/4= a/4 c2=a+a/2+a/4= 7a/4

这个概念可以扩展到任何多项式的任何值。

干杯！！！

于 2015-03-07T18:39:09.057 回答
0

要证明任何多项式 f(n)=a0+a1*n+a2*n^2+a3*n^3+...+am*n^m 是 theta(n^m)，请遵循两个简单的步骤。步骤 1. 证明 f(n) 是 bigOh(n^m) 步骤 2. 证明 f(n) 是 bigOmega(n^m)

如果上述两个条件都成立，那么 f(n) 肯定是 bigTheta(n^m)。

这是一个概括。通过设置 m=2，你得到 f(n) is bigTheta(n^2) 简单..不是吗？

于 2013-11-16T09:37:50.227 回答
0

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

于 2011-07-14T09:06:18.593 回答
0

P(n) = an 2 + bn + c = an 2 ( 1 + b / ( an ) + c / ( an 2 )) = an 2 ( 1 ± ( | b | / a ) / n ± ( √( | c | / a ) / n ) 2
所以如果我们取q = max( | b | / a, √( | c | / a ))比
P(n) ≤ an 2 ( 1 + ( q / n ) + ( q / n ) 2 )如果我们取n 0 = q，我们将得到第二个常数
c 2 = 3a类似地用于下界

于 2017-05-29T15:08:10.577 回答