Big O Frage zu einem Algorithmus mit (n ^ 2 + n) / 2 Wachstumsrate

Ich stelle diese Frage, weil ich über einen Aspekt in Bezug auf die Big-O-Notation verwirrt bin.

Ich benutze das Buch, Datenstrukturen und Abstraktionen mit Java von Frank Carrano. Im Kapitel "Effizienz von Algorithmen" zeigt er den folgenden Algorithmus:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

Er beschreibt diesen Algorithmus zunächst mit einer Wachstumsrate von ^{(n 2  + n)} / ₂ . Welcher Blick darauf scheint intuitiv.

Es wird jedoch dann angegeben, dass ^{(n 2  + n)} / ₂ sich wie n ² verhält, wenn n groß ist. Im gleichen Absatz sagt er ^{(n 2  + n)} / ₂ verhält sich auch ähnlich wie ^{n 2} / ₂ . Er benutzt dies, um den obigen Algorithmus als O (n ² ) zu klassifizieren .

Ich bekomme , dass ^{(n 2  + n)} / ₂ ist ähnlich wie ^{n 2} / ₂ , weil Prozentsatz klug, n macht kaum einen Unterschied. Was ich nicht verstehe, ist, warum ^{(n 2  + n)} / ₂ und n ² ähnlich sind, wenn n groß ist.

Zum Beispiel, wenn n = 1.000.000 :

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

Das letzte ist überhaupt nicht ähnlich. Tatsächlich ist es ganz offensichtlich doppelt so viel wie das mittlere. Wie kann Frank Carrano sagen, dass sie ähnlich sind? Auch, wie ist der Algorithmus wie folgt eingestuft O (n ² ) . Wenn ich mir diese innere Schleife anschaue, würde ich sagen, dass es n ² + ⁿ / _{2 war}

Bei der Berechnung der Big-O-Komplexität eines Algorithmus wird der Faktor angezeigt, der den größten Beitrag zur Erhöhung der Ausführungszeit leistet, wenn die Anzahl der Elemente, über die Sie den Algorithmus ausführen, zunimmt.

Wenn Sie einen Algorithmus mit einer Komplexität von haben (n^2 + n)/2 und die Anzahl der Elemente verdoppeln, hat die Konstante 2keinen Einfluss auf die Erhöhung der Ausführungszeit, der Term nbewirkt eine Verdoppelung der Ausführungszeit und der Term n^2bewirkt eine Vervierfachung der Ausführungszeit Zeit.
Da der n^2Begriff den größten Anteil hat, ist die Big-O-Komplexität O(n^2).

Die Definition ist das

f(n) = O(g(n))

wenn es eine Konstante C> 0 gibt, so dass wir für alle n größer als einige n_0 haben

|f(n)| <= C * |g(n)|

Dies gilt eindeutig für f (n) = n ^ 2 und g (n) = 1/2 n ^ 2, wobei die Konstante C 2 sein sollte. Es ist auch leicht zu erkennen, dass dies für f (n) = n ^ gilt 2 und g (n) = 1/2 (n ^ 2 + n).

Wenn Sie über Komplexität sprechen, interessieren Sie sich nur für die Zeitfaktoränderungen basierend auf der Anzahl der Elemente ( n).

Als solches können Sie jeden konstanten Faktor (wie den 2hier) entfernen .

Das lässt dich mit O(n^2 + n).

Nun, für eine vernünftige Größe ist ndas Produkt n * nbedeutend größer als nur n, was der Grund ist, warum Sie auch diesen Teil überspringen dürfen, was Ihnen in der Tat eine endgültige Komplexität von hinterlässtO(n^2) .

Es ist wahr, für kleine Zahlen wird es einen signifikanten Unterschied geben, aber dieser wird geringfügiger, je größer Sie nwerden.

Es ist nicht so, dass "(n² + n) / 2 sich wie n² verhält, wenn n groß ist", es ist so, dass (n² + n) / 2 wie n² wächst, wenn n zunimmt .

Zum Beispiel, wenn n von 1.000 auf 1.000.000 ansteigt

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Ebenso steigt n von 1.000.000 auf 1.000.000.000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Sie wachsen ähnlich, worum es bei Big O Notation geht.

Wenn Sie (n² + n) / 2 und n² / 2 auf Wolfram Alpha zeichnen, sind sie so ähnlich, dass sie nur schwer durch n = 100 zu unterscheiden sind. Wenn Sie alle drei auf Wolfram Alpha zeichnen , sehen Sie zwei durch einen konstanten Faktor von 2 getrennte Linien.

Es sieht nur so aus, als müssten Sie die große O- Notation ein bisschen weiter ausarbeiten . Wie bequem diese Notation ist, ist sehr irreführend, da ein Gleichheitszeichen verwendet wird, das hier nicht zur Bezeichnung der Gleichheit von Funktionen verwendet wird.

Wie Sie wissen, drückt diese Notation einen asymptotischen Vergleich von Funktionen aus. Wenn Sie f = O (g) schreiben, bedeutet dies, dass f (n) höchstens so schnell wächst wie g (n), wenn n gegen unendlich geht. Ein einfacher Weg, dies zu übersetzen, ist zu sagen, dass die Funktion f / g begrenzt ist. Aber natürlich müssen wir uns um die Stellen kümmern, an denen g Null ist, und am Ende haben wir die robustere Definition, die Sie fast überall lesen können .

Diese Notation erweist sich als sehr praktisch für das Rechnen - aus diesem Grund ist sie so weit verbreitet -, sollte aber mit Vorsicht behandelt werden, da das Gleichheitszeichen, das wir dort sehen, keine Gleichheit der Funktionen bedeutet . Dies ist so ziemlich so, als würde man sagen, dass 2 = 5 mod 3 nicht 2 = 5 impliziert, und wenn Sie sich für Algebra interessieren, können Sie die große O-Notation tatsächlich als ein Gleichheitsmodul verstehen.

Nun, um auf Ihre spezifische Frage zurückzukommen, es ist völlig sinnlos, einige numerische Werte zu berechnen und zu vergleichen: So groß eine Million auch sein mag, es erklärt kein asymptotisches Verhalten. Es wäre sinnvoller, das Verhältnis der Funktionen f (n) = n (n-1) / 2 und g (n) = n² zu zeichnen - aber in diesem speziellen Fall können wir leicht sehen, dass f (n) / g (n) ist kleiner als 1/2, wenn n> 0, was impliziert, dass f = O (g) ist .

Um die Notation besser zu verstehen, sollten Sie

• Arbeiten Sie mit einer klaren Definition, nicht mit einem unscharfen Eindruck, der auf ähnlichen Dingen basiert - wie Sie es gerade erlebt haben, funktioniert ein derartiger unscharfer Eindruck nicht gut.

• Nehmen Sie sich etwas Zeit, um Beispiele im Detail auszuarbeiten. Wenn Sie innerhalb einer Woche nur fünf Beispiele erarbeiten, reicht dies aus, um Ihr Selbstvertrauen zu stärken. Dies ist eine Anstrengung, die sich auf jeden Fall lohnt.

Algebraische Randnotiz Ist A die Algebra aller Funktionen Ν → Ν und C die Subalgebra der begrenzten Funktionen, so ist bei gegebener Funktion f die Menge der zu O (f) gehörenden Funktionen ein C- Submodul von A und Berechnungsregeln auf der großen O-Notation beschreibt nur, wie A auf diesen Submodulen arbeitet. Die Gleichheit, die wir sehen, ist also eine Gleichheit der C- Submodule von A , dies ist nur eine andere Art von Modul.

Ich denke, Sie verstehen falsch, was die große O-Notation bedeutet.

Wenn Sie O (N ^ 2) sehen, bedeutet dies im Grunde: Wenn das Problem 10-mal so groß wird, ist die Zeit zur Lösung: 10 ^ 2 = 100-mal so groß.

Geben Sie 1000 und 10000 in Ihre Gleichung ein: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Während also das N 10-mal so groß wurde, wurden die Lösungen 100-mal so groß. Daher verhält es sich: O (N ^ 2)

wenn n ein 1,000,000dann war

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 was?

Die Komplexität gibt uns die Möglichkeit, die tatsächlichen Kosten vorherzusagen (Sekunden oder Bytes, je nachdem, ob es sich um Zeit- oder Raumkomplexität handelt), es gibt uns jedoch keine Anzahl von Sekunden oder eine andere bestimmte Einheit.

Es gibt uns einen gewissen Grad an Proportionen.

Wenn ein Algorithmus n²-mal etwas tun muss, dauert es n² × c für einen Wert von c, der so lang ist, wie jede Iteration dauert.

Wenn ein Algorithmus n² ÷ 2 Mal ausführen muss, benötigt er n² × c für einen Wert von c, der doppelt so lang ist wie jede Iteration.

In beiden Fällen ist die benötigte Zeit immer noch proportional zu n².

Diese konstanten Faktoren können wir nicht einfach ignorieren. In der Tat kann es vorkommen, dass ein Algorithmus mit O (n²) -Komplexität besser abschneidet als einer mit O (n) -Komplexität, denn wenn wir an einer kleinen Anzahl von Elementen arbeiten, ist die Auswirkung der konsistenten Faktoren größer und kann andere Bedenken überwältigen . (Tatsächlich ist sogar O (n!) Dasselbe wie O (1) für ausreichend niedrige Werte von n).

Aber sie sind nicht das, worüber uns Komplexität erzählt.

In der Praxis gibt es verschiedene Möglichkeiten, die Leistung eines Algorithmus zu verbessern:

1. Verbessern Sie die Effizienz jeder Iteration: O (n²) läuft immer noch in n² × c Sekunden, aber c ist kleiner.
2. Reduzieren Sie die Anzahl der beobachteten Fälle: O (n²) läuft immer noch in n² × c Sekunden, aber n ist kleiner.
3. Ersetzen Sie den Algorithmus durch einen Algorithmus mit den gleichen Ergebnissen, aber geringerer Komplexität: Wenn wir beispielsweise etwas O (n²) in etwas O (n log n) umwandeln und daher von n² × c₀ Sekunden in (n log n) × c₁ Sekunden ändern könnten .

Oder anders ausgedrückt, es werden f(n)×cSekunden benötigt, und Sie können die Leistung verbessern c, indem Sie ndie fRenditen für eine bestimmte Leistung reduzieren , reduzieren oder reduzieren n.

Das erste können wir durch ein paar Mikro-Opts innerhalb einer Schleife oder mit besserer Hardware machen. Es wird immer eine Verbesserung geben.

Das zweite können wir tun, indem wir vielleicht einen Fall identifizieren, in dem wir den Algorithmus kurzschließen können, bevor alles untersucht wird, oder einige Daten herausfiltern, die nicht von Bedeutung sind. Es wird keine Verbesserung geben, wenn die Kosten dafür den Gewinn überwiegen, aber es wird im Allgemeinen eine größere Verbesserung sein als im ersten Fall, insbesondere mit einem großen n.

Das dritte können wir tun, indem wir einen völlig anderen Algorithmus verwenden. Ein klassisches Beispiel wäre das Ersetzen einer Blasensorte durch eine Quicksorte. Mit einer geringen Anzahl von Elementen haben wir möglicherweise die Situation verschlechtert (wenn c & sub1; größer als c & sub0; ist), aber dies ermöglicht im allgemeinen die größten Gewinne, insbesondere mit sehr großem n.

In der Praxis ermöglichen es Komplexitätsmessungen, die Unterschiede zwischen den Algorithmen genau zu beurteilen, da sie die Frage ignorieren, wie die Reduzierung von n oder c helfen wird, um sich auf die Untersuchung zu konzentrieren f()

Konstanter Faktor

Der Punkt der großen O-Notation ist, dass Sie einen beliebig großen konstanten Faktor wählen können, so dass O (Funktion (n)) immer größer als C * -Funktion (n) ist. Wenn Algorithmus A eine Milliarde Mal langsamer als Algorithmus B ist, haben sie dieselbe Komplexität, solange diese Differenz nicht wächst, wenn n willkürlich groß wird.

Nehmen wir einen konstanten Faktor von 1000000 an, um das Konzept zu veranschaulichen - es ist eine Million Mal größer als erforderlich, aber das zeigt, dass sie als irrelevant angesehen werden.

(n ^ 2 + n) / 2 "passt in" O (n ^ 2), weil für jedes n, egal wie groß, (n ^ 2 + n) / 2 <1000000 * n ^ 2.

(n ^ 2 + n) / 2 "passt" nicht zu einer kleineren Menge, zB O (n), weil für einige Werte (n ^ 2 + n) / 2> 1000000 * n.

Die konstanten Faktoren können beliebig groß sein - ein Algorithmus mit einer Laufzeit von n Jahren hat eine O (n) -Komplexität, die "besser" ist als ein Algorithmus mit einer Laufzeit von n * log (n) Mikrosekunden.

Bei Big-O geht es darum, wie kompliziert ein Algorithmus ist. Wenn Sie über zwei Algorithmen verfügen und einer n^2*kSekunden und der andere n^2*jSekunden benötigt, können Sie darüber streiten, welcher Algorithmus besser ist, und Sie können möglicherweise einige interessante Optimierungen vornehmen, um zu versuchen, koder j, aber beide , zu beeinflussen Diese Algorithmen sind im Vergleich zu einem Algorithmus, der n*mzum Ausführen benötigt wird , absolut langsam . Es spielt keine Rolle, wie klein Sie die Konstanten machen, koder jbei einer ausreichend großen Eingabe n*mgewinnt der Algorithmus immer, auch wenn er mziemlich groß ist.

Also nennen wir die ersten beiden Algorithmen O(n^2)und wir nennen die zweite O(n). Es unterteilt die Welt in Klassen von Algorithmen. Darum geht es bei big-O. Es ist, als würde man Fahrzeuge in Autos und Lastwagen und Busse usw. aufteilen. Es gibt viele Unterschiede zwischen den Autos, und Sie können den ganzen Tag darüber streiten, ob ein Prius besser ist als ein Chevy Volt, aber am Ende des Tages, wenn Sie Müssen 12 Personen in eine eingesetzt werden, dann ist dies ein eher sinnloses Argument. :)