Ich habe festgestellt, dass Big-O von 1000n oder 10n ist das gleiche wie O (n), aber Big-O von 2^n und 3^n sind verschieden: O (2^n) und O (3^n), was ich nicht verstehe, warum können wir die Konstanten in diesem Fall (2 oder 3) nicht ignorieren und ob es einen mathematischen Beweis gibt, der dies rechtfertigt?Große O Notation der Exponentialfunktionen
Weil es keinen konstanten Wert von k gibt, der die Ungleichheit 3^n <= k * 2^n für beliebig große n erfüllt. Somit ist f(n) = 3^n kein Mitglied von O(2^n).
Siehe http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations.
Um genau zu sein, zeigen Sie ein Gegenbeispiel zu der Behauptung: O (3^n) = O (2^n). Insbesondere ist "f (n) = 3^n" in "O (3^n)", aber nicht in "O (2^n)" mit dem Argument, das Sie oben angegeben haben. Daher sind die Mengen nicht über das Axiom der Erweiterbarkeit – rliu
@ roliu: Ich weiß nicht, was das Axiom ist, aber ja, das ist das implizierte Argument;) –
Es ist ein Axiom in der beliebtesten Mengenlehre, ZFC: https://de.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory. Es sagt nur "zwei Sätze sind gleich, wenn sie die gleichen Elemente enthalten". Niemand zitiert es jemals in einem echten Beweis, aber ich versuche nur, SO davon zu überzeugen, tatsächliche mathematische Argumentation anstelle von Intuition zu verwenden (indem es mit mathematischem Jargon extrem ausführlich ist). Wenn Sie nur versuchen, die zu verwendende Implementierung zu bestimmen, während Sie Code schreiben, können Sie Intuition verwenden. Wenn jemand sagt "beweis das", dann denke ich, dass du, weißt du, Mathe verwenden solltest :) – rliu
Eventhough für den ursprünglichen Asker könnte dies nicht mehr nützlich sein,
Ich denke, es kann einfacher angegangen werden.
Grund defenition von O-Notation: iff f (g) in O (g (n)) sein würde,
dann eine rationale Zahl c existieren, für die es f (g) = c gilt, daß * g (n), für n> = n0
(N0 eine Zahl, die Sie selbst wählen)
Lassen Sie uns versuchen, dies in O 3^n anzuwenden (2^n)
3^n = 2^n * c
3^n = 2^n * (3^n/2^n)
3^n = 2^n * (3/2)^n
3^n = 2^n^n * 1,5
Dies bedeutet, dass c = 1,5^n, der nicht rational ist Nummer, sondern eine exponentielle Funktion für sich.
Auf der anderen Seite, nach dem gleichen 3^n in O (2^n), würden wir n < = 3^n * erhalten 2^(2/3)^n
Diese könnte wie ein Konflikt erscheinen, bis Sie erkennen, dass 0,75^n < 1 für alle n> 0, was bedeutet, dass, wenn Sie eine c> 1 nehmen, wird es größer als 0 sein.67^n von n = 0
um zwei Komplexitäten zusammenzufassen, f (n) und g (n) hast du das Limit angewendet: lim_ {n -> \ inf} f (n)/g (n) und du habe drei mögliche Antworten:
1) lim_ {n -> \ inf} f (n)/g (n) = 0; Dies impliziert, dass f (n) ∈ 0 (g (n)) und g (n) ∉ 0 (f (n))
2) lim_ {n -> \ inf} f (n)/g (n) = +/- inf; Dies impliziert, dass f (n) ∉ O (g (n)) und g (n) ∈ O (f (n))
3) lim_ {n -> \ inf} f (n)/g (n) ∈ Reelle Zahl; Dies impliziert, dass f (n) ∈ O (g (n)) und g (n) ∈ 0 (f (n))
Dann zu demostrade 2^n ∈ O (3^n) Sie so arbeiten
lim_ {n -> \ inf} 2^n/3^n = lim_ {n -> \ inf} (2/3)^n = 0
und ist demostrated, und wir demostraded auch 3^n ∉ O (2^n), und es ist leicht zu sehen, dass dies die Grenze für die Konvergenz auf 0 bildet, dann hängt das Ergebnis der Grenze von den Konstanten ab, ich meine lim_ {n-> inf} a^n = 0 wenn 0 < a < 1 und lim_ {n-> inf} a^n = inf wenn a> 1;
Zum besseren Verständnis Prüfung: Introduction to Algorithms, dritte Auflage Von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein
Ich bin Professor für Algorithmen, ich hoffe, es half Sie. Pass auf.
Sie ignorieren Konstanten nicht in der Groß-O-Notation. Sie ignorieren Koeffizienten. 2 und 3 sind Basen, keine Koeffizienten. – kqr
Können Sie die Definition von Big-Oh angeben? Denken Sie daran, dass Big-Oh eine mathematische Definition hat und nicht vollständig intuitiv verwendet werden sollte. Sich zu merken, dass "man manchmal Konstanten ignorieren kann" ist meiner Meinung nach eine schlechte Angewohnheit. – rliu