Noch immer verwirrt über die Big-O-Notation
Ich habe also versucht, die Big-O-Notation so gut wie möglich zu verstehen, aber es gibt immer noch einige Dinge, über die ich verwirrt bin. Also lese ich weiter, dass, wenn etwas O (n) ist, es normalerweise sich auf den schlimmsten Fall eines Algorithmus bezieht, aber nicht unbedingt auf den schlimmsten Fall verweist Szenario , weshalb wir sagen können, dass der beste Fall der Einfügesortierung beispielsweise O (n) ist. Ich kann jedoch nicht wirklich verstehen, was das bedeutet. Ich weiß, dass, wenn der Worst-Case-Wert O (n ^ 2) ist, dies bedeutet, dass die Funktion, die den Algorithmus im schlimmsten Fall repräsentiert, nicht schneller als n ^ 2 wächst (es gibt eine obere Grenze). Aber wenn Sie O (n) als den besten Fall haben, wie soll ich das als lesen? Im besten Fall wächst der Algorithmus nicht schneller als n? Was ich mir vorstelle ist ein Graph mit n als obere Grenze, wie
Wenn das Best-Case-Szenario eines Algorithmus O (n) ist, dann ist n die obere Grenze dafür, wie schnell die Operationen des Algorithmus im besten Fall wachsen, so dass sie nicht schneller wachsen können als n ... aber nicht Das heißt, dass genauso schnell wachsen kann wie O (log n) oder O (1), da sie unterhalb der oberen Grenze liegen? Das würde aber keinen Sinn ergeben, weil O (log n) oder O (1) ein besseres Szenario ist als O (n), also wäre O (n) NICHT der beste Fall? Ich bin so verloren lol
3 Antworten
Big-O, Big-∞, Big-Ω sind unabhängig von Worst-Case, Dur-Case und Best-Case.
Die Schreibweise f (n) = O (g (n)) bedeutet, dass f (n) nicht schneller wächst als ein konstantes Vielfaches von g (n) .
Die Schreibweise f (n) = Ω (g (n)) bedeutet, dass f (n) nicht langsamer wächst als ein konstantes Vielfaches von g (n)
Die Schreibweise f (n) = Θ (g (n)) bedeutet, dass beide oben wahr sind.
Beachten Sie, dass f (n) hier die Fall-, Worst-Case- oder "Durchschnitt" -Case-Laufzeit eines Programms mit der Eingabegröße n darstellen kann.
Außerdem kann "Durchschnitt" viele Bedeutungen haben: Es kann die durchschnittliche Eingabe oder die durchschnittliche Eingabegröße ("erwartete" Zeit) oder bedeuten auf lange Sicht (amortisierte Zeit) oder beides oder etwas anderes.
Oft sind Leute an der worst-case Laufzeit eines Programms interessiert, amortisiert sich über die Laufzeit des gesamten Programms (also wenn etwas kostet n anfänglich, kostet aber nur 1 Mal für die nächsten n Elemente, es ergibt sich ein Durchschnitt von 2 pro Element. Die nützlichste Sache, die hier gemessen wird, ist die kleinste Obergrenze in der Worst-Case-Zeit; Wenn Sie also jemanden sehen, der nach dem Big-O eines Programms fragt, ist dies genau das, wonach sie suchen.
Um zu beweisen, dass ein Problem von Natur aus schwierig ist, könnte man versuchen, zu zeigen, dass die worst-case (oder vielleicht durchschnittliche) Laufzeit mindestens ist bestimmter Betrag (z. B. exponentiell).
Sie würden Big-Ω-Notation für diese verwenden, weil Sie nach unteren Grenzen suchen.
Es gibt jedoch keine spezielle Beziehung zwischen Worst-Case und Big-O oder Best-Case und Big-Ω.
Beide können für beide verwendet werden, es ist nur, dass einer von ihnen typischer ist als der andere.
Daher ist die Obergrenze für den besten Fall nicht besonders nützlich. Ja, wenn der Algorithmus immer O (n) Zeit benötigt, dann kann man sagen, dass es sowohl im besten Fall, als auch im Durchschnitt, sowie im schlimmsten Fall O (n) ist. Das ist eine perfekte Aussage, außer der beste Fall ist normalerweise sehr trivial und daher an sich nicht interessant.
Beachte außerdem, dass f (n) = n = O (n 2 ) - das ist technisch korrekt, weil f langsamer wächst als n 2 , aber es ist nicht nützlich , weil es nicht die kleinste obere Grenze ist - es gibt eine sehr offensichtliche obere Grenze, die nützlicher ist als diese, nämlich O (n). Also ja, Sie können gerne sagen, dass die beste / schlechteste / durchschnittliche Laufzeit eines Programms O (n!) Ist. Das ist mathematisch vollkommen korrekt. Es ist einfach nutzlos, denn wenn Leute nach Big-O fragen, sind sie an der Obergrenze am wenigsten interessiert, nicht nur an einer zufälligen Obergrenze.
Es ist auch erwähnenswert, dass es einfach zu wenig sein kann , um die Laufzeit eines Programms als f (n) zu beschreiben. Die Laufzeit hängt oft von der Eingabe selbst ab, nicht nur von ihrer Größe . Zum Beispiel kann es sein, dass even -Auffragen trivial leicht zu beantworten sind, während odd -Abfragen lange brauchen, um zu antworten.
In diesem Fall können Sie f nicht einfach als Funktion von n angeben - dies hängt auch von anderen Variablen ab. Merken Sie sich am Ende, dass dies nur ein Satz mathematischer Werkzeuge ist; Es ist Ihre Aufgabe, herauszufinden, wie Sie es auf Ihr Programm anwenden und herausfinden, was zu messen ist . Nützliche Werkzeuge zu verwenden erfordert etwas Kreativität, und Mathematik ist keine Ausnahme.
Informell gesprochen, bester Fall hat O (n) Komplexität bedeutet, dass wenn die Eingabe trifft bestimmte Bedingungen (d. h. ist am besten für den Algorithmus durchgeführt), dann die Anzahl von Operationen, die in diesem besten Fall ausgeführt werden, sind linear in Bezug auf n (z. B. 1n oder 1,5n oder 5n). Wenn der beste Fall also O (n) ist, bedeutet das normalerweise, dass im besten Fall genau linear ist in Bezug auf n (d. h. asymptotisch nicht kleiner und nicht größer als das) - siehe (1). Na sicher, wenn im besten Fall derselbe Algorithmus maximal c * log N Operationen ausführen kann (wobei c eine Konstante ist), dann wäre die Best-Case-Komplexität dieses Algorithmus informell bezeichnet als O (log N) und nicht als O (N) und die Leute würden sagen, dass es im besten Fall O (log N) ist.
Formal gesprochen ist "die beste Fallkomplexität des Algorithmus O (f (n))" ist eine informelle und falsche Art zu sagen, dass "die Komplexität des Algorithmus ist Ω (f (n)) " (im Sinne der Knuth-Definition - siehe (2)).
Siehe auch:
(1) Wikipedia "Familie von Bachmann-Landau Notationen"
(2) Knuths Papier "Big Omicron and Big Omega und Big Theta"
(3) Big Omega-Notation - was ist f = Ω (g)?
(4) Was ist der Unterschied zwischen Θ (n) und O (n)? / a>
(5) Was ist eine einfache englische Erklärung der "Big O" -Notation?
Ich finde es einfacher, an O() als an Verhältnisse zu denken als an Grenzen. Es ist als Grenzen definiert, und so ist es ein gültiger Weg, darüber nachzudenken, aber es scheint ein bisschen nützlicher zu sein darüber nachzudenken, "wenn ich die Anzahl / Größe der Eingaben für meinen Algorithmus verdopple, verdoppelt sich meine Verarbeitungszeit ( O(n) ), Vierfach ( O(n^2) ), etc ... ". So darüber nachzudenken macht es etwas weniger abstrakt - zumindest für mich ...