Was ist O in Big O?

23

Was ist Big and O in der Big O-Notation? Ich habe die Definitionen gelesen und weiß nicht, was O als "oh" ausgesprochen wird. Zum Beispiel - Ich verstehe, dass O (n) die Komplexität eines linearen Algorithmus ist, wobei n die Anzahl der Operationen sein könnte. aber was ist ein O ?

Karen15
quelle
13
Es ist der 15. Buchstabe des englischen Alphabets. Es ist auch der 15. Buchstabe im griechischen Alphabet.
Joel Etherton
1
Nur zur Verdeutlichung: Sie suchen nach dem Grund, warum O das verwendete Symbol ist (anstelle von Q oder E oder etwas anderem), und welche Bedeutung hat O , wenn überhaupt, gegenüber anderen Symbolen?
FrustratedWithFormsDesigner
6
@Joel: Eigentlich ist es Omicron, und das ist der Anhaltspunkt, warum dieser bestimmte Buchstabe gewählt wurde.
Jörg W Mittag
Diese Antwort widerlegt (meiner Meinung nach richtig) die Omicron-Theorie.
Hawkeye Parker

Antworten:

31

Nun, meine Vermutung wäre Ordnung, was mit Wikipedia übereinstimmt .

Edit: (meine eigene (Verbesserungen erwünscht)) Übersetzung aus dem deutschen Wikipedia-Artikel

Der Großbuchstabe O (eigentlich ein Kapital Omikron zu der Zeit) als Symbol für die Bestellung von (deutsch: „Ordnung von“) wurde erstmals von dem deutschen Zahlentheoretiker Paul Bachman in der zweiten Ausgabe sein Buchs über analytische Zahlentheorie verwendet erschienen Die Notation wurde durch die Arbeit von Edmund Landau, einem anderen deutschen Zahlentheoretiker, populär, mit dem diese Nomenklatur heute vor allem in der deutschen Terminologie häufig in Verbindung gebracht wird.

back2dos
quelle
5
Während es der Fall sein mag, dass viele Mathematiker es als solches bezeichnet haben, war es ursprünglich nicht so. Wenn Sie zahlentheoretische Bücher aus dem frühen 20. Jahrhundert lesen, werden Sie keine solche Erklärung finden. Es ist, was es ist, und ich kann kein Deutsch lesen, um herauszufinden, was er über die Notation gedacht hat.
Jonathan Henson
1
@ Jonathan: Beitrag aktualisiert.
back2dos
Sehr schön! Ich habe in all meinen Büchern zur Zahlentheorie nachgesehen und konnte nirgendwo eine Erklärung für das O finden. +1
Jonathan Henson
2
Ich habe es immer als ausgesprochene Reihenfolge der wie nur sagen , O bedeutet nicht viel.
Newtopian
16

"Groß" bedeutet "Kapital" und "O" bedeutet Ordnung, wie in "Ordnung der Komplexität". So benannt wegen der Konvention, "Reihenfolge der Komplexität" als O (f (x)) zu schreiben, z. B. mit einem Großbuchstaben "O" oder einem "Big O". Niemand spricht viel darüber, weil "jeder" versteht, was es bedeutet, und wenn man es versteht, kann man die Komplexitätsanalyse nicht wirklich verstehen.

Für das Verständnis der Komplexitätsanalyse halte ich den von topgun_ivard geposteten Link für einen guten Ausgangspunkt. Ein gutes Einführungslehrbuch über Datenstrukturen oder Algorithmen könnte ebenfalls hilfreich sein.

Ethel Evans
quelle
5
Es tut mir leid, aber die Bachmann-Landau-Notation wurde von einem deutschen Mathematiker erfunden. Ich glaube kaum, dass er sie nach einem englischen Wort benannt hätte. In der Tat, auch wenn es von einem amerikanischen Mathematiker erfunden worden wäre, wäre es wahrscheinlich noch nach einem deutschen Wort benannt worden ist, weil , wenn es erfunden wurde (um 1920, glaube ich), die internationale Sprache der Mathematik war Deutsch. Außerdem ist es gar nicht der Ferne nichts mit Komplexität zu tun haben.
Jörg W Mittag
1
@ Jörg: Ja, aber wäre das nicht einfach Ordnung , was der deutsche Wiki-Artikel als Ursprung bezeichnet: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
back2dos 13.09.11
1
@Ethel könntest du eine kleine Änderung an deinem Artikel vornehmen, damit ich dich abstimmen kann? Sie sind in der Tat richtig. Sie müssen bearbeiten, bevor ich abstimmen kann.
Jonathan Henson
1
@ Jonathan, ich bin mir nicht sicher, welche kleine Änderung Sie wollen. Können Sie einfach weitermachen und die gewünschte Bearbeitung vornehmen? Oder wir könnten die Antwort von back2dos einfach stehen lassen, es sieht so aus, als ob er aufgrund einer exzellenten Recherche ohnehin die beste Antwort erhalten hätte :)
Ethel Evans
1
Hm, interessant. In Schweden wird Big Oh normalerweise "ordo" (lateinisch für "ordnen") und nicht "ordnen" (schwedisches Wort für "ordnen") genannt.
Vatine
11

O steht für Ordnung.

Es wurde ursprünglich vom deutschen Mathematiker Paul Bachmann im zweiten Band seiner 1894 erschienenen Bücher über Zahlentheorie (S. 401) vorgestellt . Nach einer Formel, in der er zuerst die Notation verwendet, stellt er fest:

(...) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (...)

Meine Übersetzung:

(...) wobei wir mit der Notation O (n) eine Größe angeben, deren Ordnung mit Bezug auf n die Ordnung von n nicht überschreitet (...)

Im Gegensatz zu dem, was andere gesagt haben, deutet nichts in seinem Text darauf hin, dass dies tatsächlich ein Omikron der griechischen Hauptstadt ist. Er verwendet viele griechische und lateinische Schriftzeichen, so dass es eigentlich keine Möglichkeit gibt, dies zu sagen. In Anbetracht seiner fortgesetzten Verwendung von "Ordnung n log n " usw. im Text ist es klar, dass es auf jeden Fall für "Ordnung" steht, aber das könnte die Verwendung von "Ordnung" noch offen lassen ein schicker Grieche O.

Der Ursprung des Omikrons ist jedoch eher ein Retronym von Donald Knuth, der die Symbole Omega (Ω) und Theta (Θ) für verwandte Konzepte in seiner Arbeit Big Omicron und Big Omega und Big Theta oder möglicherweise Hardy und Littlewood who eingeführt hat ein Omega-Symbol früher eingeführt.


quelle
2
Interessant. Ich nehme an, du hast recht. Ich habe gerade die Definitionen in den Büchern von Landau und Bachmann nachgeschlagen, und sie verwenden tatsächlich a) ein lateinisches Oh, kein griechisches Omikron, b) beide verwenden das Wort "Ordnung", und c) Landau gibt ausdrücklich an , dass es "Ordnung" bedeutet. . Ich stehe korrigiert.
Jörg W Mittag
Welches bessere Wort könnte gefunden werden? Ich meine, von einem Deutschen? Ordnung ist das halbe Leben!
JensG
Ich denke, der erste Satz Ihrer (korrekten, überstimmten, ehrfürchtigen) Antwort sollte lauten: "O steht für" Ordnung "." Diese Antwort würde dazu beitragen, die Aufmerksamkeit anderer Leser auf sich zu ziehen.
Hawkeye Parker
5

Ich mag diesen Artikel und hoffe, dass Sie ihn auch nützlich finden!

Zitiert einen Abschnitt aus dem Artikel:
Große griechische Buchstaben

Big O wird oft missbraucht. Big O oder Big Oh ist eigentlich die Abkürzung für Big Omicron. Es repräsentiert die Obergrenze der asymptotischen Komplexität. Wenn also ein Algorithmus O (n log n) ist, existiert eine Konstante c, so dass die obere Grenze cn log n ist.

Θ (n log n) (Big Theta) ist enger gebunden. Ein solcher Algorithmus bedeutet, dass es zwei Konstanten c1 und c2 gibt, so dass c1n log n <f (n) <c2n log n ist.

Ω (n log n) (Big Omega) besagt, dass der Algorithmus eine Untergrenze von cn log n hat.

Es gibt andere, aber diese sind die häufigsten und Big O ist die häufigste von allen. Eine solche Unterscheidung ist normalerweise unwichtig, aber es ist erwähnenswert. Die richtige Notation ist schließlich die richtige Notation.

Was ist Big O?

Die Big-O-Notation versucht, die relative Komplexität eines Algorithmus zu beschreiben, indem die Wachstumsrate auf die Schlüsselfaktoren reduziert wird, wenn der Schlüsselfaktor gegen unendlich tendiert. Aus diesem Grund werden Sie häufig den Ausdruck asymptotische Komplexität hören. Alle anderen Faktoren werden dabei ignoriert. Es ist eine relative Darstellung der Komplexität.

Was ist nicht groß O?

Big O ist kein Leistungstest eines Algorithmus. Es ist auch insofern fiktiv oder abstrakt, als es dazu neigt, andere Faktoren zu ignorieren. Die Komplexität des Sortieralgorithmus wird normalerweise auf die Anzahl der zu sortierenden Elemente als Schlüsselfaktor reduziert. Dies ist in Ordnung, berücksichtigt jedoch nicht Themen wie:

Speichernutzung: Ein Algorithmus benötigt möglicherweise viel mehr Speicher als ein anderer. Abhängig von der Situation kann dies alles von völlig irrelevant bis kritisch sein; Vergleichskosten: Es kann sein, dass das Vergleichen von Elementen sehr kostspielig ist, was potenziell jeden realen Vergleich zwischen Algorithmen verändert. Kosten für das Verschieben von Elementen: Das Kopieren von Elementen ist in der Regel kostengünstig, dies muss jedoch nicht der Fall sein. etc.

topgun_ivard
quelle
5
Das einfache Verknüpfen eines Artikels ist nicht besonders hilfreich. Es ist normalerweise eine gute Idee, den Abschnitt, den Sie für den Thread besonders relevant finden, zu paraphrasieren oder zu zitieren.
Demian Brecht
3
Sind die Abstimmungen wirklich notwendig? Der Artikel, den er verlinkt hat, ist sehr relevant und meiner Meinung nach ziemlich hilfreich. In der Zwischenzeit ist die am häufigsten gewählte Antwort ein Link zu einem Wikipedia-Artikel. +1, um die Heuchelei des Hive-Mind auszugleichen.
Brandon Moretz
1
-1, weil der Artikel zwar ein sehr netter und gut geschriebener Artikel ist, aber nichts mit der Frage zu tun hat.
Jörg W Mittag
@Jorg, ich habe nie gesagt, dass der Artikel das Problem lösen würde, aber ich habe geteilt, weil ich es nützlich gefunden habe, als ich mir diese Konzepte angesehen habe.
topgun_ivard
3
@topgun_ivard: Was passiert also, wenn es zu einem toten Link wird? Paraphrasierung ermöglicht 1) dem Publikum dieses Threads, eine Coles-Notes-Version Ihres Links abzurufen (Zeit ist Geld), und 2) stellt sicher, dass Ihr Beitrag für einen toten Link nicht irrelevant wird.
Demian Brecht,
2

f (x) ist groß-oh von g (x)

Es ist eine mathematische Methode, um das Wachstum von Funktionen vorherzusagen.

Sei f und g Funktionen von der Menge der ganzen Zahlen oder der Menge oder reellen Zahlen bis zur Menge der reellen Zahlen. Wir sagen, dass f (x) O (g (x)) ist, wenn es Konstanten C und k gibt, so dass | f (x) | <= C | g (x) | wo x> k.

Sie würden dies lesen als "f (x) ist groß-oh von g (x)"

Das große O wird manchmal nach dem deutschen Mathematiker Edmund Landau als Landau-Symbol bezeichnet. Ich denke nicht, dass es für etwas anderes steht. Sie haben auch die ähnlichen Big-Omega- und Big-Theta-Notationen. Die Symbole sind so willkürlich wie immer, wenn Sie Theta verwenden, um die Winkel in Ihren Dreiecken zu kennzeichnen, die in Ihrer Klasse für planare Geometrie der Highschool verwendet wurden.

Correction @ back2dos hat eine zufriedenstellende Erklärung für das O in Bezug auf die Bestellung geliefert. Gut gemacht. Siehe seine Antwort.

Donald Knuth wandte es an, um die Komplexität von Computerprogrammen zu untersuchen.

Wenn Sie den Grund für die Verwendung der Notation herausfinden möchten, sollten Sie lesen

"Analytische Zahlentheorie" von Paul Bachmann aus dem Jahr 1892

Jonathan Henson
quelle
2

EDIT: Stellt sich heraus, dass ich falsch liege. Trotzdem hilft dies vielleicht jemandem, seine Symbole gerade zu halten, sodass ich sie nicht löschen werde.


Eigentlich ist es nicht der lateinische Buchstabe Oh , es ist der griechische Buchstabe Omicron . Leider haben diese beiden die exakt gleiche Glyphe, so dass mit der Zeit die Originalversion beschädigt wurde, und jetzt ist es nur noch Oh .

Die Wahl des Symbols hat eigentlich keine besondere Bedeutung, sondern wurde als Gedächtnisstütze gewählt :

  • Omicron enthält die Buchstaben MICRO, und die Semantik des Omicron-Symbols bedeutet ungefähr "kleiner als".
  • Omega enthält die Buchstaben MEGA, und die Semantik des Omega-Symbols bedeutet ungefähr "größer als".
  • Theta (Θ) sieht ein bisschen aus wie ein Gleichheitszeichen, und die Semantik des Theta-Symbols bedeutet ungefähr "gleich".

Das ist es. Es hat keine wirkliche Bedeutung, es ist nur ein Wortspiel, wenn Sie so wollen, damit Sie sich besser an die Semantik erinnern können.

Jörg W Mittag
quelle
2
Ich würde gerne an Ihren Gedächtnisspruch glauben (es ist eine wirklich coole Idee), aber ich werde einen Beweis dafür brauchen, dass dies die eigentliche ursprüngliche Absicht von Bachmann ist. Stellen Sie es zur Verfügung, und ich werde Sie +1.
Jonathan Henson
2
@ Jonathan Henson: Anscheinend wurde ich von Prof. Knuth in die Irre geführt :-)
Jörg W Mittag
-5

UPDATE: Ich versuche, meine Antwort zu bereinigen und genauer zu sein

Die Big-O-Notation ist eine Möglichkeit, Funktionen anhand ihrer Wachstumsraten zu charakterisieren. Das O steht für Ordnung (erste Ordnung ist n zweite Ordnung ist n-Quadrat usw.). Und wenn ich mich nicht irre, wäre dies das Worst-Case-Szenario für eine Methodenlaufzeit (oder -speicherung) mit N Elementen. Je größer die Reihenfolge, desto schlechter die Leistung der Methode.
Zum Beispiel ist das Nachschlagen eines Datensatzes in einem Array O (1) (ich glaube an eine Implementierung von Hash-Tabellen, die auch der Fall ist). Das Hinzufügen eines Werts am Ende einer Linkliste wäre O (N), da Sie erst ans Ende der Liste gelangen müssen, bevor Sie das Element usw. hinzufügen können.

Diese Antwort sollte etwas korrekter sein als mein erster Versuch :)

SoftwareSavant
quelle
2
-1, weil dies einfach nur alt und falsch ist und eine separate Frage beantwortet hat, als sie gestellt wurde. Die Frage war, warum der Buchstabe "O" verwendet wird und nicht "wie funktioniert die Big O-Notation?". Sie sind falsch, was die Funktionsweise von Big-oh angeht. Die Schleife durch ein Array ist O (n), wobei n die Größe des Arrays und nicht O (1) ist. Die Notation hat nichts mit "Zyklen" eines Algorithmus zu tun ... es ist ein Maß für die Obergrenze der Laufzeit eines Algorithmus.
Casey Patton
Ich will hier nicht mit dir streiten, aber so habe ich es gemeint. Was bedeutet Laufzeit richtig? Nun, die Laufzeit hängt davon ab, was auf der Maschine verarbeitet werden muss. Ich denke, ich benutze den Zyklus hier ziemlich großzügig. Nach Zyklus hätte ich wohl sagen sollen, dass ich durchlaufen soll, oder so ähnlich. Sie haben jedoch Recht mit der Obergrenze. Sie bestimmt nicht den Durchschnitt. Deshalb akzeptiere ich das Downgrade.
SoftwareSavant