Asymptotische enge Schranke für quadratische Funktionen

Question

Im CLRS ( Einführung in Algorithmen von Cormen, Leiserson, Rivest und Stein), für eine Funktion

f ( n ) = eine 2 + bn + c

sie sagten

Angenommen, wir nehmen die Konstanten c ₁ \= a /4, c ₂ \= 7 a /4, und n ₀ \= 2-max(| b |/ a , (| c |/ a )).
Dann 0 c ₁ n 2 eine 2 + bn + c c ₂ n 2 für alle n n ₀ .
Deshalb f ( n ) ist ( n 2 ).

Aber sie haben nicht angegeben, wie die Werte dieser Konstanten zustande gekommen sind ?
Ich habe versucht, es zu beweisen, konnte es aber nicht.
Bitte sagen Sie mir, wie diese Konstanten entstanden sind?

Answer 1

Es gibt nichts Besonderes an diesen speziellen Konstanten (außer der Tatsache, dass sie im Zusammenhang mit einer bestimmten n Wert erfüllen sie die Theta-Eigenschaft von f ). Keine Magie. Wenn Sie andere positive Konstanten finden können, bei denen die Beziehung hält, ist das genauso gültig (in der Tat, c1 kann sein ka für jede 0<k<1 ). Aber wenn sie schon mal da sind, lassen Sie uns analysieren c1 :

Sie muss die folgende Ungleichung erfüllen:

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

Nehmen wir ihren Wert: c1 = a/4 . Für was n Können wir garantieren, dass die Ungleichung gilt? Wir könnten lösen:

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

Die Quadratische hat Lösungen bei (-b +- sqrt(b^2-3ac)) / (3a/2) , von dem nur das Positive von Interesse ist, da wir ein Polynom mit positivem Leitkoeffizienten haben, so dass wir n > 2 * (sqrt(b^2-3ac) - b) / 3a die gut definiert ist, wenn man annimmt b^2 >= 3ac (und wenn nicht, dann ist die quadratische Funktion positiv definit, was noch besser ist, da sie überall >=0 ist und die Ungleichung für alle n gilt). Ich sollte darauf hinweisen, dass dies eine gültige Lösung ist, auch wenn wir noch ein wenig arbeiten müssen, bis wir die Darstellung aus dem Buch haben.

Wir können unsere Analyse in 2 Fälle aufteilen. Erstens, nehmen wir an |b|/a >= sqrt(|c|/a) . So können wir von oben die Innenseite des sqrt(...) con 4b^2 und erfordern n > 2/3 * [sqrt(4b^2)-b]/a die nach oben begrenzt werden kann durch 2/3 * 3|b|/a = 2|b|/a .

Zweiter Fall, nehmen wir an |b|/a < sqrt(|c|/a) . So können wir von oben die Innenseite des sqrt(...) con 4a|c| und erfordern n > 2/3 * [sqrt(4a|c|)-b]/a die nach oben begrenzt werden kann durch 2/3 * 3*sqrt(a|c|)/a = 2sqrt(|c|/a) .

Wir sehen also in jedem Fall, dass wir, wenn wir die max(|b|/a, sqrt(|c|/a)) unsere Ungleichung gilt, wenn n > 2 * max

Ähnliches gilt für c2 .

Answer 2

Die Idee ist, (für ausreichend große n ) die interessierende Funktion zwischen zwei "reinen" Wachstumsfunktionen (die nur eine einzige Proportionalitätskonstante haben) "einklemmen". In dieser Abbildung sind zwei quadratische Funktionen (rot und blau gezeichnet) zwischen zwei reinen Wachstumsfunktionen (schwarz gezeichnet) gefangen, und der kleinstmögliche Wert von n ₀ ist jeweils angegeben.

Sobald Sie also Ihre Werte ausgewählt haben c ₁ y c ₂ können Sie den Wert von n ₀ indem Sie Ihre Funktion mit den beiden reinen Wachstumsfunktionen schneiden und den Schnittpunkt ganz rechts nehmen.

Aber es ist Ihnen egal, was Sie bekommen. kleinstmöglich Wert für n ₀ - Da es sich hier um Asymptotik handelt, ist jeder Wert, der groß genug ist, ausreichend - Sie können also Näherungswerte verwenden, um eine obere Grenze zu erhalten.

Siehe die Antwort von Davin, wie man die obere Grenze für n ₀ in die in CLRS angegebene Form zu bringen.

Answer 3

Nun, es ist ganz einfach 1.c1<=a + b/n + c/n^2 Hier ist a >0, während b und c entweder positiv oder negativ sind. Jetzt müssen wir den Wert von n so wählen, dass b/n + c/n^2 niemals a in RHS der obigen Gleichung übersteigt, weil es sonst negativ wird und c1 auch. aber per Definition ist c1 eine positive Konstante

Wir wollen also sicherstellen, dass a>b/n+c/n^2

wenn wir n=2*max(|b|/a, sqrt(|c|/a) ) wählen erhalten wir b/n + c/n^2 als einen Ausdruck, dessen Wert kleiner als a/2+a/4 ist.

Somit hat a+b/n+c/n^2 den Maximalwert a+a/2+a/4 und den Minimalwert a-(a/2+a/4), was nichts anderes als die Werte von c2 und c1 ist.

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

Dieses Konzept kann auf beliebige Werte für beliebige Polynome ausgedehnt werden.

Prost!!!

Answer 4

c1 y c2 willkürlich gewählt werden kann, solange 0 < c1 < a y a < c2 < infinity . n0 berechnet, so dass die Ungleichung 0 <= c1*n^2 <= an^2 + bn + c <= c2*n^2 ist erfüllt für alle n>=n0 .

Answer 5

Um zu beweisen, dass ein beliebiges Polynom f(n)=a0+a1*n+a2*n^2+a3*n^3+...+am*n^m theta(n^m) ist, sind zwei einfache Schritte erforderlich. Schritt 1. zeige, dass f(n) bigOh(n^m) ist Schritt 2. zeige, dass f(n) bigOmega(n^m) ist

Wenn die beiden oben genannten Bedingungen zutreffen, dann ist f(n) definitiv bigTheta(n^m).

Dies ist eine Verallgemeinerung. Wenn man m=2 setzt, erhält man f(n) ist bigTheta(n^2) Einfach, nicht wahr?