Ich bin gerade in die Big-O-Notation eingeführt worden und habe mir einige Fragen gestellt. Ich bin jedoch verwirrt, wie man den Wert von n0 ermittelt.
Ich muss zeigen, dass 3n^3 +20n^2 + 5 O (n ^ 3) ist. Bisher habe ich:
Ich weiß einfach nicht, was ich von hier aus tun soll, um n0 und c zu finden. Würde es jemandem etwas ausmachen zu erklären?
Je nachdem, wo die Größer-Bedingung beginnen soll, können Sie jetzt n0 wählen und den Wert finden.
Zum Beispiel für n0 = 1:
%Vor%Es ist erwähnenswert, dass es bei der Definition der Big-O-Notation nicht erforderlich ist, dass die Grenze tatsächlich so eng ist. Da dies eine einfache Funktion ist, können Sie sie einfach erraten und überprüfen (z. B. 100 für c auswählen und beachten, dass die Bedingung tatsächlich asymptotisch ist).
Zum Beispiel:
%Vor%Diese wahre Wahrheit genügt, um zu beweisen, dass f (n) O (n ^ 3) ist.
Um einen besseren Beweis zu bieten, muss tatsächlich gezeigt werden, dass die beiden Konstanten c und n0 so existieren, dass f(n) <= cg(n) for all n > n0 .
Mit unserem c = 28 ist dies sehr einfach:
%Vor%(Das ist ein ziemlich schlecht gemacht 'Beweis', aber hoffentlich zeigt die Idee.)
Wenn Sie f(n) = (3n^3 + 20n^2 + 5) haben und wollen sehen, ob es O(g(n)) ist, wo g(n) = n^3 , glaube ich, dass Sie das Limit von f(n)/g(n) als n- & gt; unendlich nehmen können.
Da das Limit 3 ist, können Sie sehen, dass 3n^3 + 20n^2 + 5 nur so schnell wächst wie n^3 . Wenn Sie ein Polynom wie 3n^3 + 20n^2 + 5 haben, können Sie durch Inspektion feststellen, dass der größte Ordnungsbegriff immer der Wert von O(f(n)) ist.
Es ist nicht viel Hilfe, n 0 und C zu finden, aber es ist ein relativ einfacher Weg, um zu bestimmen, wie die Ordnung von etwas ist. Wie die anderen hier gesagt haben, können Sie einfach n 0 auswählen und dann C berechnen.
Wenn Sie n 0 = 1 wählen, haben Sie 3*(1^3) + 20*1^2 + 5 = 28 . Also, wenn c1^3 <= 28 , muss c 28 sein. Du hast dort gezeigt, dass es ein c und n0 gibt, die diese Bedingung erfüllen, also hast du bewiesen, dass f (n) O (n ^ 3) ist
Teilen durch n ^ 3 wir bekommen 3 + 20 / n + 5 / n ^ 3 & lt; = C 20 / n + 5 / n ^ 3 & lt; = C-3
Nimm den C-Wert als 10 20 / n + 5 / n ^ 3 & lt; = 7
Wir müssen dies für verschiedene Werte von n lösen, bis die Bedingung erfüllt ist C = 10 und n0 = 3 ergeben die Lösung
Tags und Links big-o