Facebook
Twitter
Google+
Kommentare
17

O-Notation – Akademischer Tag 1

Als ich in der Ideenschmiede den Vorschlag O-Notation gelesen habe, habe ich es fast nicht glauben können und schon vermutet, ich kenne ein PHP Feature namens O-Notation noch nicht. Doch es handelt sich wirklich um die mathematische O-Notation (oder Landau-Notation), die mit diesem Artikel auf Nils Wunsch hin den Blog auch mit etwas theoretischem Background erweitern soll.

Also was ist dieses \mathcal O nun?

f(n)= \mathcal O(g(n)) \longleftrightarrow \exists c, n_0 \geq 1 \: \: \forall n \geq n_0 \: \:  (f(n) \leq c \cdot g(n))

Doch keine Angst, es ist wesentlich einfacher als es aussieht. Die O-Notation gibt an, wie komplex ein Algorithmus oder Codestück ist und wie es skaliert.
Ein klassisches Beispiel ist der BubbleSort Algorithmus, der ein Array von Zahlen sortiert. Er hat eine Komplexität von \mathcal O(n^2). Das heißt, wenn das zu sortierende Array eine Größe n hat, dann benötigt BubbleSort nicht mehr als n^2 Vergleichsschritte im Worst-Case, um das Array zu sortieren. Gezählt werden hier die Vergleichsschritte, da diese am meisten Ressourcen benötigen (im Gegensatz zum Schreiben/Lesen des Arrays) und damit die Skalierung am stärksten beeinflussen. Der derzeit beste vergleichsbasierte Sortieralgorithmus hat übrigens eine Komplexität von \mathcal O(n \cdot log(n)). Wenn jemand etwas Schnelleres programmieren kann (und den bestehenden Beweis dazu widerlegen kann), veröffentlicht Nils sicher gerne einen Artikel im Blog ;)

Zusätzlich vereinfacht die O-Notation die Angabe der Komplexität. Nehmen wir einmal an, ein Algorithmus benötigt 4 \cdot n^2 + n + 5000 Vergleichsschritte. Die O-Notation beschreibt dabei die Skalierung (in der theoretischen Informatik Wachstum genannt) und betrachtet daher nur die am schnellsten wachsenden Bereiche. So kann auch bei 4 \cdot n^2 + n + 5000 Vergleichen von \mathcal O( n^2 ) gesprochen werden, da bei einem großen n das n^2 am schnellsten wächst  und somit der Rest nicht mehr ins Gewicht fällt. Die Konstanten, die weggelassen werden können, haben in der Realität aber sehr wohl eine Bedeutung, da z.B. ein +1000000 Vergleiche (fällt in der O-Notation als Konstante weg) in der praktischen Welt trotzdem zu Buche schlägt.

Natürlich kann in dem O alles mögliche stehen und so gibt es natürlich auch \mathcal O(log(n)) < \mathcal O(n) < \mathcal O(n \cdot log(n)) < \mathcal O(n^2) < \mathcal O(n^3) < \mathcal O(2^n) < \mathcal O(n!) und viele mehr. Die beste Komplexität ist \mathcal O(1). Dies bedeutet, dass der Algorithmus in konstanter Zeit läuft, egal wie groß das n ist bzw. wie viele Elemente durch den Algorithmus behandelt werden. Beispiel wäre hierzu eine Suchfunktion mit der Hilfe einer Hashtabelle. Egal wie viele Elemente die Hashtabelle beinhaltet, für die Suche muss nur einmal die Hashfunktion berechnet und sonst keine Elemente mehr verglichen werden.

Vielen InformatikstudentInnen liegt vermutlich noch der Satz des Professors “Welche Komplexität hat dieser Algorithmus, schreiben Sie das in der O-Notation einmal auf” im Nacken. Der Grund dafür ist jedoch nicht die Schwierigkeit der O-Notation an sich, sondern der Hintergrund. Um die O-Notation angeben zu können, muss man den Algorithmus verstehen und seine Komplexität abschätzen können. Leider denken viele Programmierer nicht über ihren eigenen Code nach und so werden einzelne Algorithmen oft zum schlecht skalierenden Flaschenhals. Ich bin der Meinung, dass auch in Zeiten von Profilern der Code mit Köpfchen erstellt werden sollte. Es kann also nicht schaden, wichtige Algorithmen ein paar Minuten zu analysieren und sich einmal zu überlegen, welche Komplexität denn wirklich dahinter steckt.

Warum brauche ich nun dieses komische \mathcal O?

  • Man kann vergleichen und verglichen werden. Im wissenschaftlichen Bereich ist es üblich, die Komplexität von neu entwickelten Algorithmen anzugeben um die Algorithmen vergleichbarer zu machen.
  • Man befasst sich mit eigenen Algorithmen oder Abläufen und entdeckt so Fehler oder Verbesserungen
  • Man lernt Einschätzungen zur Skalierung zu machen
  • Man steht nicht unwissend da, wenn jemand einmal die O-Notation erwähnen sollte
  • Und eigentlich der wichtigste Grund für den modernen Programmierer von Heute: Man kann mit seinem Wissen imponieren ;)

Zum Imponieren hier auch noch ein paar Begriffe zum googlen, die man unbedingt benötigt, um im Komplexitäts-Bullshit-Bingo zu bestehen:

  • \mathcal O / \Omega / \Theta – Notation
  • Linear Speedup Theorem
  • Asymptotische Laufzeitkomplexität
  • Super- und Hyperexponentielle Komplexität
  • O-Kalkül
  • Landau-Symbole
  • Definition des asymptotischen Maßes mit Limites
  • Univariate Funktionen

Natürlich gibt es noch ganze Bücher hinter der O-Notation und ihrem mathematischen Hintergrund (siehe auch Bullshit-Bingo Liste). Dies würde aber natürlich den Rahmen dieses Blogs sprengen und so verabschiede ich mit NP \neq P ?

Weiterführende Links:

http://www.linux-related.de/index.html?/coding/o-notation.htm
http://de.wikipedia.org/wiki/O-Notation
http://en.wikipedia.org/wiki/Big_O_notation
http://de.wikipedia.org/wiki/Komplexitätstheorie
http://mathworld.wolfram.com/AsymptoticNotation.html

Über den Autor

Wolfgang Gassler

Wissenschaftlicher Mitarbeiter in der Forschungsgruppe Datenbanken und Informationssysteme an der Universität Innsbruck. Web-Entwickler seit über 10 Jahren - mit PHP3 groß geworden.
Kommentare

17 Comments

  1. Ich habe das ganze zwar schon alles einmal in der Uni gehört, ist aber trotzdem schön es mal wieder ein wenig aufgefrischt zu haben. Danke dafür.

    Reply
  2. Die Aussage “Der derzeit beste vergleichsbasierte Sortieralgorithmus hat übrigens eine Komplexität von O(n*log(n))” suggeriert, dass es vergleichsbasiert besser gehen könnte.

    Bevor hier tatsächlich noch jemand versucht, einen schnelleren Algorithmus zu finden:

    Jeder deterministische Sortieralgorithmus, der auf paarweisen Vergleichen von Schlüsseln basiert, benötigt zum Sortieren einer n-elementigen Liste von Elementen sowohl im Worst-Case als auch im Average-Case (bei Gleichverteilung) Omega(n*log(n)) Vergleiche.

    Diese Abschätzung bezieht sich auf alle möglichen (vergleichsbasierten) Sortierverfahren, bekannte wie noch nicht unbekannte.

    Reply
  3. Danke für den Artikel!
    Übrigens zur Aussage mit dem besten _vergleichsbasierten_ Sortieralgorithmus: Die Implikation, dass es noch andere Sortieralgorithmen gibt außer vergleichsbasierte ist korrekt, man kann auch anders sortieren (und dann auch durchaus in O(n), zum Beispiel mit dem RadixSort)! Dazu muss man allerdings einige Bedingungen erfüllen und benötigt mehr Speicher. Interessante Lektüre zu Algorithmen und IT-Themen aller Art (unbedingt anschauen!):

    http://www.stefan-baur.de/index.contents.0.html

    Reply
  4. Passt gut, am Dienstag schreiben wir Algorithmen/Datenstrukturen Klausur und genau das ist eins der Themen.
    Du könntest allerdings noch anhand einer geschachtelten Schleife demonstrieren, wie das in einem einfachen Beispiel berechnet wird.

    Reply
  5. ALso ich als Nicht-Informatik-Studierter komme da schon ein wenig ins Schleudern :) Schön zu wissen, dass es das gibt und das es seine Berechtigung hat, aber anfangen kann ich damit jetzt erstmal gar nichts ;)

    Ist aber auch mal interessant zu sehen, was denn so bei Theoretischer Informatik unterrichtet wird.

    Reply
  6. Hallo,
    der Beitrag hat mir gut gefallen! Einblicke in die theoretische Informatik finde ich sehr interessant. Vor Allem die Begriffe und die weiterführenden Links find ich klasse! So kann ich noch ein wenig mein Imponiergehabe ausbauen ;) :P

    Ich hoffe den “Akademischen Tag” gibt es in Zukunft öfter.

    Viele Grüße
    n3or

    Reply
  7. Ich habe mich schon öfter gefragt, wie das funktioniert und was dieses O eigentlich genau bedeutet. Jetzt bin ich schlauer. Vielen Dank für diesen super Artikel.

    Reply
  8. Super Artikel! Schlage mich damit gerade im Studium rum und freue mich auch mal soetwas in einem Blog zu lesen.

    Über eine kleinen Einführung in Sachen LaTeX würde ich mich sehr freuen.

    Reply
  9. Sehr fein zu lesen ! Aber vorallem klasse ums in der Firma rumzuschicken das man endlich “O(n)” sagen kann und nichtmehr erklären muss was gemeint ist.

    Super geschrieben

    Reply
  10. Super Artikel! Nur leider ist das Latex-Plugin deaktiviert, so dass er nicht ganz so einfach zum Lesen ist…

    Reply
  11. Geht nur mir das so, oder Fehlt dem Blog ein Parser-Plugin ([latex])? Ich kann die Funktionen so jedenfalls nicht lesen. :-/

    Reply

Leave a Comment.

Link erfolgreich vorgeschlagen.

Vielen Dank, dass du einen Link vorgeschlagen hast. Wir werden ihn sobald wie möglich prüfen. Schließen