Big ‚O‘ Notation

In diesem Blogpost berichte ich über das Big ‘O’ Notation. Ich konnte kein anderes Thema für diesen Monat finden und habe deshalb Google nach Themen gefragt. Da bin ich auf Big ‘O’ Notation gestossen und obwohl ich das Thema schon kenne, gibt es immer noch vieles neues zu lernen.

Zuerst beantworte ich mal die Frage: Was ist die Big ‘O’ Notation überhaupt? Die Big ‘O‘ Notation wird in der Informatik verwendet, um die Laufzeitkomplexität eines Algorithmus zu beschreiben. Anders beschrieben ist die Big ‘O’ Notation eine mathematische Notation, die beschreibt, wie lange eine Algorithmus braucht, um ausgeführt zu werden. Damit kann man die Effizienz eines Algorithmus mit verschiedenen Ansätzen vergleichen. 

Die Laufzeitkomplexität wird im Bit ‘O’ Notation folgendermassen ausgedrückt:

• Es ist schwierig die genaue Laufzeit eines Algorithmus zu bestimmen. Sie hängt nämlich von der Geschwindigkeit des Computerprozessors ab. Anstatt also direkt über die Laufzeit zu sprechen, verwenden wir die Big ‘O’ Notation, um auszudrücken, wie schnell die Laufzeit wächst.
• Würden wir unsere Laufzeit direkt messen, könnten wir unsere Geschwindigkeit in Sekunden und Minuten angeben. Da wir messen, wie schnell unsere Laufzeit zunimmt, müssen wir unsere Geschwindigkeit in Bezug auf etwas anderes ausdrücken. Bei der Big ‘O’ Notation verwenden wir die Größe der Eingabe, die wir „n“ nennen. Wir können also sagen, dass die Laufzeit „in der Größenordnung der Eingabe“ (O(n)) oder „in der Größenordnung des Quadrats der Eingabe“ (O(n²)) wächst.
• Ein Algorithmus kann Schritte enthalten, die teuer erscheinen, wenn n klein ist, aber schließlich durch andere Schritte in den Schatten gestellt werden, wenn n größer wird. Bei der Analyse in der Big-’O’ Notation interessieren wir uns mehr für die Dinge, die am schnellsten wachsen, wenn die Eingabe größer wird, da alles andere schnell in den Hintergrund tritt, wenn n sehr groß wird.