O-Notation Vergleich

Worum geht es?

Die O-Notation beschreibt das asymptotische Wachstumsverhalten von Algorithmen. Sie sagt nicht, wie lange ein Algorithmus konkret läuft, sondern wie sich die Laufzeit mit wachsender Eingabe n entwickelt.

Diese Formel berechnet exemplarisch den Wert von O(log n) = log₂(n) und stellt ihn den anderen Klassen gegenüber.

Die Formel

OLogN = log₂(n)

Umstellung:
    n = 2^OLogN

Die Variablen

Minimal-Beispiel

Wie viele Operationen für n = 1024 bei O(log n)?

OLogN = log₂(1024)
      = 10 Ops

Praxis-Beispiele

Beispiel 1 — Klassenvergleich für n = 1000

O(1)        =                 1
O(log n)    ≈    log₂(1000) ≈ 10
O(n)        =              1 000
O(n log n)  ≈  1000 · 10  ≈ 10 000
O(n²)       =          1 000 000

Beispiel 2 — Eingabegröße rückwärts

Wie groß war n, wenn O(log n) = 20 Ops ergab?

n = 2^20
  = 1 048 576

Beispiel 3 — Verdopplung der Eingabe

Verdoppelt sich n von 1024 auf 2048:

log₂(1024) = 10
log₂(2048) = 11

Zuwachs: nur +1 Operation.