Was ist O in Big O?

Nun, meine Vermutung wäre Reihenfolge, die mit Wikipedia übereinstimmt.

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

Der Großbuchstabe O (damals eigentlich ein Großbuchstabe) als Symbol für die Ordnung von (deutsch: „Ordnung von“) wurde erstmals von verwendet Der deutsche Zahlentheoretiker Paul Bachman erschien 1894 in der zweiten Ausgabe seines Buches über analytische Zahlentheorie. Die Notation gewann aufgrund der Arbeit von Edmund Landau, einem anderen deutschen Zahlentheoretiker, mit dem diese Nomenklatur heute, insbesondere in der Deutsche Terminologie.

Kommentare

• Möglicherweise haben sich viele Mathematiker darauf bezogen es als solches war es ursprünglich nicht so. Wenn Sie Bücher zur Zahlentheorie 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: Post aktualisiert.
• 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
• Ich ‚ habe es immer als Reihenfolge von ausgesprochen, da nur O nicht viel bedeutet.

ehr informativ! aber immer noch – Warum wird O von Programmierern als ‚ oh ‚ ausgesprochen?

„Big“ bedeutet „Kapital“ und „O“ bedeutet Ordnung, wie in „Reihenfolge 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 „großen O“. Niemand spricht viel darüber, weil „jeder“ versteht, was es bedeutet, und das Verständnis hilft Ihnen nicht wirklich, die Komplexitätsanalyse zu verstehen.

Für ein Verständnis der Komplexitätsanalyse denke ich, dass der von topgun_ivard gepostete Link ein ist Ein guter Einstieg. Ein gutes Einführungslehrbuch über Datenstrukturen oder Algorithmen könnte ebenfalls hilfreich sein.

Kommentare

• I ‚ Es tut mir leid, aber die Bachmann-Landau-Notation wurde von einem deutschen Mathematiker erfunden, daher glaube ich kaum, dass er sie nach einem englischen Wort benannt hätte. Tatsächlich, selbst wenn sie von erfunden worden wäre Als amerikanischer Mathematiker wäre es wahrscheinlich immer noch nach einem deutschen Wort benannt worden, denn als es erfunden wurde (glaube ich um 1920), war die internationale Sprache der Mathematik Deutsch. Außerdem ist es nicht ‚ nicht einmal aus der Ferne hat etwas mit Komplexität zu tun.
• @J ö rg: Ja, aber nicht ‚ Das ist nur Ordnung , von der der deutsche Wiki-Artikel behauptet, sie sei der Ursprung: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel Könnten Sie Ihren Artikel geringfügig ändern, damit ich Sie abstimmen kann? Sie sind in der Tat richtig. Sie müssen bearbeiten, bevor ich abstimmen kann.
• @Jonathan, ich ‚ bin mir nicht sicher, welche geringfügige Änderung Sie möchten. Können Sie einfach die gewünschte Bearbeitung vornehmen? Oder wir könnten einfach back2dos ‚ antworten lassen, es sieht so aus, als hätte er aufgrund exzellenter Recherchen ohnehin die beste Antwort erhalten 🙂
• Hm interessant. In Schweden wird Big Oh normalerweise als “ ordo “ (lateinisch für Ordnung) und nicht als ordning “ (das schwedische Wort für Bestellung).

O steht für order.

Es wurde ursprünglich vom deutschen Mathematiker Paul Bachmann in dem zweiten Band seiner Bücher zur Zahlentheorie Die Analytische Zahlentheorie eingeführt. veröffentlicht 1894 (S. 401) . 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, ihre Ordnung in Bezug auf n die Ordnung von n nicht entschiedenem (…)

Meine Übersetzung:

(…) wobei mit der Notation O (n) wir Geben Sie eine Größe an, deren Reihenfolge in Bezug auf n die Reihenfolge von n (…)

Im Gegensatz zu dem, was andere gesagt haben, deutet nichts in seinem Text darauf hin, dass es sich tatsächlich um ein griechisches Hauptstadt-Omikron handelt. Er verwendet viele griechische und lateinische Schriftzeichen, daher gibt es keine Möglichkeit, dies zu beurteilen. Angesichts seiner fortgesetzten Verwendung von „Ordnung n log n “ usw. im Text ist klar, dass dies der Fall ist steht auf jeden Fall für „Ordnung“ (deutsch für „Ordnung“, wenn es irgendwelche Zweifel gab), aber das könnte immer noch die Verwendung eines ausgefallenen griechischen O offen lassen.

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 einführte oder möglicherweise Hardy und Littlewood , die zuvor ein Omega-Symbol eingeführt haben.

Kommentare

• Interessant. Ich nehme an, du hast recht. Ich habe gerade die Definitionen in den Büchern von Landau ‚ s und Bachmann ‚ nachgeschlagen, und sie verwenden tatsächlich a) ein lateinisches Oh, nicht ein griechischer Omikron, b) beide verwenden das Wort “ Ordnung „, und c) Landau gibt dies ausdrücklich an es bedeutet “ Ordnung „. Ich stehe korrigiert da.
• Welches bessere Wort könnte gefunden werden? Ich meine, von einem Deutschen? Ordnung ist das halbe Leben!
• Ich denke, der erste Satz Ihrer (richtigen, optimierten, großartigen) Antwort sollte lauten: ‚ O steht für “ Ordnung “ (deutsche Bedeutung “ Bestellung „) ‚ Es würde dieser Antwort helfen, die Aufmerksamkeit anderer Leser zu erregen.

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

Zitieren eines Abschnitts 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 Obergrenze cn log n ist.

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

Ω (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 allen gemeinsam. 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 den Schlüssel reduziert wird Faktoren, wenn der Schlüsselfaktor gegen unendlich tendiert. Aus diesem Grund hören Sie häufig den Ausdruck asymptotische Komplexität. Dabei werden alle anderen Faktoren ignoriert. Es ist eine relative Darstellung der Komplexität.

Was ist nicht Big 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 Elemente reduziert, die als Schlüsselfaktor sortiert werden. Dies ist in Ordnung, berücksichtigt jedoch keine Probleme wie:

Speichernutzung: Ein Algorithmus verwendet möglicherweise viel mehr Speicher als ein anderer. Abhängig von der Situation kann dies von völlig irrelevant bis kritisch sein. Vergleichskosten: Es kann sein, dass der Vergleich von Elementen sehr teuer ist, was möglicherweise den realen Vergleich zwischen Algorithmen verändert. Kosten für das Verschieben von Elementen: Das Kopieren von Elementen ist normalerweise billig, dies ist jedoch nicht unbedingt der Fall. usw.

Kommentare

• Das einfache Verknüpfen eines Artikels ist nicht ‚ nicht allzu hilfreich. ‚ ist normalerweise eine gute Idee, den Abschnitt zu paraphrasieren oder zu zitieren, den Sie für den Thread besonders relevant finden.
• Sind die Abstimmungen wirklich notwendig? Der Artikel, den er verlinkt hat, ist sehr relevant und meiner Meinung nach ziemlich hilfreich.Die am häufigsten gewählte Antwort ist ein Link zu einem Wikipedia-Artikel. +1, um die Heuchelei des Schwarmgeistes auszugleichen.
• -1, weil der Artikel zwar ein sehr schöner und gut geschriebener Artikel ist, aber nicht ‚ Ich habe nichts mit der Frage zu tun.
• @Jorg, ich habe nie gesagt, dass der Artikel das Problem lösen würde, aber ich habe es geteilt, weil ich es nützlich gefunden hatte, als ich mir diese Konzepte angesehen habe.

BEARBEITEN: Es 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 genau das gleiche Symbol, so dass im Laufe der Zeit die Originalversion beschädigt wurde und jetzt nur noch Oh .

Die Auswahl des Symbols hat eigentlich keine bestimmte Bedeutung, es wurde als mnemonisches Gerät ausgewä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 wie ein Gleichheitszeichen aus 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 wird, um Ihnen zu helfen, sich an die Semantik mehr zu erinnern e asily.

Kommentare

• Obwohl ich gerne Ihrem mnemonischen Vorschlag glauben würde (es ist eine wirklich coole Idee), werde ich sehen müssen einige Beweise dafür, dass dies die eigentliche ursprüngliche Absicht von Bachmann ist. Geben Sie es an, und ich ‚ werde Sie +1.
• @Jonathan Henson: Anscheinend wurde ich von Prof. Knuth in die Irre geführt 🙂

„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 immer x> k.

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

Das große O wird manchmal nachher als Landau-Symbol bezeichnet der deutsche Mathematiker Edmund Landau. Ich glaube 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 bezeichnen, die in Ihrer planaren Geometrie der High School verwendet wurden Klasse.

Korrektur @ back2dos hat eine zufriedenstellende Erklärung für das O in Bezug auf die Reihenfolge geliefert. Großartig Job. Siehe seine Antwort.

Donald Knuth hat sie angewendet, um die Komplexität von Computerprogrammen zu untersuchen.

Wenn Sie herausfinden möchten, warum die Notation verwendet wurde, sollten Sie

„Analytische Zahlentheorie“ von Paul Bachmann aus dem Jahr 1892

UPDATE: Der Versuch, meine Antwort zu bereinigen und genauer zu sein

Die Big O-Notation ist eine Möglichkeit, Funktionen anhand ihrer Wachstumsraten zu charakterisieren steht für Ordnung (erste Ordnung ist n zweite Ordnung ist n-Quadrat usw.) Und wenn ich nicht bin Ein Fehler wäre das Worst-Case-Szenario für eine Methodenlaufzeit (oder -speicherung) mit N Elementen. Je größer die Reihenfolge, desto schlechter ist die Leistung der Methode.
Zum Beispiel ist das Nachschlagen eines Datensatzes in einem Array O (1) (ich glaube an eine Implementierung einer Hash-Tabelle, die auch der Fall ist). Das Hinzufügen eines Werts am Ende einer Linkliste wäre O (N), da Sie zum 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 🙂

Kommentare

• -1, weil dies einfach nur alt falsch ist UND eine andere Frage beantwortet hat als gestellt. Die Frage war, warum der Buchstabe “ O “ verwendet wird und nicht “ wie Big funktioniert O Notationsarbeit? „. Sie ‚ sind falsch darüber, wie Big-oh auch funktioniert … Das Durchlaufen eines Arrays ist O (n), wobei n die Größe des Arrays ist, nicht O (1). . Die Notation hat nichts mit “ Zyklen “ eines Algorithmus zu tun … es ‚ eine Messung der Obergrenze der Laufzeit eines Algorithmus.
• Hier nicht mit Ihnen zu streiten, aber das ist ‚ das, was ich meinte. 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 großzügig. Nach Zyklus hätte ich wohl Iterate-through oder so etwas sagen sollen. Sie haben Recht mit der Obergrenze. Sie bestimmt nicht den Durchschnitt. Daher akzeptiere ich das Downgrade.