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

16

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) / 2 . Welcher Blick darauf scheint intuitiv.

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

Ich bekomme , dass (n 2  + n) / 2 ist ähnlich wie n 2 / 2 , weil Prozentsatz klug, n macht kaum einen Unterschied. Was ich nicht verstehe, ist, warum (n 2  + n) / 2 und n 2 ä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 2 ) . Wenn ich mir diese innere Schleife anschaue, würde ich sagen, dass es n 2 + n / 2 war

Andrew S
quelle
Wenn Sie interessiert sind, hatte ich eine Antwort für drei verschachtelte Schleifen mit Execution Tree Diagram Check gegeben. Ein Puzzle im Zusammenhang mit verschachtelten Schleifen
Grijesh Chauhan
1
Grundsätzlich besteht die Idee darin, dass sich nsowohl die Funktionen 'n ^ 2' als auch Ihre Funktion beim Wachsen ähnlich verhalten, da ihre Wachstumsrate konstant unterschiedlich ist. Wenn Sie einen komplexen Ausdruck haben, dominiert die schneller wachsende Funktion.
AK_
1
@MichaelT: Ich denke nicht, dass dies ein Duplikat dieser Frage ist, da die andere Frage nur eine Frage der Fehlzählung ist. Dies ist eine subtilere Frage, warum die kleineren Terme (insbesondere konstante Multiplikatoren und Polynome niedrigeren Grades) ignoriert werden. Der Fragesteller hier versteht anscheinend bereits die in der anderen Frage aufgeworfene Frage, und eine Antwort, die für diese Frage ausreicht, wird diese Frage nicht beantworten.
Sdenham

Antworten:

38

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).

Bart van Ingen Schenau
quelle
2
Ich mag das, es wird ein bisschen klarer.
Andrew S
7
Das ist sehr handgewellt. Könnte wahr sein oder könnte falsch sein. Wenn Sie ein bisschen Mathe nehmen können, sehen Sie sich eine der folgenden Antworten an.
USR
2
Diese Argumentation ist zu vage: Es würde bedeuten, dass wir daraus schließen könnten O(n * log n) = O(n), was nicht wahr ist.
Vgl.
Es ist vielleicht nicht die präziseste oder semantisch korrekteste Antwort, aber was hier wichtig ist, ist, dass ich damit begonnen habe, den zentralen Punkt zu verstehen, und ich denke, das war das Ziel des Autors. Es ist absichtlich vage, da die Details oft von den Grundprinzipien abweichen können. Es ist wichtig, den Wald vor lauter Bäumen zu sehen.
Andrew S
Bart sprach wirklich von Begriffen, nicht von Faktoren. Wenn wir das verstehen, können wir daraus nicht schließen O(n * log n) = O(n). Ich denke, dies gibt eine gute Erklärung für die Hintergründe der Definition.
Mark Foskey
10

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).

cfh
quelle
4
"Wenn es eine Konstante C> 0 gibt, so dass für alle n gilt" sollte lauten "Wenn es Konstanten C gibt, n_0, so dass für alle n> n_0 gilt"
Taemyr
@Taemyr: Solange die Funktion gungleich Null ist, ist dies eigentlich nicht erforderlich, da Sie die Konstante C immer erhöhen können, um die Aussage für die endlich vielen ersten n_0-Werte wahr zu machen.
Vgl.
Nein, solange wir Funktionen betrachten, gibt es nicht eine endliche Anzahl möglicher n_0-Werte.
Taemyr,
@Taemyr: n_0 ist eine endliche Zahl. Wählen Sie C = max {f (i) / g (i): i = 1, ..., n_0}, und die Anweisung gilt immer für die ersten n_0-Werte, wie Sie leicht überprüfen können.
Vgl.
In CS ist dies weniger bedenklich, da n normalerweise die Eingabegröße ist und daher diskret ist. In diesem Fall kann man C so wählen, dass n_0 = 1 funktioniert. Die formale Definition ist jedoch beliebig größer als ein bestimmter Schwellenwert, wodurch eine ganze Reihe von Fehlwahlen bei der Anwendung der Definition vermieden werden.
Taemyr,
6

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.

Mario
quelle
Wie groß muss n sein, damit die Differenz marginal wird? Und warum wird die / 2 entfernt, ihre Existenz halbiert den Wert?
Andrew S
6
@AndrewS Weil Big O Notation über Wachstum spricht. Das Teilen durch 2 ist außerhalb des Kontexts von Benchmarks und Zeitstempeln irrelevant, da es letztendlich die Wachstumsrate nicht ändert. Die größte Komponente funktioniert jedoch, und das ist alles, was Sie behalten.
Neil
2
@Niel, brillant so klar. Ich wünschte, die Bücher würden es so ausdrücken. Manchmal denke ich, dass die Autoren zu viel wissen, dass sie vergessen, dass bloße Sterbliche nicht über ihr funktionales Wissen verfügen und daher wichtige Punkte nicht klar herausstellen, sondern es in einer formalen mathematischen Beschreibung begraben oder alles zusammen weglassen, indem sie glauben, dass es impliziert ist.
Andrew S
Ich wünschte, ich könnte diese Antwort mehr als einmal positiv bewerten! @Neil, du solltest die Big O-Bücher schreiben.
Tersosauros
3

Es ist nicht so, dass "(n² + n) / 2 sich wie n² verhält, wenn n groß ist", es ist so, dass (n² + n) / 2 wiewä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.

ShadSterling
quelle
Das ist gut, das macht es mir sehr deutlich. Danke für Ihre Antwort.
Andrew S
2

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.

Michael Le Barbier Grünewald
quelle
1
Dieser Wikipedia-Artikel ist nach dem ersten kleinen Stück schwer zu folgen. Es wurde für versierte Mathematiker von versierten Mathematikern geschrieben und ist nicht die Art von Einführungstext, die ich von einem enzyklopädischen Artikel erwarten würde. Vielen Dank für Ihren Einblick, obwohl es alles gut ist.
Andrew S
Sie überschätzen das Niveau im Wikipedia-Text! :) Es ist sicher nicht so gut geschrieben. Graham, Knuth und Patashnik haben ein schönes Buch „Konkrete Mathematik“ für CS-Studenten geschrieben. Sie können auch “The Art of Computer Programming” oder ein in den 50er Jahren geschriebenes Zahlentheorie-Buch (Hardy & Wright, Rose) ausprobieren, da es sich in der Regel an Schüler der Sekundarstufe richtet. Sie müssen nicht das ganze Buch lesen, wenn Sie eines auswählen, sondern nur den Teil über Asymptotik! Aber bevor Sie sich entscheiden müssen, wie viel Sie verstehen müssen. :)
Michael Le Barbier Grünewald
1

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)

Pieter B
quelle
1

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()

Jon Hanna
quelle
"O (n!) Ist dasselbe wie O (1) für ausreichend niedrige Werte von n" ist einfach falsch. Es muss einen besseren Weg geben, um zu erklären, dass " nBig-O keine Rolle spielt , wenn es ausreichend niedrig gehalten wird".
Ben Voigt
@BenVoigt Ich bin noch keinem begegnet, der die gleiche rhetorische Wirkung hatte, als ich ihn zum ersten Mal las. es ist nicht ursprünglich meins, ich habe es von Eric Lippert gestohlen, der es vielleicht von jemand anderem stammt oder genommen hat. Natürlich verweist es auf Witze wie "π ist gleich 3 für kleine Werte von π und große Werte von 3", die noch älter sind.
Jon Hanna
0

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.

Peter ist
quelle
0

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. :)

Jason Walton
quelle