Begründung für die Vernachlässigung konstanter Faktoren in Big O

Viele Male, wenn die Komplexitäten Konstanten wie 3n haben, vernachlässigen wir diese Konstante und sagen O (n) und nicht O (3n). Ich kann nicht verstehen, wie wir eine solche dreifache Veränderung vernachlässigen können? Manche Dinge variieren dreimal so schnell wie andere! Warum vernachlässigen wir diese Tatsache?

Um zu klären, wie asymptotische Notationen konstante Faktoren ignorieren, stelle ich mir das normalerweise so vor: Asymptotische Komplexität dient nicht zum Vergleichen der Leistung verschiedener Algorithmen, sondern zum Verstehen, wie die Leistung einzelner Algorithmen in Bezug auf die Eingabegröße skaliert.

Zum Beispiel sagen wir, dass eine Funktion, die Schritte dauert, O ( n ) ist , weil bei ausreichend großen Eingaben die Verdoppelung der Eingabegröße nicht mehr als die doppelte Anzahl der Schritte bewirkt. In ähnlicher Weise bedeutet O ( n 2 ) , dass die Verdoppelung der Eingangsgröße die Anzahl der Schritte höchstens vervierfacht, und O ( log n ) bedeutet, dass die Verdoppelung der Eingangsgröße die Anzahl der Schritte um höchstens eine gewisse Konstante erhöht.$3n$$O(n)$$O(n^2)$$O(\log n)$

Mit diesem Tool können Sie feststellen, welche Algorithmen besser skalieren und welche nicht absolut schneller.

Erstens ist, wie andere Antworten bereits erklärt haben, , oder um es in Worten auszudrücken, eine Funktion genau dann O ( 3 n ), wenn sie O ( n ) ist . f = O ( 3 n ) bedeutet , dass ein Punkt existiert N und einem Faktor C 3 so daß für alle n ≥ N , f ( n ) ≤ C 3 ⋅ $O(3n) = O(n)$$O(3n)$$O(n)$$f = O(3n)$$N$$C_3$$n \ge N$ . Nun Pick C 1 = 3 C 3 : für alle n ≥ N , f ( n ) ≤ C 1 ⋅ n , so f = O ( n ) . Der Beweis des Gegenteils ist ähnlich.$f(n) \le C_3 \cdot 3n$$C_1 = 3 C_3$$n \ge N$$f(n) \le C_1 \cdot n$$f = O(n)$

Nun zum Grund, warum dies das richtige Werkzeug ist. Beachten Sie, dass wir keine Einheit angeben, wenn wir die Komplexität eines Algorithmus messen. Wir zählen keine Sekunden oder Maschinenanweisungen: Wir zählen einige nicht spezifizierte elementare Schritte, die jeweils eine begrenzte Zeit in Anspruch nehmen. Wir tun dies, weil die Ausführung desselben Algorithmus auf einer anderen Maschine die pro Befehl benötigte Zeit verändern würde - multiplizieren Sie die Taktfrequenz mit und die Ausführungszeit geht von f ( n ) bis f ( n ) /$3$$f(n)$$f(n)/3$. Wenn wir den gleichen Algorithmus in einer anderen Sprache oder auf einem anderen System implementieren, ist die Zeit, die für jeden Elementarschritt benötigt wird, zwar unterschiedlich, aber auch das ist zu detailliert: Wir kümmern uns kaum um solche Unterschiede.

Wenn Sie sich für präzise Zeitabläufe interessieren, ist die asymptotische Komplexität nicht relevant: Die asymptotische Komplexität gibt an, was bei sehr großen Eingabegrößen passiert, bei denen es sich möglicherweise um die tatsächlichen Eingabegrößen handelt, mit denen Sie es zu tun haben.

Erinnern Sie sich an die Definition von Big-O:

genau dannwenn es existiert , c > 0 , so daß f ( n ) ≤ c g ( n ) für alle n .$f(n)\in O(g(n))$$c>0$$f(n)\le cg(n)$$n$

Nach dieser Definition haben wir für jede Konstante d . Der Zweck der O- Notation besteht genau darin, Ausdrücke auf diese Weise zu vereinfachen. Tatsächlich 3 n wächst 3 - mal so schnell wie$dn\in O(n)$$d$$O$$3n$ , aber beide sind linear. Ob dies gerechtfertigt ist oder nicht, hängt vom Kontext ab. Wenn Sie sich jedoch damit einverstanden erklären, die O- Notation zu verwenden, gilt dies per Definition.$n$$O$

Die Big-O-Notation ist ein einheitenfreies Mittel für die Messung von Leistungsschwankungen und ist daher unempfindlich gegenüber den relativen Kosten von Rechenprimitiven.

Kurz gesagt: Die Big O-Notation ist eine einheitfreie relative Messart (im Gegensatz zur absoluten Messung). Es kann nur Leistungsschwankungen messen, nicht die absolute Leistung, für die Konstanten eine große Rolle spielen. Der Vorteil besteht darin, dass die Implementierung weitgehend unabhängig ist, da eine einfachere Analyse möglich ist, bei der die relativen Kosten elementarer Operationen ignoriert werden können, sofern diese Kosten positive feste Ober- und Untergrenzen haben. Die Konsequenz ist jedoch, dass konstante Faktoren bedeutungslos sind . Die Analyse der asymptotischen Komplexität kann jedoch auch für den beabsichtigten Zweck aus anderen Gründen in Frage gestellt werden und muss sorgfältig abgewogen werden. Beispielsweise ist die unformatierte Eingabegröße möglicherweise nicht der richtige Parameter.

Eine erste Bemerkung ist, dass Ihre Frage nicht ganz richtig gestellt ist. Wenn Sie die Konstante in 3 vernachlässigen$3$, gibt es zwar eine "dreifache Änderung", aber beide variieren mit der gleichen Rate, und Sie können nicht behaupten, dass "[eines] dreimal schneller variiert als das andere".$3n$

Ein guter Grund, die Konstante in der Landau-Notation zu ignorieren, ist, dass wir keine Einheit haben, auf die wir uns verlassen können. Wenn jemand angibt, dass A doppelt so weit von Ihnen entfernt ist wie B, hat dies unabhängig von einer Einheit eine Bedeutung. Wir können uns darauf einigen, obwohl Sie Entfernungen in Zoll messen, während ich das in Lichtjahren mache. Die absolute Entfernungsmessung erfordert jedoch die Angabe von Einheiten, und ihre numerische Formulierung hängt von der gewählten Einheit ab.

Die tatsächliche Zeit, die ein Algorithmus benötigt, hängt von der Ausführungszeit elementarer Operationen ab, die sehr maschinenabhängig ist. Sie könnten die Anzahl der elementaren Operationen zählen, aber es gibt keinen Grund zu der Annahme, dass sie alle dieselbe Zeit benötigen, und es ist immer möglich, mehrere Operationen zu einer einzigen zusammenzufassen oder umgekehrt eine Operation in kleinere zu zerlegen, sodass die Anzahl erhalten bleibt von Operationen ist nicht wirklich sinnvoll, es sei denn, Sie stimmen einer virtuellen Referenzmaschine zu. Referenzunabhängigkeit ist von Vorteil.

Ein weiterer Vorteil des Ansatzes besteht darin, dass Sie in der Analyse nur die Anzahl der Elementaroperationen zählen müssen, sofern deren Kosten eine Obergrenze und eine positive Untergrenze haben. Sie müssen sich nicht um die individuellen Kosten kümmern.

Der zu zahlende Preis für diesen Vorteil ist jedoch, dass die Berechnung mit einer nicht angegebenen Einheit erfolgt und die Berechnungszeit beispielsweise Nanosekunden oder Jahrtausende betragen kann - wir versuchen es nicht einmal zu wissen. Mit anderen Worten, konstante Faktoren sind bedeutungslos, da sich ändernde Einheiten nicht von ändernden konstanten Faktoren trennen lassen und keine Bezugseinheiten verwendet werden.

Wie von Patrick87 bemerkt , reicht dies aus, um zu verstehen, wie ein Algorithmus in Bezug auf die Eingabegröße skaliert, aber es gibt kein absolutes Maß für die Leistung, wenn man sich nicht auf eine Referenzeinheit verlässt. Das Fehlen einer gemeinsamen Referenz-Abstract-Maschine kann durchgeführt werden, wenn die Leistung bestimmter Algorithmen tatsächlich verglichen werden soll, es ist jedoch schwieriger sicherzustellen, dass der Vergleich nicht durch Realisierungsdetails verzerrt wird. In der asymptotischen Komplexität wird dieses Risiko vermieden, weil Sie den Algorithmus mit sich selbst vergleichen.

Wie auch immer, nur ein naiver Programmierer würde sich ausschließlich auf asymptotische Komplexität verlassen, um einen Algorithmus auszuwählen. Es gibt viele andere Kriterien, einschließlich der unermesslichen Konstante und der tatsächlichen Kosten für elementare Operationen. Darüber hinaus kann die Worst-Case-Komplexität ein schlechter Indikator sein, da die Quelle der Worst-Case-Komplexität selten auftritt und bei Fragmenten der Eingabe so klein ist, dass sie eine begrenzte Auswirkung hat. Zum Beispiel haben allgemeine Parser für Grammatiken, die an einen Baum angrenzen , eine theoretische Komplexität und sind in der Praxis durchaus verwendbar. Der schlimmste mir bekannte Fall ist die polymorphe Inferenz nach Damas-Hindley-Milner$O(n^6)$Algorithmus für ML mit exponentieller Worst-Case-Komplexität. Dies scheint jedoch ML-Benutzer nicht zu stören oder das Schreiben sehr großer Programme in ML zu verhindern. Es geht um mehr als die Konstante. Tatsächlich bezieht die asymptotische Analyse ein Maß für die Kosten einer Berechnung auf ein Maß für die Komplexität der Eingabe. Aber die Rohgröße ist möglicherweise nicht das richtige Maß.

Komplexität ist wie Entscheidbarkeit, sie mag theoretisch schlecht sein, aber das mag für den größten Teil des Datenraums irrelevant sein ... manchmal. Die Analyse der asymptotischen Komplexität ist ein gutes und gut gestaltetes Werkzeug, mit seinen Vorteilen und Einschränkungen, wie alle Werkzeuge. Mit oder ohne Erklärung der Konstante, die bedeutungslos sein kann, ist ein Urteil erforderlich.

Die anderen Antworten liefern ausgezeichnete Erklärungen dafür, warum gemäß der Definition von Big-O .$O(n)=O(3n)$

Was den Grund angeht, warum wir dies in CS tun, haben wir eine kompakte Beschreibung der Effizienz eines Algorithmus. Beispielsweise könnte es einen Algorithmus mit einer if-Anweisung geben, bei dem eine Verzweigung Anweisungen und die andere 3 n Anweisungen ausführt . Dies bedeutet, dass sich die genaue Anzahl für jede Eingabe ändert, auch für Eingaben mit derselben Länge. Wir konnten für jede Eingabe eine Zahl finden, aber die Verwendung der Big-O-Notation gibt uns ein Maß für die Zeitkomplexität, die für ALLE Eingaben gilt.$n$$3n$

Dies ist viel nützlicher, um zu erraten, wie schnell ein Algorithmus sein wird. Andernfalls müssten wir uns eine massive stückweise Funktion ansehen, die sehr schwer zu verstehen wäre.

Der andere Hauptgrund ist, dass diese Messungen hardwareunabhängig sind. Verschiedene Compiler und Architekturen wandeln denselben Code in sehr unterschiedliche Befehlssätze um. Wenn wir jedoch wissen, dass die Anzahl der Anweisungen linear, exponentiell usw. ist, haben wir eine Vorstellung von der Geschwindigkeit der Algorithmen, unabhängig davon, auf welchem ​​Computer wir sie kompilieren oder ausführen.

bedeutet lim sup n → ∞ f ( n $f(n)=O(g(n))$$\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$

$g(n)=n$$g(n)=3n$

$O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$. Hier bedeutet die Gleichheit das$f$gehört der LHS wenn es der RHS gehört. Das$=$ Zeichen hier ist ein schwerwiegender Missbrauch der Notation, die ich persönlich hasse, weil es verwirrend ist.

Let me explain you simply. Let us take n = 100000. Now, what is 3n? It is 300000 (Yeah, it is 3 folds of n) But what is n^2 ? 10000000000. ( it is 1 lakh folds of n)..Compare n^2 with n. 3 is negligible when we compare with 1 lakh. so, we can remove it.

Think if n is some billions or trillions. In this case, again we are going to compare 3 with some billions or trillions. Now, you know why we can neglect 3.