18

CLRS ( Cormen、Leiserson、Rivest、および Stein によるアルゴリズムの紹介) では、関数の

f ( n ) = an 2 + bn + c

彼らは言った

定数c 1 = a /4、c 2 = 7 a /4、およびn 0 = 2·max(| b |/ a , √(| c |/ a )) を取るとします。
次に、すべてのn ≥ n 0に対して 0 ≤ c 1 n 2 ≤ an 2 + bn + c ≤ c 2 n 2です。 したがって、 f ( n ) は Θ ( n 2 ) です。

しかし、彼らはこれらの定数の値がどのように得られたかを特定しませんでした?
証明しようとしましたができませんでした。
これらの定数の由来を教えてください。

4

6 に答える 6

14

これらの特定の定数について特別なことは何もありません (特定のn値のコンテキストで のシータネスを満たすという事実を除いてf)。魔法はありません。関係が保持される他の正の定数を見つけることができれば、それは同じように有効です (実際、任意の に対してc1可能です)。彼らはそこにいるので、分析しましょう：ka0<k<1c1

次の不等式を満たすために必要です。

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、requiren > 2/3 * [sqrt(4b^2)-b]/aで上限をバインドできます2/3 * 3|b|/a = 2|b|/a。

2 番目のケースでは、 と仮定しましょう|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 に答える
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

簡単です 1.c1<=a + b/n + c/n^2 ここで a は >0 ですが、b,c は正または負のいずれかです 次に、b/n + c/n となるように n の値を選択する必要があります^2 は上記の式の RHS で a を超えることはありません。それ以外の場合は負になり、c1 も負になります。ただし、定義により、c1 は正の定数です

したがって、a>b/n+c/n^2 であることを確認します。

n=2*max(|b|/a, sqrt(|c|/a) ) を選択すると、値が a/2+a/ より小さい式として b/n + c/n^2 が得られます。 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) であることを証明するには、2 つの簡単な手順に従います。ステップ 1. f(n) が bigOh(n^m) であることを示す ステップ 2. f(n) が bigOmega(n^m) であることを示す

上記の両方の条件が満たされている場合、f(n) は間違いなく bigTheta(n^m) です。

これは一般化です。m=2 とすると、 f(n) は bigTheta(n^2) となります。

于 2013-11-16T09:37:50.227 に答える