O Notation



  • Hallo zusammen,

    ich beschäftige mich gerade mit Komplexitätsklassen und habe damit so meine Schwierigkeiten. Momentan gehts um die O - Notation, die ja den maximalen wachstum einer Funktion angibt. Nun habe ich folgenden Satz gelesen:

    Algorithmus A ist aus O(n), dann ist der Algorithmus ebenso aus O(2*n) und O(n^2) oder O(n*m) usw.

    Wenn A maximal linear also mit n steigt, warum ist er dann auch aus n^2? Dann würde er ja nicht maximal mit n steigen???

    Könnt ihr mir helfen?

    Vielen Dank
    lg, freakC++


  • Mod

    Die Angabe ist eine Obergrenze.

    Nochwas: O(2*n) macht keinen Sinn. Ist das von dir selber ausgedacht?



  • Da gibt es nicht viel zu sagen. Guck Dir halt die Definition an:

    http://de.wikipedia.org/wiki/Landau-Symbole

    Wie Du siehst, gibt es verschiedene Landau-Symbole, die alle etwas unterschiedliches aussagen. Möglicherweise hast Du an ein anderes gedacht. An das große Theta oder so.



  • Ganz anderes Beispiel:

    Wenn ich in der Klasse der Noch-Nicht-Volljährigen bin, bin ich dann auch in der Klasse Unter-30-Jährigen?



  • SeppJ schrieb:

    Nochwas: O(2*n) macht keinen Sinn. Ist das von dir selber ausgedacht?

    Wieso macht das keinen Sinn? f(n) ist in O(g(n)) wenn ab einem bestimmten n gilt f(n) <= c*g(n) für eine geeignete Konstante c. Warum genau darf g(n) nun nicht 2*n sein?


  • Mod

    Jester schrieb:

    SeppJ schrieb:

    Nochwas: O(2*n) macht keinen Sinn. Ist das von dir selber ausgedacht?

    Wieso macht das keinen Sinn? f(n) ist in O(g(n)) wenn ab einem bestimmten n gilt f(n) <= c*g(n) für eine geeignete Konstante c. Warum genau darf g(n) nun nicht 2*n sein?

    Es darf, aber es ist eine unnötige Zusatzangabe ohne jeden Mehrwert. Wenn man sie verwendet, deutet dies darauf hin, dass man die Notation nicht verstanden hat. Alle O(m*n) sind äquivalent (außer m=0).



  • Hallo,

    danke für eure Antworten und Beispiele.

    Wenn ein Algorithmus aber maximal linear steigt und er aber auch O(n^2) angehört, dann würde doch die Obergrenze nach oben verschoben, weil n^2 größert ist als n.

    Das verstehe ich nicht, denn n^2 und n sind zwei unterschiedliche Größen und wenn ich unter n bin, dann kann ich nicht zwischen n und n^2 sein.

    Wo liegt mein Denkfehler?

    Vielen Dank
    lg, freakC++



  • freakC++ schrieb:

    Das verstehe ich nicht, denn n^2 und n sind zwei unterschiedliche Größen und wenn ich unter n bin, dann kann ich nicht zwischen n und n^2 sein.

    Wo liegt mein Denkfehler?

    O(n^2) heißt nicht "zwischen n und n^2", sondern nur "unter c*n^2 für alle n größer einem n_0(c)".



  • wenn es unter n^2 ist, dann kann es aber noch immer über n sein und daher über O(n), obwohl letztes die Obergrenze ist, oder?

    Vielen Dank
    lg, freakC++



  • Man ist aber nicht an der Obergrenze interessiert. Deswegen ist es sinnlos zu sagen, dass Suchen eines Elements in einer List in O(2n) liegt. Das ist zwar korrekt, aber voellig unnuetz. Es spielt einfach keine Rolle, was man so alles sagen kann, wenn der Tag lang ist ...



  • freakC++ schrieb:

    wenn es unter n^2 ist, dann kann es aber noch immer über n sein und daher über O(n), obwohl letztes die Obergrenze ist, oder?

    Ja. Mit O(n^2) gibst Du praktisch eine schwächere Obergrenze als mit O(n) an. Deswegen legt O(n^2) aber immer noch _eine_ Obergrenze für den Algorithmus fest.



  • knivil schrieb:

    Man ist aber nicht an der Obergrenze interessiert.

    Ich dachte, dass das genau der Sinn der O Notation ist. Hä??

    Ich habe den Eindruck, dass ich immer weniger verstehe....

    Vielen dank
    lg, freakC++



  • freakC++ schrieb:

    knivil schrieb:

    Man ist aber nicht an der Obergrenze interessiert.

    Ich dachte, dass das genau der Sinn der O Notation ist. Hä??

    Ich habe den Eindruck, dass ich immer weniger verstehe....

    Die O-Notation ist letztlich durch ein paar Ungleichungen definiert, also gibt die Frage nach "der" Obergrenze recht wenig Sinn. Du suchst stattdessen eine möglichst kleine obere Schranke.

    Das ist wie bei allen Ungleichungen. Angenommen, Du hast festgestellt, daß x < 5 ist. Jetzt kannst Du natürlich hergehen und auch feststellen, daß immer x<10 ist. Oder x<10^234. Oder x aus ganz R. Alles richtig. Aber dein Ziel war es ja, möglichst präzise anzugeben, wie sich x wirklich verhält und genau so ist es bei der O-Notation. Du kannst natürlich einen linearen Verlauf erst mal durch einen exponentiellen Verlauf abschätzen. Ist halt reichtlich konservativ und wenn Du Leute davon Überzeugen willst, deinen Algorithmus tatsächlich zu verwenden (also für Sachen, wo das asymtpotische Verhalten wirklich interessant ist), dann solltest Du dir bessere Argumente einfallen lassen.



  • Wie schon geschrieben wurde gibt man mit dem O eine mögliche Obergrenze an, dass muss aber weder die kleinste, noch eine besonders gute Grenze sein. In der Komplexitätstheorie ist das aber auch oft gar nicht nötig besonders gute Grenzen zu haben.

    So ist z.B. eine Laufzeit von O(n^k), mit einem von der Eingabelänge unabhängigen k, polynomiell. Wenn man nun zeigen will das ein Problem in P liegt, reicht es einen Algorithmus zu finden der diese Laufzeit für ein beliebiges k hat.

    Und auch hier gibt es das gleiche Prinzip. Wenn es einen Algorithmus gibt, der das Problem in polynomieller Zeit löst, dann gibt es auch einen der dafür Exponentielle Zeit benötigt. Langsamer machen geht immer.


Log in to reply