Diskussion:Landau-Symbole

Formale Definition

gilt in der formalen Definition von groß O nun $0\leq \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty$ $\exists \ a$ oder $\forall \ a$?

Weder noch. a ist der Grenzwert, der üblicherweise "vergessen" wird Landau-Symbole#Vergessener_Grenzwert, also eigentlich f=O(g) für x gegen a, wenn gilt ... --NeoUrfahraner 15:36, 14. Mai 2007 (CEST)

konstante

Es ist aus dem artikel zwar klar dass für die algorithmische klasse O(1) == O(42) ist, jedoch weiss ich nicht ob, und wenn ja wie man es herleitet O(0) == O(1) ist. Keine zeit ist intuitiv was anderes als "eine nicht näher bezifferte endliche menge zeit". wäre schön wenn der artikel da noch mehr licht drauf werfen würde. (nicht signierter Beitrag von 62.155.239.225 (Diskussion) 19:34, 7. Dez. 2011 (CET))

Der Vollständigkeit halber hier mal die Aufklärung, auch wenn die Frage lange her ist:

Man kann den Ausdruck ${\mathcal {O}}(0)={\mathcal {O}}(1)$ schlicht nicht herleiten. Die Menge ${\mathcal {O}}(0)$ ist undefiniert, da für keine Funktion $f$ und erweiterte reelle Zahl $a$ der Grenzwert $\limsup _{x\to a}|f(x)/0|$ existiert, auch nicht im uneigentlichen Sinne.

Liebe Grüße -- 2001:638:807:20D:55AD:44F5:6CF6:ECF1 14:48, 23. Sep. 2015 (CEST)

Edit: Ok, wenn man die Quantoren-Definition zu Grunde legt, ist die Menge ${\mathcal {O}}(0)$ schon definiert, enthält aber nur die in einer Umgebung von $a$ verschwindenden Funktionen. Insbesondere gilt hier ${\mathcal {O}}(0)\neq {\mathcal {O}}(1)$. -- 2A02:8109:A7BF:E964:CD4A:2D71:A31D:E413 09:31, 25. Sep. 2015 (CEST)

Edit 2: Ich habe jetzt unten mal die Frage aufgeworfen, welche der beiden Fassungen nun "richtiger" (im Sinne der vorherrschenden Literatur) ist. -- 2001:638:807:20D:B9DF:2F79:BAE7:4835 11:47, 30. Sep. 2015 (CEST)

Witz?

Der Weblink ganz unten im Artikel soll doch ein schlechter Witz sein, oder? Das ist doch keine Mathematik, was der da macht?! (http://www.henning-thielemann.de/Study/Landau/landau.pdf)

Singularregel

Spricht etwas dagegen, den Artikel wegen der Singularregel [1] auf "Landau-Symbol" umzubennen? --NeoUrfahraner 05:40, 6. Mär 2005 (CET)

Der Begriff wird recht selten im Singular benutzt. Für mich spricht gegen eine Verschiebung aber hauptsächlich der Aufwand um die vorhandenen Redirects anzupassen. Vielleicht kann das ja jemand mit einem Bot machen. Gruß, JuergenL 10:31, 6. Mär 2005 (CET)

Da es sich ja um mehrere verschiedene Symbole handelt, würde ich eine Beibehaltung des Plurals bevorzugen. Denn es handelt sich ja nicht einfach um eine Mehrzahl von ein und demselben "Gegenstand", sondern tatsächlich um unterschiedliche Symbole, die unter einem Begriff zusammengefasst werden. Man beachte auch, dass die Singularregel zahlreiche Ausnahmen hat und daher nicht zu streng ausgelegt werden darf. --Mkleine 19:47, 8. Mär 2005 (CET)

ACK. Wenn jemand "Landau-Symbol" sagt, frag ich mich gleich: "welches?" - der Artikel sollte das Plural-Lemma behalten. -- D. Dÿsentrieb ⇌ 22:51, 8. Mär 2005 (CET)

PS: Das mit der Asymptotischen Laufzeit ist in der Tat unglücklich - es kann ja genausogut Asymptotischer Platzbedarf sein - man sollte den Artikel wohl entsprechend umschreiben. -- D. Dÿsentrieb ⇌ 22:52, 8. Mär 2005 (CET)

Asymptotisches Verhalten

Ich habe jetzt den Link von "asymptotisches Verhalten" auf Asymptotische Analyse gesetzt, den ich (analog zur englischen Version) neu angelegt habe; der Link auf "asymptotisches Verhalten" war dabei ein vergessener Zwischenzustand. REDIRECT von "Asymptotisches Verhalten" auf Asymptotische Analyse (wie in der englischen Version) halte ich nicht für notwendig. In Asymptotische Analyse wird als ein Beispiel weiter auf Asymptotische Laufzeit verwiesen, wenn es einen Artikel zum asymptotischer Platzbedarf gibt, gehört der sinnvollerweise wohl ebenfalls damit verlinkt. --NeoUrfahraner 23:57, 8. Mär 2005 (CET)

Prima so! Grüße --Mkleine 12:10, 9. Mär 2005 (CET)

Knuth-Definition

Wo findet sich die Knuth-Definition der Landau-Symbole? TAOCP? Sind f und g positiv, so stimmt die Definition mit der mir bekannten überein; ist eines der beiden negativ, gibt es aber wesentliche Unterschiede. Kann jemand bitte nachprüfen, ob die Definition wirklich so stimmt, wie sie hier steht. Danke, --NeoUrfahraner 00:46, 9. Mär 2005 (CET)

Ich habe vorerst im Artikel bei der Knuth-Definition gefordert, dass f und g nichtnegativ sind; das ist jednefalls der interessante Fall und damit sind wir auf der sicheren Seite. Falls jemand die genaue Knuth-Definition für den negativen Fall findet, kann er die Änderung gerne rückgängig machen. --NeoUrfahraner 17:15, 9. Mär 2005 (CET)

Habe sie rausgenommen. Das war ein Überbleibsel aus der ursprünglichen Version; die Definitionen Knuth zuzuschreiben, erscheint mir ziemlich fragwürdig, 1892 hat Knuth noch nicht gelebt.-- Gunther 14:53, 18. Apr 2005 (CEST)

Landau-Symbole in der Komplexitaetstheorie

In der Informatik werden sie insbesondere in der Komplexitätstheorie verwendet, um verschiedene Probleme und Algorithmen danach zu vergleichen, wie "schwierig" sie zu berechnen sind.

Ich behaupte mal ganz frech, dass die Landau-Symbole in der Komplexitaetstheorie relativ selten verwendet werden.

Betrachtet man Probleme bzgl. ihrer Komplexitaet, so werden eher die Komplexitaetsklassen wie P, NP, PSPACE, EXPTIME usw. herangezogen.

In der Informatik werden die Landau-Symbole v.a. bei der Laufzeitanalyse bzw. der Analyse des Speicherplatzbedarfs von konkreten Algorithmen eingesetzt.

--zeno 14:22, 18. Apr 2005 (CEST)

Wie nennt man das Teilgebiet der Informatik, dass sich mit "der Laufzeitanalyse bzw. der Analyse des Speicherplatzbedarfs von konkreten Algorithmen" beschäftigt? --NeoUrfahraner 08:56, 1. Jun 2005 (CEST)

Algorithmik? ---

Zu diesem Stichwort gibt es (noch?) keinen Eintrag in der Wikipedia. --NeoUrfahraner 12:37, 23. Nov 2005 (CET)

Wie wäre es mit Computeralgebra? Das Problem ist, dass die Fragestellung genau im Grenzgebiet zwischen Mathematik und Informatik liegt.--JFKCom 13:02, 22. Okt. 2006 (CEST)

Meiner Meinung nach, sollte ein Wikipedia-Artikel nicht ausufern. Die Landau-Symbole sind ein allgemeines mathematisches Konstrukt und werden natürlich gerade in der Komplexitätstheorie verwendet. Trotzdem ist es fehl am Platz, in diesem Artikel über Compiler und Maschinenmodell zu reden. Verständlicher wäre der Artikel, wenn man den ganzen Abschnitt streichen würde.

Dem möchte ich voll und ganz zustimmen.

Außerdem ist der Abschnitt hier schwach formuliert, z.B. "In der Komplexitätstheorie werden die Landau-Symbole vor allem verwendet, um den (minimalen oder maximalen)Zeit- oder Speicherplatzbedarf eines Algorithmus zu beschreiben. Man spricht dann von Zeitkomplexität bzw. Platzkomplexität. " -- Wieso "dann"? Man spricht immer von Zeit- bzw. Platzkomplexität. Das wäre auch ohne Landau-Symbole so. Es sollte nicht der Schwanz mit dem Hund wedeln. Man verwendet ja auch in vielen Bereichen das +-Symbol, ohne dass man sie nun alle unter dem Artikel "Addition" subsummieren würde. --Bri B. 11:23, 15. Feb. 2010 (CET)

Beispiele

am besten sind Beispiele.

Wie lautet beispielsweise die Komplexität:

for (i=5;i<n*n;i++){ i=i+1; for (j=0;j<i;j++){ a=sqrt(c*c - b*b) }

}

oder:

for (i=5;i<n;i++){ i=i+1; }

for (j=0;j<i;j++){ a=sqrt(c*c - b*b) }

Besser wären wohl ein paar konkrete Algorithmen, beispielsweise ein dynamisch wachsendes Array; wenn man immer Blöcke fester Länge allokiert, hat das Einfügen am Ende O(n) Aufwand; wenn man die Blockgröße immer verdoppelt, hat das Einfügen am Ende im Durchschnitt O(1) Aufwand. --NeoUrfahraner 09:02, 1. Jun 2005 (CEST)

Hallo, ich mache für mein Informatik Studium ein Projekt zum Thema O Notation machen. Würd gerne ein paar Beispiele machen und die hier online stellen bzw auf der Seite verbessern. Wir wäre es mit konkreten Algorithmen wie von einem Heapsort, Bubblesort die eine Laufzeit von O(n) haben oder vllt aber aber auch eine Suche in einer Baumstruktur, die eine Laufzeit von O(log2 n) haben. Ich werde mal in den nächsten Tagen was ausarbeiten und hier nochmal die Beispiele reinstellen. Will nichts verändern ohne Zustimmung von euch.

Mit Freundlichen Grüßen

Matthäus Gdaniec

Wenn du wirklich Ahnung vo Thema hast und dich nicht für das Projekt das erstemal mit der O-Notation beschäftigst, dann kannst du gerne dern Artikel verbessern. Aber bitte wirklich was qualitativ hochwertiges. --Stefan Birkner 00:26, 9. Mai 2007 (CEST)

Also ich hab da mal was ausgearbeitet. Bzw was geändert und ein Rechenbeispiel angefügt

Das sieht gut aus. --Stefan Birkner 22:24, 12. Mai 2007 (CEST)

Also ich sprech das dann mal mit meinem Prof ab und stell das dann online --Matthäus Gdaniec 11:56, 13. Mai 2007 (CEST)

Habs nochmal alles geändert --Matthäus Gdaniec 11:56, 13. Mai 2007 (CEST)

Die Tabelle (mit Beispielen für Laufzeiten) gefällt mir sehr gut. Als typisches Beispiel für O(1) könnt man Look-Up in einer Hashtabelle (bei geeigneter Wahl von Hash-Funktion und Größe der Hashtabelle) wählen; als Beispiel für O(n log n) könnte man noch FFT anführen. --NeoUrfahraner 09:01, 30. Mai 2007 (CEST)

Zu $f\in {\mathcal {O}}(x\log x)$: Was mit "Suche im sortierten Feld mit x Einträgen" gemeint ist, ist mir nicht ganz klar. Als Beispiel für O(1) ist mir noch das Löschen und Einfügen eines Elements in einer Liste (Datenstruktur) eingefallen, vgl. auch die Tabelle in en:Linked_list#Linked_lists_vs._arrays --NeoUrfahraner 22:11, 2. Jun. 2007 (CEST)

Beispiel für exponentielles Wachstum $O(z^{N})$: Backtracking --NeoUrfahraner 09:10, 30. Mai 2007 (CEST)

Beispiel für $O({\sqrt {x}})$: en:Birthday attack --NeoUrfahraner 09:18, 30. Mai 2007 (CEST)

Das Rechenbeispiel gefällt mir weniger; insbesondere würde ich die Rechnung durch $ax^{n}\in {\mathcal {O}}(x^{m})$ für $n\leq m$ und $f_{n}(x)\in {\mathcal {O}}(g)\implies \sum _{n=1}^{N}f_{n}(x)\in {\mathcal {O}}(g)$ abkürzen. --NeoUrfahraner 09:01, 30. Mai 2007 (CEST)

Und wurde es so erklärt, ich finds so relativ anschaulich und es wird sogar von Laien relativ gut verstanden --Matthäus Gdaniec 16:59, 02. Juni 2007 (CEST)

Das ist jedenfalls eine Geschmacksfrage, vielleicht gibt es noch andere Meinungen dazu. --NeoUrfahraner 22:11, 2. Jun. 2007 (CEST)

Hmm irgendwie schreibt keiner mehr was dazu --Matthäus Gdaniec 16:45, 07. Juni 2007 (CEST)

Leider :-(. Die Spalte mit den Beispielen für Laufzeiten wären (mit Ausnahme von "Suche im sortierten Feld mit x Einträgen") meines Erachtenes jedenfalls reif, in den Artikel aufgenommen zu werden. Machst Du das? --NeoUrfahraner 17:13, 7. Jun. 2007 (CEST)

Habs gemacht. Was machen wir mit dem anderen?? --Matthäus Gdaniec 22:29, 08. Juni 2007 (CEST)

Vorher noch eine Frage: wie ist das mit O(x log x) und "Suche im sortierten Feld mit x Einträgen" gemeint? Wenn's Feld sortiert ist, ist es ja binäre Suche und O(log x). --NeoUrfahraner 08:22, 9. Jun. 2007 (CEST)

Beispiele

In den folgenden Beispielen ist $f=f(x)$ stets als Funktion von $x$ zu verstehen.

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
$f\in {\mathcal {O}}(1)$	$f$ ist konstant	$f$ wächst nicht, wenn sich das Argument ändert.	Look Up in einer Hashtabelle
$f\in {\mathcal {O}}(\log x)$	$f$ logarithmisches Wachstum	$f$ wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Merke: Die Basis des Logarithmus ist egal.	Binäre Suche im sortierten Feld mit x Einträgen
$f\in {\mathcal {O}}({\sqrt {x}})$	$f$ Wachstum wie die Wurzelfunktion	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument vervierfacht
$f\in {\mathcal {O}}(x)$	$f$ lineares Wachstum	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument verdoppelt.	Suche im unsortierten Feld mit x Einträgen
$f\in {\mathcal {O}}(x\log x)$			Suche im sortierten Feld mit x Einträgen Mergesort
$f\in {\mathcal {O}}(x^{2})$	$f$ quadratisches Wachstum	$f$ wächst ungefähr auf das vierfache, wenn sich das Argument verdoppelt	Einfache Algorithmen zum Sortieren von x Zahlen Bubblesort
$f\in {\mathcal {O}}(2^{x})$	$f$ exponentielles Wachstum	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument um eins erhöht
$f\in {\mathcal {O}}(x!)$	$f$ faktorielles Wachstum	$f$ wächst ungefähr um das $x$-fache, wenn sich das Argument von $x-1$ auf $x$ erhöht.

Anmerkung: Mir erscheinen die Beispiele etwas irreführend. Ist hier nicht jeweils die Theta-Notation angebracht? Schließlich ist ja auch z.b. 3x+4 in O(x^2), auch wenn das nicht "ungefähr auf das vierfache wächst, wenn sich das Argument verdoppelt"--Bushmann 18:10, 6. Jul. 2009 (CEST)

Anmerkung: Ich stimme zu, so wie das momentan da steht ist das in meinen Augen falsch. f konstant liegt z.B. in allen angegebenen Wachstumsklassen, aber passt zur Bedeutung und anschauliche Erklärung nur im ersten fall.-- 84.170.177.240 19:34, 20. Feb. 2010 (CET)

Ja, die Tabelle ist total irreführend. Es wird gar nicht klar, dass es sich um eine obere Schranke handelt. --132.176.94.105 09:40, 15. Nov. 2024 (CET)

Rechenbeispiele

Zu der ${\mathcal {O}}$ Notation (Obereren Schranke)

Das Wachstum eines Polynoms $f(x)=\sum _{i=0}^{n}k_{i}\cdot x^{i}$ ist nach ${\mathcal {O}}$-Notation beschränkt durch das Monom mit dem größten Grad, also durch ${\mathcal {O}}(x^{n})$.

$f(x)={\mathcal {O}}(x^{n})\,\,\,\forall n\geq n_{0}$

${\mathcal {O}}(g(x))=c\cdot g(x)$

$\Leftrightarrow \,\,\,\,\,\,f(x)\leq c\cdot g(x)\,\,\,\forall n\geq n_{0}$

Gegeben sei eine Funktion $f(x)$ mit $f(x)=3x^{3}-2x^{2}+x-9$

$f(x)={\mathcal {O}}(x^{3})\,\,\,\forall n\geq n_{0}$

$3x^{3}+2x^{2}+x+9\leq c\cdot x^{3}\,\,\,\forall n\geq n_{0}$

Wahl c & $n_{0}$:

Das Monom mit größten Grad der Funktion $f(x)=3x^{3}-2x^{2}+x-9$ ist $3x^{3}$

$\rightarrow \,\,\,\,\,c\geq 3$

Graphen

wähle $c=15\,\,\,\,n_{0}=1$ ( beide Werte zufällig gewählt )

Beweis:

$3x^{3}+2x^{2}+x+9\leq 15\cdot x^{3}\,\,\,\forall n\geq n_{0}$

$\Leftrightarrow 2x^{2}+x+9\leq 12\cdot x^{3}\,\,\,\forall n\geq n_{0}$

$\Leftrightarrow 2x^{2}+x+9\leq 12\cdot x^{3}\,\,\,\forall n\geq n_{0}$

$\Leftrightarrow {2 \over x}+{1 \over x^{2}}+{9 \over x^{3}}\leq 12\,\,\,\forall n\geq n_{0}$

Da $n_{0}=1$

${2 \over 1}+{1 \over 1^{2}}+{9 \over 1^{3}}\leq 12$

$\Leftrightarrow 12\leq 12$

q.e.d.

TeX oder Text, das ist die Frage

@Squizzz: Ich hatte im letzten Abschnitt die TeX-Formatierungen durch Text ersetzt, weil sich dadurch der ganzen Textabschnitt erstens schöner lesen lesen, und desweiteren der Text schön gleichmäßig aussah. In manchen Fällen ist TeX wohl eine bessere Variante, das gebe ich zu, doch hier fand ich es wirklich schöner. Zumal für diesen Abschnitt wirklich für jedes TeX-Zeichen ein Textzeichen existierte. Was hast du gegen Text-Zeichen???

Vielleicht können auch noch andere Leute ihre Meinung zu "TeX-oder Textzeichen" äußern. Danke.--217.233.162.55 22:59, 28. Mär 2006 (CEST)

Das wurde schon x-mal diskutiert: Konsens ist, dass keine Formeln von TeX in HTML/Wiki-Markup umgeschrieben werden sollen. Hoffentlich bald kann man dann auch die Darstellung mit MathML auswählen, dann springen die Formeln nicht mehr so aus der Zeile.--Gunther 23:17, 28. Mär 2006 (CEST)

Verständlichket dieser Seite

Liebe Landau-Symbol-Editoren: Ich habe soeben von der End-Rekursion her auf diese Seite verlinkt, weil wir dort die Gross-O-Notation für die Bezeichnung der Laufzeitklassen benötigen. Aber wenn nun ein Laie von der End-Rekursion her diese Seite anklickt, dann wird er den Computer verkaufen und Gärtner! Da bin ich überzeugt (Gärtner ist im Übrigen auch ein schöner Beruf)

Ich kenne die Gepflogenheiten bzgl. sprachübergreifender Links, bzw. Kopien (mit Übersetzungen) aus einer anderen Sprache von Wikipedia nicht, aber: Die englische Seite bzgl. der O-notation beinhaltet eine kleine Tabelle (Common orders of functions) der geläufigen Laufzeit-klassen. Könnte die hier noch 'reingeoperiert' werden?

Nicht, dass die Seite dadurch für Laien erheblich beruhigender wirken würde, aber es wäre ein Anfang und genau das, was von unserem Link her erwartet würde.

Frage

Hi,
ich hab mal n Frage und bitte um schnelle Antwort:
ist O(x) - O(x) = 0 oder = O(x)

vielen Dank

مبتدئ 04:45, 22. Okt. 2006 (CEST)

Wo ist das Problem? $\textstyle 0={\mathcal {O}}(x)$ ist doch offensichtlich. (Wenn Du die Frage nicht an zig Stellen gespammt hättest, hätt ich Dir glatt ’ne ausführlichere Antwort gegeben, so hab ich aber keine Lust dazu. *feix*) —mnh·∇· 06:10, 22. Okt. 2006 (CEST)

Erste Aussage ist falsch. Siehe ausführliche Antwort auf meiner Diskseite. --Schlurcher ??? 10:54, 22. Okt. 2006 (CEST)

Auch ich bin Opfer des Mehrfach-Spammens und habe geantwortet.--JFKCom 13:04, 22. Okt. 2006 (CEST)

Danke Mnh: es findet sich immer ein nette Wikipedianer der die Fragen beantwortet. Ich weiss das es in etwa sowas wie vernachlässigbar heisst, nur leider brauche ich das Symbol für die Reduktion von Systemen auf Zentrumsmannigfaltigkeiten und da muss ich den Restfehler oder Restdynamik schon Richtig Abschätzen und nicht einfach Null setzen. Danke JFKCom und sorry für das Spam nur leider brauche ich die Infos für in 2 Tagen deswegen bin ich etwas in Eile. Thanx مبتدئ 03:59, 23. Okt. 2006 (CEST)

Struktur der Landau-Mengen

Ich beziehe mich auf einige der oben gestellten Fragen (Verständlichkeit).
Die Mengen, die eigentlich mit den Landau-Symbolen ${\hbox{O}}(g)$ und ${\hbox{o}}(g)$ gemeint sind, haben ja eine "natürliche Struktur" als Funktionenräume bzw. sogar als Algebren. Einige der formalen Eigenschaften (die mit den vielen Quantoren drin) ließen sich unter diesem Gesichtspunkt leichter formulieren, bzw. wären sogar selbstverständlich. Vielfache, Summe usw. von linearen Räumen. Dann würden auch die in Beweisen gern verwandten assymmetrischen Gleichheitszeichen der Art:

$x+{\hbox{O}}(\log(x))={\hbox{O}}(x)$

(weil der Autor die bessere Abschätzung mit log nicht braucht) richtiger als Element- bzw. Teilraumbeziehungen interpretieren:

$x+{\hbox{O}}(\log(x))\subseteq {\hbox{O}}(x)\quad {\hbox{oder ausfuehrlicher}}\quad x\in {\hbox{O}}(x){\hbox{ und }}{\hbox{O}}(\log(x))\subseteq {\hbox{O}}(x)$

Problem dabei: Ob Landau die Symbole so gemeint hat, ist fraglich. Und das asymmetrische "=", das zumindest in der Zahlentheorie verbreitet ist, bleibt ein Ärgernis, das nicht via Enzyklopädie getadelt oder gar beseitigt werden kann.--KleinKlio 22:18, 26. Okt. 2006 (CEST)

Gebt dem Vorschreiber vollkommen Recht

Änderungen von Wimmerm, 6. April 2007

Hallo Wimmerm, bei Deinen Änderungen vom 6. April sind mir zwei Punkte aufgefallen:

Erstens: Du hast

$\Theta (f)={\hbox{O}}(f)\cap \Theta (f)$

auf

$\Theta (f)={\hbox{O}}(f)\cap {\hbox{o}}(f)$

geändert. Wegen $\Theta (f)\subseteq {\hbox{O}}(f)$ ist die alte Version offensichtlich richtig gewesen; wegen ${\hbox{o}}(f)\subseteq {\hbox{O}}(f)$ ist die neue Version IMHO falsch; richtig wäre beispielsweise

${\hbox{o}}(f)={\hbox{O}}(f)\cap {\hbox{o}}(f)$

Natürlich hast Du recht. Ich habe meinen Fehler rückgängig gemacht. Sorry.Wimmerm 15:04, 6. Apr. 2007 (CEST)

Zweitens: "In den folgenden Beispielen ist $f=f(n)$ stets als Funktion von $n$ zu verstehen." In der Spalte "Notation" verwendest Du aber $x$; da gehört einheitlich $x$ oder einheitlich $n$. --NeoUrfahraner 08:17, 6. Apr. 2007 (CEST)

Das x in O(x) ist eine ungebundene Variable, oder noch besser, eine Funktion wie beispielsweise bei O(x^2+log(x)). Sie wird verwendet, um die Klasse aller gleich schnell wachsenden Funktionen darzustellen. Sie hat aber nichts mit dem Funktionsparameter von f links des Gleichheitszeichens zu tun. Ich weiß, eine weitere Variable verwirrt, aber die selbe Variable würde implizieren, dass sie doch etwas mit dem Funktionsparameter zu tun hat.

Der Grund, wieso ich n eingeführt habe, war die Erklärung von "f wächst faktoriell". Da kommt das n auch vor. Ohne Bindung des n ist die Erklärung unverständlich.Wimmerm 15:04, 6. Apr. 2007 (CEST)

Bitte wie? Setzen wir z.B. $f(n)=n^{2}$. Was bedeutet dann z.B. $n^{2}\in {\hbox{o}}(x)$? --NeoUrfahraner 07:36, 7. Apr. 2007 (CEST)

Ok, ich habe es geändert. Gruß, Wimmerm 20:29, 7. Apr. 2007 (CEST)

Danke, --NeoUrfahraner 00:18, 8. Apr. 2007 (CEST)

Beispiel der Stirling-Formel inkorrekt

Da schon $n!={\mathcal {O}}\left(n^{n}\right)$ gilt ist die Abschätzung $n!={\mathcal {O}}\left({\sqrt {n}}\cdot n^{n}\right)$ viel zu ungenau, die Stirling-Formel braucht man dazu nicht. Gemeint ist hier vermutlich $n!={\mathcal {O}}\left({\sqrt {n}}\left({\frac {n}{e}}\right)^{n}\right)$. -- octo

Stimmt. Anonyme Änderung vom 30. März 2006: http://de.wikipedia.org/w/index.php?title=Landau-Symbole&diff=15196731&oldid=15091466 , seither unentdeckt. Ich korrigier's. --NeoUrfahraner 13:09, 18. Apr. 2007 (CEST)

Wer weiß was?

Weiß jemand ob folgenden Beziehungen immer stimmt und wie man die formal beweisen kann? (anschaulich ist klar)

${\mathcal {O}}({\mathcal {O}}(f))\subseteq {\mathcal {O}}(f)$

${\mathcal {O}}(f)+{\mathcal {O}}(g)\subseteq {\mathcal {O}}(f+g)={\mathcal {O}}(\max(f,g))$

(nicht signierter Beitrag von 129.13.186.1 (Diskussion) 20:49, 28. Mai 2007 (CET))

Da die Landau-Symbole nur für Funktionen und nicht für Mengen erklärt sind und auch nicht ad hoc klar ist, was hier mit der Summe von Mengen gemeint ist, formuliere ich deine Fragen zunächst um.

(Solche Dinge passieren leider, wenn man ein sybolisches Gleichheitszeichen verwendet, statt eines "$\in$".)

(1) $\forall f'\in {\mathcal {O}}(f)\colon {\mathcal {O}}(f')\subseteq {\mathcal {O}}(f);$

(2).1 $\ \forall f'\in {\mathcal {O}}(f),g'\in {\mathcal {O}}(g)\colon f'+g'\in {\mathcal {O}}(f+g);$

(2).2 $\ {\mathcal {O}}(f+g)={\mathcal {O}}(\max(f,g)).$

Es wird hier nur der Grenzwert $a=\infty$ behandelt; die Fälle $a\in \mathbb {R}$ und $a=-\infty$ sind analog. Wegen der unten behandelten Diskrepanz wird die Quantoren-Definition herangezogen.

• Zu (1): Sei $h\in {\mathcal {O}}(f')$ und daher $\exists C_{1},C_{2},x_{1},x_{2}>0\colon (\forall x>x_{1}\colon |h(x)|\leq C_{1}\cdot |f'(x)|)\land (\forall x>x_{2}\colon |f'(x)|\leq C_{2}\cdot |f(x)|)$ daraus folgt nun $\forall x>\max(x_{1},x_{2})\colon |h(x)|\leq (C_{1}\cdot C_{2})\cdot |f(x)|$, also $h\in {\mathcal {O}}(f)$ wie gewünscht.
• Die Beziehungen in (2) gelten nur unter der Voraussetzung $(*):f,g\in {\mathcal {O}}(f+g)$ (für hinreichend große $x$ mit den jeweiligen Konstanten $C_{f}$ und $C_{g}$). Diese Voraussetzung ist allerdings nur in pathologischen Fällen nicht erfüllt.
  • Beweis (2).1: Unter den genannten Bedingungen gilt $\exists C_{1},C_{2},C_{f},C_{g},x'>0\ \forall x>x'\colon |f'(x)+g'(x)|\leq |f'(x)|+|g'(x)|\leq C_{1}|f(x)|+C_{2}|g(x)|\leq ^{(*)}(C_{1}\cdot C_{f})|f(x)+g(x)|+(C_{2}\cdot C_{g})|f(x)+g(x)|=((C_{1}\cdot C_{f})+(C_{2}\cdot C_{g}))|f(x)+g(x)|$, ergo $f'+g'\in {\mathcal {O}}(f+g)$.
  • Beweis (2).2: Wegen (1) genügt es hier $f+g\in {\mathcal {O}}(\max(f,g))$ und $\max(f,g)\in {\mathcal {O}}(f+g)$ zu zeigen. Dies folgt aus $|f+g|\leq |f|+|g|\leq 2\cdot |\max(f,g)|$ sowie $|\max(f,g)|\leq \max(|f|,|g|)\leq |f|+|g|\leq ^{(*)}(C_{f}+C_{g})|f+g|$, jeweils punktweise für hinreichend große $x$.

Gilt die Voraussetzung $(*)$ nicht, so ist $f(x)=x,g(x)=-x$ ein Gegenbeispiel: Es gilt ${\mathcal {O}}(g)={\mathcal {O}}(f)$ - man beachte die Definition über den Betrag - aber mit der Wahl $f'=g'=f$ gilt $f'+g'=2x\notin {\mathcal {O}}(f+g)={\mathcal {O}}(0)$.

Liebe Grüße -- 2001:638:807:20D:A99F:A822:4219:A849 15:20, 2. Okt. 2015 (CEST)

QuickSort nicht ohne Weiteres in O(n log n)

Wer hat denn das Beispiel QuickSort bei O(n log n) eingetragen. Das stimmt nicht. QuickSort hat worst case O(n^2) und nur im best case O(n log n). Es gibt andere Sortieralgorithmen, die sicher in O(n log n) laufen: Heapsport, IntroSort, ... vielleicht sollte man das austauschen.

Ich habe QuickSort entfernt, vgl. http://de.wikipedia.org/w/index.php?title=Landau-Symbole&diff=34023670&oldid=33376112 --NeoUrfahraner 14:14, 12. Sep. 2007 (CEST)

Lambda-Kalkül

Müsste für die formal korrekte Schreibweise nicht das Lambda-Kalkül angewendet werden?

Statt $f(x)\in {\mathcal {O}}(x^{2})$ oder $f\in {\mathcal {O}}(x^{2})$ besser $f\in {\mathcal {O}}(\lambda x.x^{2})$

Es sind schließlich Aussagen über Funktionen und nicht den Funktionswert an eine Stelle $x$.--Fomafix 23:59, 15. Nov. 2007 (CET)

aufwändig oder aufwendig

Zwar sind beide Formen korrekt, jedoch wird die Form "aufwendig" von der Dudenredaktion empfohlen. Siehe hierzu [2]. Grund dieser Empfehlung ist: Elektriker legen Kabel "aufwändig", also auf der Wand. Dennoch sind beide Formen korrekt. Ich bin aber dafür, der Empfehlung zu folgen. -- Sulai 12:25, 9. Dez. 2007 (CET)

Da beide Formen korrekt sind, liegt es im Ermessen des jeweiligen Autors, welche er verwendet. In einem Artikel sollte die Schreibweise einheitlich sein. Es wird jedoch nicht gerne gesehen, wenn jemand Artikel ändert, nur um seine bevorzugte Schreibweise einzuführen. --Stefan Birkner 14:40, 9. Dez. 2007 (CET)

Form des Os

Mir ist in der Mathematik und in der Physik bisher nur ein einfaches großes $O$ begegnet, aber kein ${\mathcal {O}}$. Ist letzteres tatsächlich gebräuchlich bzw. das Gebräuchlichere? --Digamma 20:13, 21. Dez. 2007 (CET)

Ich glaube, dass ein mathematisches ${\mathcal {O}}$ in angloamerikanischen Raum recht verbreitet ist, jedenfalls habe ich es sehr häufig in wissenschaftlichen Publikationen gesehen. Viele Grüße -- Meph666 ^{→ post} 14:33, 22. Dez. 2007 (CET)

(BK)Mir laufen beide Varianten etwa gleich häufig über den Weg, wobei Skripte/Präsentationen scheinbar meist $O$ verwenden und Bücher und Papers unabhängig vom Herkunftsland häufiger ${\mathcal {O}}$. Ich vermute das liegt daran, dass erstere mit Powerpoint und co gebaut werden, bei denen die Autoren es für umständlich und entbehrlich halten, ewig in den Sonderzeichen nach dem Kalligrafie-O zu suchen, während das selbe Problem z.B. in LaTeX (und vermutlich in anderen Typesetting-Systemen) überhaupt kein Thema ist. Allerdings bezieht sich meine Erfahrung eher auf die Literatur in der Informatik als auf die in Mathe und Physik.

Ich persönlich halte die beiden Varianten für vollkommen austauschbar, die Kalligrafie-Variante aber für unzweideutiger als das reguläre O, wenn der Kontext nicht eindeutig ist. --Schmiddtchen 说 14:38, 22. Dez. 2007 (CET)

Im Original bei Bachmann und Landau ist es wohl $O$ gewesen (Ich habe es aber nicht überprüft), und wenn es tatsächlich ein großes griechisches Omikron sein soll, muss es natürlich wie ein normales O aussehen. Das kalligraphische O für die O-Notation halte ich für einen bedauerlichen Auswuchs aus den Möglichkeiten von LaTeX, wo man solche Sonderzeichen leicht zur Verfügung hat, und wo sich diese Variante in der Informatik verbreitet hat. Auch in der Reihe $O,o,\Omega ,\omega ,\Theta$ würde das ${\mathcal {O}}$ aus dem Rahmen fallen. Natürlich hat er andererseits etwas für sich, für Symbole mit besonderer Bedeutung besondere Schriften zu nehmen. Aber die kalligraphischen Buchstaben werden typischerweise eher für „große“ Objekte wie Mengenfamilien verwendet, und das ${\mathcal {O}}$ würde für meinen Geschmack in einer langen Herleitung mit viel O-Notation zu sehr auffallen. Ich halte auch nichts davon, das klein-o nicht einfach als $o()$ zu schreiben, sondern als geradegestelltes $\mathrm {o} ()$ hervorzuheben. Das sieht für mich in der Mitte einer Formel eher wie ein Kringel aus. Typischerweise sind die griechischen Kleinbuchstaben (omikron) auch schräggestellt. Don Knuth, von dem erstens TeX entwickelt wurde, und dem zweitens die Verbreitung der $\Omega$-Notation in der Informatik und überhaupt die Einführung der $\omega$-Notation zu verdanken ist, schreibt jedenfalls auch $O()$, siehe die Referenzen auf der englischen wikipedia-Seite, zum Beispiel Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11.1: The O-Notation, pp.107–111. --Günter Rote 14:30, 10. Juni 2008 (CET)

In der Mathematik wird fast ausschließlich ein normales $O$ benützt. Ein Großteil der asymptotischen Analysis kommt aus der Theorie komplexer Funktionen. Das Symbol ${\mathcal {O}}$ ist dort bereits für die Menge holomorpher Funktionen im Einsatz. In der Algebraischen Geometrie verwendet man ${\mathcal {O}}$ für die Strukturgarbe eines Schemas oder eines geringten Raums. Das Symbol $O$ hingegen ist nicht anders belegt. ASlateff -- 193.170.74.111 13:22, 22. Jul. 2010 (CEST)

Stochastik

Mal jemand O_p und o_p ergänzen? --Scherben 17:08, 20. Feb. 2008 (CET)

Anschauliche Bedeutung "nicht wesentlich schneller"

"f wächst nicht wesentlich schneller als g" ist zwar "richtiger" als "f wächst nicht schneller als g", kann aber von einem Laien auch leicht fehlinterpretiert werden. Und zwar so, dass f zwar schneller wachsen muss, aber nur unwesentlich. Kann man das nicht noch besser (eindeutig) formulieren?

Vielleicht mit ein wenig Redundanz: "f wächst langsamer oder zumindest nicht wesentlich schneller als g"? --NeoUrfahraner 18:47, 13. Aug. 2009 (CEST)

Definition mit Quantoren

$\lbrace x:d(x,a)<\varepsilon \rbrace$

Wo kommt das d denn her? Was bedeutet es? 134.2.173.104 15:35, 28. Jul. 2009 (CEST)

Das d ist die Metrik eines metrischen Raums und kommt von dieser Änderung: http://de.wikipedia.org/w/index.php?title=Landau-Symbole&diff=prev&oldid=21558864 Irgendwann wurde aus dem metrischen Raum ein normierter Raum: http://de.wikipedia.org/w/index.php?title=Landau-Symbole&diff=prev&oldid=24883966 Ich mache wieder einen metrischen Raum draus. --NeoUrfahraner 16:26, 28. Jul. 2009 (CEST)

PS: Die Änderung http://de.wikipedia.org/w/index.php?title=Landau-Symbole&diff=62449745&oldid=61198741 habe ich bewußt nicht übernommen: $f\in {\mathcal {O}}(g)$ bedeutet, $0\leq \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty$, wird der Quotient 0, so wächst f wesentlich langsamer als g. --NeoUrfahraner 16:36, 28. Jul. 2009 (CEST)

Die Definitionen sind fragwürdig (x wird bei der Menge sowohl als freie, als auch als gebundene Variable eingesetzt).

Ausreichend wäre: Für alle x mit d(x,a) kleiner epsilon gilt... Generell ist der Artikel in keinem guten mathematischen Stil geschrieben. Auch Formeln wie $0\leq \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty$ sind schlechter Stil, denn ein Betrag ist immer größer gleich Null. Der wesentliche Punkt ist, dass der Limes Superior endlich ist. Dass eine Metrik vorkommt, ohne einen metrischen Raum zu erwähnen, rundet das Bild äußert schlechten Stils ab. ASlateff -- 193.170.74.111 13:15, 22. Jul. 2010 (CEST)

Log2

Wäre es nicht korrekt und angebracht, dass bei den O(log (x)) Beispielen darauf verwiesen wird, dass es sich um den Logarithmus mit Basis 2 handelt und nicht mit Basis 10 oder e? Respektive - warum ist die Basis des Logarithmus 'egal'? Ist den quadratischer Aufwand auch das gleiche wie kubischer Aufwand? --Fmerian 10:59, 14. Okt. 2009 (CEST)

Siehe Logarithmus#Basisumrechnung

$\log _{b}r={\frac {\log _{a}r}{\log _{a}b}}$

somit ist

${\mathcal {O}}(\log _{b}x)={\frac {1}{\log _{a}b}}{\mathcal {O}}(\log _{a}x)$

und der Faktor ${\frac {1}{\log _{a}b}}$ spielt für das asymptotische Verhalten keine Rolle. --NeoUrfahraner 16:15, 28. Okt. 2009 (CET)

Falscher Web-Link O-Notation auf linux-related.de (http://www.linux-related.de/coding/o-notation.htm )

Der Link führt nicht zu einem Beitrag zum Thema. Ist das Link-Spam oder eine Fehler?

Ich hoffe mit diesem Hinweis Wikipedia geholfen zu haben. Sollte er gegen Richtlinien verstoßen, tut mir das leid. Dann bitte umgehend löschen. Ich habe den Link nicht selbst gelöscht, weil dort noch so viele andere Sachen standen, die nicht angezeigt werden, für Wikipedia aber vielleicht nützlich sind.

MfG, KS (nicht signierter Beitrag von 109.90.26.182 (Diskussion) 23:54, 9. Aug. 2010 (CEST))

Bei mir führt er durchaus zu einem Artikel zum Thema mit Titel "Laufzeitkomplexität von Algorithmen - die O-Notation". -- Digamma 10:25, 10. Aug. 2010 (CEST)

Ja, nach vielen Redirects gehts zu: http://www.linux-related.de/index.html?/coding/o-notation.htm - das werde ich im Artikel mal anpassen. -- Phil1881 16:16, 10. Aug. 2010 (CEST)

Folgerungen

In der Liste der Folgerugnen findet sich auch $\Theta (f)\subseteq {\mathcal {O}}(f)\cap \Omega (f)$. Das ist zwar offensichtlich korrekt, könnte man da nicht aber die schärfere Bedingung $\Theta (f)={\mathcal {O}}(f)\cap \Omega (f)$ ansetzen? Das folgt m.E. bereits aus der Definition. -- PyroPi 21:27, 12. Feb. 2011 (CET)

Sehe ich genauso und finde es verwirrend, nur die Teilmengenbeziehung anzugeben, da man annehmen könnte, es handle sich um eine echte Teilmenge. Habe es daher geändert. -- Christian Matt 23:29, 1. Jul. 2011 (CEST)

Fehler in Definition?

Ist in den Definitonen mit Quantoren nicht ein Fehler beim Zweiten? Wenn es für alle c gelten soll, dann müsste f praktisch 0 sein, oder? Danke --Engeltr 08:40, 11. Jul. 2011 (CEST)

Meinst du das?

$\forall \ c>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|\leq c\cdot |g(x)|$

--Jobu0101 11:36, 19. Jul. 2011 (CEST)

Fakultät

Im Artikel steht etwas von

$f\in {\mathcal {O}}(x!)$

Wobei x reell sein soll. Die Faktultät ist aber nicht für alle reelle Zahlen definiert. Man sollte das vielleicht mit der Gammafunktion ersetzen. --Jobu0101 11:34, 19. Jul. 2011 (CEST)

Fehler in O-Definition

Da $o(f)\subseteq O(f)$ müßte doch eigentlich $f\in O(g)\Leftrightarrow 0\leq \lim _{n\rightarrow a}\sup {\frac {f(n)}{g(n)}}<\infty$ gelten und nicht $f\in O(g)\Leftrightarrow 0<\lim _{n\rightarrow a}\sup {\frac {f(n)}{g(n)}}<\infty$, ansonsten wäre ja $n\in o(n^{2})$, aber $n\notin O(n^{2})$. -- Ibennyd 14:48, 17. Aug. 2011 (CEST)

Sprechweise

Wie spricht man das ${\mathcal {O}}$ bzw. o eigentlich aus? $f\in {\mathcal {O}}(g)$ also "f ist Element von O bzw o von g"? Ich habe im Hinterkopf, dass da ein "ordo" (Groß-Ordo oder Klein-Ordo) gesprochen wird (etwa der Art "f ist Groß-Ordo von g"), kann dazu jetzt aber nichts finden. Wer Verbindliches weiß, sollte das mal hier erläutern und im Artikel ergänzen. --CarstenH 14:55, 14. Dez. 2011 (CET)

Ordo habe ich nie gehört. Gängig ist die Aussprache "groß O" bzw. "klein o". Eigentlich ist es ja kein lateinisches O/o, sondern ein großes/kleines Omikron, wird aber meist nicht so genannt.--92.77.208.58 04:38, 27. Aug. 2014 (CEST)

auf englisch sagt man manchmal "order of" (etwa: in der groessenordnung von), also bspw. "order of n squared" fuer O(n^2). --Mario d 10:44, 27. Aug. 2014 (CEST)

Definition mit Limes Superior und Limes Inferior

In der Definition mit Limes Superior und Limes Inferior sehe ich nicht, wieso $g(x)\neq 0$ gelten sollte. In diesem Fall ist $|{\frac {f(x)}{g(x)}}|$ aber nicht definiert. Ich schlage vor hier die Konvention

$|{\frac {f(x)}{g(x)}}|:=0$ falls $g(x)=0$ und $f(x)=0$

$|{\frac {f(x)}{g(x)}}|:=\infty$ falls $g(x)=0$ und $f(x)\neq 0$

zu treffen. Meiner Meinung nach müsste diese Definition das gewünschte Verhalten widerspiegeln (jedenfalls bei den ersten beiden Definitionen) und auch zur Definition mit Quantoren passen. (nicht signierter Beitrag von Saibot.S (Diskussion | Beiträge) 14:25, 13. Jan. 2012 (CET))

Originale Meinung des Symbols "Omega"

Die originale Meinung des Symbols $\Omega$ ist unterschiedlich: "ist nicht ein kleines o". Dies war in 1914 von Hardy und Littlewood eingeführt (Acta Mathematica 37 (1914), S. 225), und auch von Landau benutzt ( Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137-150.). Landau auch erfund die Prototypen für $\Omega _{+}$ ("ist grösser als ein kleines o") und $\Omega _{-}$ ("ist kleiner als ein (negativ) kleines o") (er schrieb $\Omega _{R}$ und $\Omega _{L}$). Knuth kannte die H.-L. Definition, aber verstand es nicht und leider änderte es anstatt ein anderes Symbol zu wählen. Das symbol $\Omega$ ist nun systematisch in die analytische Zahlentheorie mit die originale Meinung benutzt, und NIE mit die Meinung der Artikel. Ich denke das sollte erwähnt sein (aber mein Deutsch ist nicht zu gut). Sapphorain (Diskussion) 08:11, 24. Mai 2013 (CEST)

Wenn diese andere Definition in der Zahlentheorie üblich ist, dann sollte das nicht nur unter "Geschichte" erwähnt werden, sondern es sollten die beiden üblichen Definitionen im Artikel dargestellt und gegeneinander abgegrenzt werden. Trau dich ruhig, das zu schreiben. Es wird sich schon jemand finden, der das Deutsch verbessert. --Digamma (Diskussion) 20:09, 26. Mai 2013 (CEST)

Alright then, why not! But I will do it first on the french and then english pages, for practice! Sapphorain (Diskussion) 21:12, 27. Mai 2013 (CEST)

Fachsprache für Laien unverständlich

Im ersten Absatz wird erklärt, was Landau-Symbole sind. Diese Erklärung ist für mich gut verständlich. Ohne Zweifel ist das tiefere Verstehend der verwendung von Landau-Symbolen sowieso nur möglich, wenn man sich mit der Mathematik dahinter auskennt. Ich denke allerdings, dass zumindest die Erklärung, wofür Landau-Symbole verwendet werden, auch für Laien verständlich sein sollte. Das ist noch nicht der fall, da auch im ersten Absatz technische Formulierungen benutzt werden, deren Struktur Laien gewöhnlich gänzlich unbeknnt ist, wie z.B. Einklammerungen im Sinne von "bzw.". Beispiel:

"Man nennt sie (nicht) polynomiell lösbar."

Dieser Satz soll heißen:

"Man nennt sie polynomiell lösbar bzw. nicht polynomiell lösbar."

Die Schreibweise mit Klammern ist jedoch rein in technischen Bereichen, insbesondere in der Mathematik, verbreitet. Ein Laie würde denken, dass Dinge, die in Klammern stehen, auch weggelassen werden könnten, weil sie unwichtig sind und kaum einen Unterschied machen. Das ist hier aber ganz und gar nicht der Fall. Um diesem Missverständnis vorzubeugen, sollte dieser Satz umformuliert werden.

Gleiches gilt für den Satzteil

"dessen Laufzeitzuwächse sich durch das Wachstum eines Polynoms beschränken lassen"

Ein Laie würde denken, "OK, wenn sich der Laufzeitzuwachs durch ein Polynom beschränken lässt, dann bedeutet das, dass ein Polynom dazu taugt, das zugrundeliegende Problem einfacher zu machen." Das ist aber wieder ein Missverständnis, weil "beschränken" hier mathematische Fachsprache ist, aber extrem schwer als solche zu erkennen ist. Besser wäre hier etwas in der Richtugn wie "dessen Anzahl an Elementarschritten nur z.B. quadratisch oder mit der dritten Potenz der Menge der Eingangsdaten wächst". Das ist zwar auch noch teilweise Fachsprache/Gedanken, aber besser als solche erkennbar. (nicht signierter Beitrag von 130.83.244.129 (Diskussion) 17:31, 6. Aug. 2013 (CEST))

Du kannst das einfach selbst ändern. --Digamma (Diskussion) 21:05, 6. Aug. 2013 (CEST)

Anzeigefehler im Abschnitt "Folgerung"

Da scheint etwas mit der math-align-Funktion nicht zu klappen, was wohl ein genereller Fehler ist, der mir z.B. auch in https://de.wikibooks.org/wiki/LaTeX-W%C3%B6rterbuch:_align aufgefallen ist. (Kann kein TeX und Wiki-Syntax auch nur in den für mich notwendigen Grundzügen ;-) ) --Constejo (Diskussion) 14:10, 7. Feb. 2014 (CET)

Limes superior vs. Quantoren

Bei der Beantwortung einer Frage hier auf der Disk ist mir eine Diskrepanz zwischen der Definition von ${\mathcal {O}}$ mittels des Limes superior und der angeblich äquivalenten Quantoren-Definition aufgefallen. Es geht um den (sicherlich pathologischen) Fall der konstanten Null-Funktion: Sei also $g(x)=0$ für alle $x$, dann ist für keine Funktion $f$ und kein $x$ der Quotient $|f(x)/g(x)|$ definiert und damit erst recht nicht der Limes superior für $x\to a$. Also wäre ${\mathcal {O}}(g)={\mathcal {O}}(0)$ undefiniert. Andererseits erfüllen aber alle Funktionen $f$, die lokal um $a$ verschwinden, widerpruchsfrei die Quantoren-Fassung $\exists \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :|f(x)|\leq C\cdot |g(x)|=0$ - sogar für jedes $C>0$ und daher ${\mathcal {O}}(0)=o(0)$.

Also entweder sind die beiden Definitionen eben nicht äquivalent oder man muss zumindest die pathologischen Fälle im Artikel explizit ausschließen. Was sagt denn die Literatur?

Liebe Grüße -- 2001:638:807:20D:B9DF:2F79:BAE7:4835 11:44, 30. Sep. 2015 (CEST)

"mindestens 25 Jahre falsch?"

"(auch im Jahr 1976 war es für mindestens 25 Jahre falsch[6])" im Abschnitt über die Knuth'sche Definition von Omega. Was genau war 25 Jahre lang falsch? Was soll der Verweis [6] belegen? (nicht signierter Beitrag von 160.45.40.209 (Diskussion) 13:15, 16. Nov. 2015 (CET))

[6] wurde 1951 veröffentlicht. In [6] wird das Symbol Omega systematisch im Sinne von Hardy-Littlewood eingesetzt (Kapitel VIII, "Omega-theorems"). [6] ist ein Referenzwerk in der Zahlentheorie für den Riemann Zeta-Funktion (für mindestens dreissig Jahren war dieses Buch sogar das einigste Referenzwerk für den Zeta-Funktion). [6] und seine zweite Auflage wurde in 518 Artikeln zitiert (nach Zentralblatt). Also die 1976 Knuthsche Behauptung, dass die Hardy-Littlewoodsche Definition fast nie benutzt wird, mindestens seit 1951 falsch war. Sapphorain (Diskussion) 18:22, 16. Nov. 2015 (CET)

groteske Notation

Entweder benutzt man eine Notation durchgängig, oder es zeigen sich Kontexte wo Schwierigkeiten auftreten. Dann muss man Kompromisse finden. Es können auch erst dann Schwierigkeiten auftreten, wenn ein anderes Gebiet betreten wird. Hinzu kommen persönliche Meinungen und Vorlieben, was die Sache schwierig machen kann. In den meisten Fällen sind mathematische Notationen unproblematisch. Die Probleme fangen aber bereits beim Gleichheitszeichen an. Ohne Kontext sind $x^{2}=9$ und $x^{2}-1=(x-1)(x+1)$ mißverständlich. Das erste kann eine Gleichung in der Variablen x darstellen, deren Lösungen gesucht sind oder eine für fast alle Werte x falsche Aussage. Die zweite Gleichung ist eine Identität (binomische Formel), oder eine Gleichung mit unendlich vielen Lösungen. Streng genommen würde man zwei unterschiedliche Gleichheitszeichen benötigen: Soll-Gleich und Ist-Gleich.

Jemand, der den Mengenbegriff aus verschiedenen Gründen nicht übermäßig benutzen mag, wird sich in konkreten Fällen an der Schreibweise $f(x)\in {\mathcal {O}}(g(x))$ stoßen. Sei $f(x)=3x^{2}+4x$ dann gilt $f(x)\leq C\cdot x^{2}$, $x\to \infty$. Die häufig dafür verwendete Notation $f(x)={\mathcal {O}}(x^{2})$, $x\to \infty$ ist im üblichen Kontext von Zahlentheorie unproblematisch. Im Artikel steht die Stirlingsche Formel in ihrer üblichen Notation:

$n!={\mathcal {O}}\left({\sqrt {n}}\cdot \left({\frac {n}{e}}\right)^{n}\right){\text{ für }}n\to \infty$

Die Schreibweise

$n!\in {\mathcal {O}}\left({\sqrt {n}}\cdot \left({\frac {n}{e}}\right)^{n}\right){\text{ für }}n\to \infty$

halte ich für grotesk. Wie soll das bei

$n!={\sqrt {2\pi n}}~{\left({\frac {n}{e}}\right)}^{n}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right){\text{ für }}n\to \infty$

gehen? Richtig grotest ist die Notation $f\in {\mathcal {O}}(x^{2})$. Das schafft Querverbindungen in die Diskussion, ob eine Funktion mit f oder f(z) bezeichnet werden soll. Diese Diskussion gipfelt in groteske Punkt-Notationen wie $f={\sqrt {.}}$.

Das Argument mit der fehlenden Trasitivität ist absurd. Klar, es ist nicht transitiv. Da gibt es aber noch andere Beispiele: Gleichungen sind auch nicht transitiv: aus $x^{2}=1$ und $x^{3}=1$ folgt nicht $x^{3}=x^{2}$.

Strenges Fazit. Der Artikel muss grundlegend überarbeitet und vereinheitlicht werden (z.B. durch strenge Zweiteilung der Varianten). Persönliche Meinungen müssen verschwinden (siehe TF). Evtl. muss ein Überarbeitungsbaustein gesetzt werden. Der Artikel hat auch etwas belehrendes. Man darf aber nicht belehren und dann nach unterschiedlichem Maß messen. --Skraemer (Diskussion) 22:27, 8. Dez. 2015 (CET)

Tatsächlich ist nicht der Artikel von persönlichen Meinungen gefärbt, sondern lediglich deine Anmerkung. Die einzige mathematisch korrekte Schreibweise ist die Element-Schreibweise. Dass man sich durch andere Notationen häufig das Leben erleichtert (wie in deinen Beispielen) stimmt und wird auch so im Artikel erwähnt. Das macht diese Notationen allerdings noch nicht korrekt (im Sinne von widerspruchsfrei definierbar - dann müsste nämlich nicht nur das groß-O, sondern auch das Gleichheitszeichen "umdefiniert" werden). Dass du diese Schreibweise für "grotesk" hältst ändert nichts daran.

(Im Übrigen folgt aus $x^{2}=1$ und $x^{3}=1$ sehr wohl $x^{3}=x^{2}$) --Cerotidinon (Diskussion) 13:34, 8. Feb. 2016 (CET)

Limes superior für o und w?

Im Abschnitt "Definition" steht bei ο und ω nur lim und nicht lim sup. Kann man in diesen Fällen annehmen, dass der existiert oder wurde das dort einfach vergessen? Ich weiß, dass man der Einfachheit halber meist nur lim schreibt, aber die Inkonsistenz verwirrt mich hier. (nicht signierter Beitrag von 77.179.98.134 (Diskussion) 13:22, 2. Jan. 2017 (CET))

Bei "o" könnte man auch lim sup schreiben. Aus 0 ≤ lim inf ≤ lim sup ergibt sich: Wenn lim sup = 0 ist, dann existiert der Grenzwert und es gilt lim = 0.

Bei ω könnte man entsprechend lim inf schreiben. Aus lim inf = ∞ folgt, dass lim = ∞. lim sup genügt hier nicht, das wäre eine schwächere Aussage. --Digamma (Diskussion) 17:53, 2. Jan. 2017 (CET)

„Ordnung von“

Im Artikel steht:

Der Großbuchstabe $O$ als Symbol für Ordnung von wurde erstmals vom deutschen Zahlentheoretiker Paul Bachmann in der 1894 erschienenen zweiten Auflage seines Buchs Analytische Zahlentheorie verwendet.

$O(n)$ steht bei Bachmann für „eine Grösse […], deren Ordnung in Bezug auf $n$ die Ordnung von $n$ nicht überschreitet“, nicht für die Ordnung von $n$ selbst.

Tatsächlich handelt es sich bei ${\mathcal {O}}(g(x))$ um eine Menge, welche alle diejenigen Funktionen enthält, welche höchstens so schnell wachsen wie $g(x)$. Die Schreibweise $f(x)\in {\mathcal {O}}(g(x))$ ist also formal korrekt.

So lässt sich das ${\mathcal {O}}$-Symbol natürlich umdeuten, um die Schreibweise mit dem Element-Symbol zu ermöglichen, aber Bachmann meinte das natürlich nicht so, sondern verwendete „$O(n)$“ so, wie in natürlicher Sprache „Element“ in „$x$ ist Element von $M$“ verwendet wird, nämlich indefinit: Es gibt mehrere Größen, die $O(n)$ sind, und „$f(n)=O(n)$“ besagt, dass $f(n)$ eine solche Größe ist.

Ebenso könnte geschrieben werden: $O(n)=O(n)$. Jedes $O(n)$ ist offensichtlich (ein) $O(n)$. „$O(n)\in O(n)$“ wäre im Rahmen von ZFC problematisch. -- IvanP (Diskussion) 09:10, 20. Okt. 2017 (CEST) (Bearbeitet: -- IvanP (Diskussion) 20:06, 1. Mai 2018 (CEST))

Die Aussage

Tatsächlich handelt es sich bei ${\mathcal {O}}(g(x))$ um eine Menge, welche alle diejenigen Funktionen enthält, welche höchstens so schnell wachsen wie $g(x)$. Die Schreibweise $f(x)\in {\mathcal {O}}(g(x))$ ist also formal korrekt.

bezieht sich ganz sicher nicht auf die Art, wie das Symbol von Bachmann oder Landau verwendet wurde, sondern ist eine moderne Interpretation. Es ist ganz sicher nicht gemeint, dass Bachmann oder Landau das so verstanden oder verwendet hätten.

Mir wird nicht klar, warum du "O(n)" schreibst, denn in den Klammern muss natürlich eine Funktion bzw. ein Funktionsterm stehen und keine Zahl. Oder soll das die Ordnung eines Polynoms sein? --Digamma (Diskussion) 17:23, 20. Okt. 2017 (CEST)

OK, der Kontext, in dem diese Aussage fällt, ist aber die Verwendung des Gleichheitszeichens. Mir geht es darum, dass das Gleichheitszeichen sehr wohl für Gleichheit verwendet wurde und nicht etwa „symbolisch“ für die Elementbeziehung, nur bezeichnet „$O(g(x))$“ in dem Fall keine bestimmte Größe, sondern „$f(x)=O(g(x))$“ bedeutet, dass es ein $O(g(x))$ gibt, dem $f(x)$ gleicht (!). Vergleiche mit „$G=6{,}674\;08(31)\cdot 10^{-11}\,\mathrm {\frac {m^{3}}{kg\cdot s^{2}}}$“ aus der Physik, hier ist $6{,}674\;08(31)$ eine Größe der Menge / im Intervall $[6{,}674\;08-0{,}000\;31,6{,}674\;08+0{,}000\;31]$, wobei nicht spezifiziert wird, welche. Prädikatenlogisch sauber ließe sich dies mit dem Existenzquantor ausdrücken, wer aber ganz streng sein will, müsste auch die Schreibweise „$f(x)\in O(g(x))$“ mangels expliziter Variablenbindung verwerfen; stattdessen bietet sich „$f\in O(g)$“ an.

Im Artikel steht auch:

Dies bedeutet hier „$f$ ist ein Omega von $g$“ und nicht „$f$ ist gleich ein Omega von $g$“.

Die Aussagen sind doch äquivalent, sofern „ein [!] Omega von $g$“ gleichermaßen verwendet wird. Es ist nicht das Wort „gleich“, das einen Unterschied macht, sondern die Verwendungsart von „Omega von $g$“. Im Artikel Omikron lesen wir übrigens:

In der Mathematik wurde ein großes Omikron von Paul Bachmann 1892 zur Beschreibung der Größenordnung einer Funktion verwendet. Heute ist diese Notation unter dem Namen Landau-Symbol bekannt und wird üblicherweise als lateinisches O verstanden.

Erstens wird das $O$ im 1892 erschienenen ersten Teil Die Elemente der Zahlentheorie von Bachmanns Zahlentheorie noch gar nicht verwendet; es erscheint im zweiten Teil Analytische Zahlentheorie (im Artikel Landau-Symbole steht dagegen „zweiten Auflage seines Buchs Analytische Zahlentheorie“) von 1894. Zweitens wird es aufgrund der als Landau-Symbole verwendeten griechischen Buchstaben $\Omega$, $\Theta$ und $\omega$ heutzutage zwar auch als Omikron aufgefasst, jedoch ist keineswegs ersichtlich, dass er es so auffasste; „eine Grösse […], deren Ordnung in Bezug auf $n$ die Ordnung von $n$ nicht überschreitet“ (Fettdruck von mir) deutet auf ein lateinisches O hin. -- IvanP (Diskussion) 19:36, 1. Mai 2018 (CEST)

Aber die darüber stehenden Aussagen:

"Es handelt sich dabei aber um eine rein symbolische Schreibweise und nicht um eine Gleichheitsaussage, auf die beispielsweise die Gesetze der Transitivität oder der Symmetrie anwendbar sind: Eine Aussage wie $f(x)={\mathcal {O}}(g(x))$ ist keine Gleichung und keine Seite ist durch die andere bestimmt. Aus $f_{1}(x)={\mathcal {O}}(g(x))$ und $f_{2}(x)={\mathcal {O}}(g(x))$ folgt nicht, dass $f_{1}$ und $f_{2}$ gleich sind. Genauso wenig kann man aus $f(x)={\mathcal {O}}(g_{1}(x))$ und $f(x)={\mathcal {O}}(g_{2}(x))$ schließen, dass ${\mathcal {O}}(g_{1}(x))$ und ${\mathcal {O}}(g_{2}(x))$ dieselbe Klasse sind oder die eine in der anderen enthalten ist."

sind meinern Meinung nach zweifellos richtig.

Ich würde es eher so ausdrücken, dass hier das Gleichheitszeichen im Sinne von "ist" verwendet wird, wie das auch bei der vor allem bei Physikern beliebten Schreibweise "= const." der Fall ist. Die rechte Seite ist kein mathematisches Objekt, sondern ein Prädikat. --Digamma (Diskussion) 21:11, 1. Mai 2018 (CEST)

Was mich an der eingangs erwähnten Stelle stört, ist nur, dass es zunächst um die Verwendung des Gleichheitszeichens geht und dann erwähnt wird, bei ${\mathcal {O}}(g(x))$ handele es sich „tatsächlich“ um eine Menge, ohne anzumerken, dass hier eine andere Interpretation von „${\mathcal {O}}(g(x))$“ verwendet wird. Der Grund für die Unzulässigkeit von „$f(x)=O(g(x))$“ im ursprünglichen Sinn ist nämlich nicht, dass in diesem Fall mit „$O(g(x))$“ eigentlich eine Menge gemeint ist, die $f(x)$ als Element enthält, sondern dass „$O(g(x))$“ auf eine Weise verwendet wird, die in der mathematischen Notation (streng genommen) gar nicht erst zulässig ist. Diese Verwendung ist nicht auf Gleichungen beschränkt, in natürlicher Sprache kann zum Beispiel formuliert werden: „Der Algorithmus benötigt $O(n\log n)$ Schritte.“ Ich habe in einer Vorlesung gehört, das „$=$“ heiße im Prinzip „$\in$“, was die ursprüngliche Logik hinter dem Ganzen nicht adäquat erklärt. Ansonsten siehe die weiteren Mängel; um noch einmal diese Stelle aus dem Artikel aufzugreifen:

Dies bedeutet hier „$f$ ist ein Omega von $g$“ und nicht „$f$ ist gleich ein Omega von $g$“.

Nehmen wir ein anderes Beispiel: Wenn 2 eine Primzahl ist, so können wir doch auch sagen, dass 2 gleich einer Primzahl ist, d. h.: $\exists x\in \mathbb {P} (2=x)$. Ebenso ist 3 gleich einer Primzahl, allerdings gleicht 2 einer anderen Primzahl als 3, drum folgt auch nicht $2=3$. In der deutschen Sprache gibt es Bezeichnungen wie Primzahl, die Oberbegriffe für mehrere mathematische Objekte sind. Eine Primzahl ist ein mathematisches Objekt, allerdings kann jedes der Objekte 2, 3 und 5 (zum Beispiel) gleichermaßen als eine Primzahl bezeichnet werden. In der mathematischen Notation ist das standardmäßig nicht so, ein Symbol à la „${\sqrt {2}}$“ hat in diesem Rahmen zwangsläufig einen festen Referenten; unter Umständen ist es nicht wohldefiniert, zum Beispiel ist bei den affin erweiterten reellen Zahlen unklar, ob $1/0$ nun $+\infty$ oder $-\infty$ ist, auf jeden Fall können wir aber nicht widerspruchsfrei behaupten, dass $+\infty$ und $-\infty$ beide $1/0$ sind.

Nun gibt es eben Fälle, bei denen von der Norm abgewichen wird, etwa wenn ein Ingenieur (kein Mathematiker!) schreibt:

${\begin{aligned}x^{2}&=4\\x&={\sqrt {4}}\\x&=\pm 2\end{aligned}}$

Wie das verstanden werden kann: 4 hat zwei Quadratwurzeln, +2 und −2. „$x={\sqrt {4}}$“ soll heißen, dass $x$ einer davon gleicht. (Schon klar, standardmäßig steht „${\sqrt {4}}$“ für die nichtnegative Wurzel. Es könnte dann „$|x|={\sqrt {4}}$“ und „$x=-2\lor x=2$“ geschrieben werden.)

Zur Omikron-Geschichte sei noch angemerkt, dass $O$ (lateinischer Buchstabe) im Gegensatz zu $\Omega$ und $\Theta$ (griechische Buchstaben) geneigt ist. Im Buch Concrete Mathematics, in dem sich am Rand die Bemerkung

Since $\Omega$ and $\Theta$ are uppercase Greek letters, the $O$ in $O$-notation must be a capital Greek Omicron.

After all, Greeks invented asymptotics.

findet, wird für Landau-Symbole allerdings die Schrift AMS Euler verwendet, da passt es wieder zusammen. -- IvanP (Diskussion) 21:27, 5. Mai 2018 (CEST)

Wie ich sehe, heißt die Abhandlung Die analytische Zahlentheorie (mit bestimmtem Artikel), ich habe den WP-Artikel mal angepasst. In ISO 80000-2:2009 werden O und o jedoch aufrecht geschrieben. Umseitig wird bereits ${\hbox{o}}$ verwendet, wobei sich auch kursive Vorkommnisse des Kleinbuchstabens fanden (die ich ersetzt habe). Sollte der Einheitlichkeit halber dann auch $O$ in der ersten Tabelle durch ${\hbox{O}}$ ersetzt werden, was meinst du, Digamma? Es könnten auch beide Schreibweisen genannt werden (und ${\mathcal {O}}$ natürlich), dann würde ich aber auch $o$ unterbringen.

Leider gibt es bei uns \omega nur kursiv, soweit ich weiß. In manchen Artikeln wird „$\mathrm {d} x$“ geschrieben, dafür erscheint das Integralzeichen $\int$ kursiv (in besagter ISO-Norm sind sowohl d als auch das Integralzeichen aufrecht!). Interessant: $\oiint$, $\oiiint$ (autsch; noch ein Versuch: $\oiiint \ \$) und $\varointclockwise$ erscheinen mit aufrechtem Integralzeichen, $\oint$ nicht. Falsch erscheinen \varcoppa ($\mbox{\coppa}$) und \omicron ($\mathrm {o}$ – müsste als griechischer Kleinbuchstabe kursiv sein), \mathit\Lambda (${\mathit {\Lambda }}$) wird anders dargestellt als \Lambda ($\Lambda$). -- IvanP (Diskussion) 01:42, 12. Aug. 2018 (CEST) (Bearbeitet: -- IvanP (Diskussion) 21:39, 12. Aug. 2018 (CEST))

Ich denke nicht, dass dies hier die richtige Stelle ist, um allgemein mathematische Typographie zu diskutieren. Konkret zu den Landau-Symbolen: Ich habe die noch nie aufrecht gesehen. Man sollte schauen, was in mathematischer Literatur üblich ist, nicht, was in der ISO-Norm steht. Nur kurz zum Integralzeichen: Ich bezweifle, dass die ISO-Norm den Anspruch hat, die Form des Integral-Zeichens festzulegen. Das ist vermutlich einfach die Form, die im entsprechenden Formelsatz vorhanden ist. --Digamma (Diskussion) 09:59, 12. Aug. 2018 (CEST)

Kleines kalligraphisches o

@RPI: Du hast ohne Kommentar an einer Stelle das einfache kleine o durch ein kalligraphische Version ersetzt. Gibt es dafür Belege? --Digamma (Diskussion) 20:25, 9. Apr. 2019 (CEST)

Ich erinnere mich, das so schon gesehen zu haben, allerdings ist das schon lange her. Einen Beleg dafür habe ich im Internet leider nicht gefunden und in absehbarer Zeit werde ich auch nicht dazu kommen, in einer Uni-Bibliothek nachzusehen.

Aber wenn man schon ${\mathcal {O}}$ benutzt, dann wäre es konsequent auch ${\begin{smallmatrix}\!{\mathcal {O}}\!\end{smallmatrix}}$ zu schreiben. Viele Leute scheinen wohl nur ${\mathcal {O}}$ zu kennen oder sie meinen, es wäre besser, dies so zu schreiben, um kenntlich zu machen, dass es sich hier nicht um einen Operator handelt. Das macht aber nur dann Sinn, wenn die restlichen Landau-Symbole auch kalligraphisch geschrieben werden. Da es aber in der Regel für letztere an kalligraphischen Zeichen fehlt, kommt ein sinnloser Mischmasch heraus. Meiner Meinung nach wäre es daher am besten, im Artikel nur einmal kurz auf die verbreitete ${\mathcal {O}}$-Variante hinzuweisen, aber sonst ausschließlich die originären $O$- und $o$-Varianten zu benutzen. --RPI (Diskussion) 16:55, 11. Apr. 2019 (CEST)

Dies ist jedoch nicht unsere Aufgabe, die beste Schrift für o in Wikipedia zu bestimmen. Wenn das kleine kalligraphische o in der Literatur nicht verwendet ist, hat es in diesem Artikel nichts zu tun. Und wenn es nur selten verwendet ist, darf es nicht das andere kleine o ersetzen. Sapphorain (Diskussion) 18:18, 11. Apr. 2019 (CEST)

Knuth'sche Definition: Satz über vorherige Benutzung.

Der Zusatz in Klammern bietet imo keinen enzyklopädischen Mehrwert. Zuvor stand dort "oft", was impliziert hätte, dass Knuth mit seiner Aussage falsch lag. Nach Diskussion mit @user:Sapphorain wurde "oft" entfernt. Nun fehlt aber der Bezug zu dem Satz davor, da Knuth ja nie bestritten hat, dass die Definition schon mal benutzt wurde, sondern lediglich, dass sie oft benutzt wird. --Cerotidinon (Diskussion) 03:30, 29. Aug. 2019 (CEST)

Möglicherweise möchten Sie den Satz umformulieren, aber den Verweis auf Titschmarsh's Buch, das ein Nachschlagewerk ist, nicht vollständig löschen. Sapphorain (Diskussion) 08:31, 29. Aug. 2019 (CEST)

Was ist der enzyklopädische Mehrwert/die Aussage dieses Satzes an dieser Stelle? Bitte auf das, was ich oben geschrieben habe, eingehen. Dass ein Buch ein Nachschlagewerk ist, ist in keiner Hinsicht eine Rechtfertigung, dass es an dieser Stelle von irgendeiner Relevanz ist. --Cerotidinon (Diskussion) 18:21, 29. Aug. 2019 (CEST)

Dieses Nachschlagewerk von 1951, das allen Zahlentheoretikern bekannt ist und regelmäßig neu aufgelegt wird, enthält ein ganzes Kapitel über Omega-Theoreme. Seit diesem Buch wird in der analytischen Zahlentheorie systematisch das Omega-Symbol verwendet. Das heißt a fortiori oft (aber da es Sie stört, werden wir es nicht erwähnen). In jedem Fall ist es absolut legitim, dieses Buch hier zu erwähnen. Sapphorain (Diskussion) 08:58, 30. Aug. 2019 (CEST)

Wenn es für sich hohe Relevanz hat, dann sollte das Buch bei der Hardy-Littlewood'schen Definition stehen und nicht in dem Absatz über Knuths Definition. So wirkt der Abschnitt meinungsbehaftet, da ohne Anlass Knuth widersprochen wird, bzw. suggestiv auf eine Verwendung einer anderen Quelle hingewiesen wird. Wenn es eine Quelle gibt, die belegt, dass Hardy-Littlewood weitreichend Anwendung gefunden hat, dann kann diese dort eingefügt werden. --Cerotidinon (Diskussion) 09:14, 30. Aug. 2019 (CEST)

Im Gegenteil, ich denke immer noch, dass die Erwähnung von Titschmarsh's Buch hier durchaus angebracht ist. (Nichts hindert sie daran, auch im vorherigen Abschnitt erwähnt zu werden.) Weil erwähnt Knuth es in seinem Artikel ("The most prominent appearance of this notation is in Titchmarsh’s magnum opus on Riemann’s zeta function, where he defines \Omega(f(n)) on p. 152 and devotes his entire Chapter 8 to « \Omega-theorems »."), und behauptet trotzdem, dass die Notation so gut wie nie verwendet wird. (Nachdem er sogar behauptet hatte, Landau habe es nie benutzt, was offensichtlich falsch ist). Sapphorain (Diskussion) 09:05, 31. Aug. 2019 (CEST)

Dann hat Knuth hier offensichtlich eine andere Auffassung. Ich verstehe, dass man der Meinung sein kann, dass Knuth falsch liegt, aber persönliche Meinungen haben in einem Wikipedia-Artikel nichts zu suchen. Und die Referenz belegt nicht, dass Knuth falsch liegt, sondern ist lediglich ein Vorwand, um ihm in diesem Abschnitt zu widersprechen. Man könnte den Satz gleichsam so formulieren, dass Knuth dieser Auffassung war, obwohl ihm die Verwendung bei Titchmarsh bekannt ist, wodurch ebenfalls das Standardwerk zitiert wird. Wäre das genauso zufriedenstellend in Ordnung? Dadurch wird zumindest der Bezug zu dem Abschnitt gewahrt, aber ein komplett gegenteiliger Eindruck vermittelt. --Cerotidinon (Diskussion) 00:21, 1. Sep. 2019 (CEST)

In diesem Fall sollten wir auch Knuths Aussage erwähnen, dass Landau das Omega-Symbol nie benutzt hat. Dies ist objektiv falsch (E. Landau, "Über die Anzahl der Gitterpunkte in Gewissen Bereichen, IV", Nachr Gesell, Wiss Gött, Math-Phys Kl, 1924, S. 137-150). In diesem Fall handelt es sich nicht um eine persönliche Meinung: Knuth ist objektiv falsch. (Meine persönliche Meinung ist, dass Knuth den Artikel von Landau im Übrigen genau kannte, aber das ist nicht objektiv, und das werde ich im Artikel nicht sagen …). Sapphorain (Diskussion) 08:48, 2. Sep. 2019 (CEST)

Diese Aussage ist wohl tatsächlich falsch, das ist aber nicht die Aussage aus dem Artikel. Wenn du darstellen kannst, dass das enzyklopädische Relevanz hat, dann schreibe dazu, dass Knuth meinte, dass Landau das nie benutzt hat, das aber nicht stimmt (jeweils mit Belegen). Allerdings kommt mir das trotzdem mehr wie eine persönliche Meinung vor, da es an der Grundaussage von Knuth nichts ändert, wenn er in diesem einen Fall falsch lag. Besser wäre eine offizielle Quelle, die ihn in einer Grundaussage kritisiert. Ich bin daher stand jetzt immer noch für eine ersatzlose Löschung. --Cerotidinon (Diskussion) 16:52, 2. Sep. 2019 (CEST)

Ich habe den Text geändert. Sapphorain (Diskussion) 16:58, 3. Sep. 2019 (CEST)

Jetzt geht es eher in die Richtung, obwohl ich die Relevanz immer noch nicht wirklich sehe und die Formulierung auch immer noch tendenziös ist. Bei kurzem Durchblättern der Quelle zu Landau (die sich übrigens auf Seite 210:243 befindet) habe ich allerdings (wie Knuth ;-) ) keine einzige Verwendung finden können. Bitte um genauen Verweis auf die Seite. --Cerotidinon (Diskussion) 20:35, 3. Sep. 2019 (CEST)

Der Artikel ist in seinen gesamten Werken wiedergegeben (Thales Verlag, Bd. 8, S. 145-158). Die Symbole Omega_R und Omega_L von Hardy-Littlewood werden in der Aussage des Hauptsatzes S. 148 definiert und verwendet. Das Symbol Omega ohne Index wird in der Demonstration S.149 definiert und verwendet. Sapphorain (Diskussion) 11:24, 4. Sep. 2019 (CEST)

Tabelle in Beispiele und Notation könnte man durch Diagramme grafisch ergänzen

In der Tabelle bei Landau-Symbole#Beispiele_und_Notation wäre es sinnvoll, wenn man zu jeder Notation (also jeder Zeile) noch eine kleine Diagrammgrafik hinzufügt, bei der auf der x Achse ein Ansteigen von n dargestellt wird und auf der Y Achse der Aufwand. Damit wäre grafisch sofort ersichtlich, warum die eine Notation besser ist, als die andere ist. --93.229.166.182 07:15, 21. Sep. 2024 (CEST)

Ich habe mal den Anfang mit Gnuplot gemacht. Die Funktionen müsste jemand einzeln in eine Bilddatei plotten und dann als Bilder online stellen, so dass man sie in die Tabelle einbauen kann. Als IP geht das Onlinestellen von Bildern nicht.

Für den gnuplot Code gebe ich keine Gewähr auf Richtigkeit, wer Fehler findet, kann aber gerne helfen sie zu korrigieren.

Die O(n^m) Funktion (im Code f8(x) genannt) habe ich auskommentiert, da x**x nicht das gleiche ist wie n**m und ich leider keine Entsprechung für m gefunden habe. Man könnte eventuell z nehmen, aber dann wird es dreidimensional und unschön für den Rest.

Die Funktion "O(A(n))" (im Code f11(x)) ist ebenfalls auskommentiert, da ich nicht weiß, wie ich programmtechnisch die modifizierte Ackermannfunktion in gnuplot implementieren soll. Soweit geht mein Wissen über gnuplot leider nicht. Wer von gnuplot mehr Ahnung hat, kann das gerne umsetzen.

Hier der Code für Gnuplot:

 set logscale y 10
 set samples 100
 set xrange [ 0.00000 : 100.00 ] noreverse writeback
 set yrange [ 0.100000 : 10000.0000 ] noreverse writeback
 set title "O-Notation"
 set xlabel "n" 
 set ylabel "Aufwand" 
 f1(x)=1
 f2(x)=log(log(x))
 f3(x)=log(x)
 f4(x)=sqrt(x)
 f5(x)=x
 f6(x)=x * log(x)
 f7(x)=x**2 
 #f8(x)=x**x  # TODO gesucht O(n^m)
 f9(x)=2**x
 f10(x)=(int(x)==0) ? 1.0 : int(x) * f9(int(x)-1.0)
 # f11(x)=   # TODO gesucht O(A(n))
 # f11(x)=(x>=1) ? 2*x : 2
 plot\
   f1(x) title "O(1)",\
   f2(x) title "O(log log n)",\
   f3(x) title "O(log(n)",\
   f4(x) title "O(sqrt(n))",\
   f5(x) title "O(n)",\
   f6(x) title "O(n log(n)",\
   f7(x) title "O(n^2)",\
   f9(x) title "O(2^n)",\
   f10(x) title "O(n!)" lc "gray70"
 #  f8(x) title "O(n^m)",\
 # f11(x) title "O(A(n))"
 #    EOF

Die Farben kann man mit dem Gnuplot Befehl lc gegebenenfalls anpassen. Hier gibt es eine Farbtabelle zu Gnuplot. --93.229.166.182 10:50, 21. Sep. 2024 (CEST)