Was bedeutet: O(n), O(n)², O(log n)?

Ich bin kein Mathematiker, aber stoße immer wieder die oben genannten und weitere ähnliche Angaben.

Was bedeuten die?

Damit wird ja meistens angegeben, wie lange eine Operation (meistens filtern oder suchen) dauert. Der Wikipedia Artikel bringt mich auch so gar nicht weiter, weil er meiner Meinung ein Mathematikstudium voraussetzt.

Gibt es nicht einfach irgendwo eine Liste in der das ganze nach Dauer aufgelistet ist (das ist schneller als das z.B.) ?

Hallo Froggie

Eigentlich kann man mit den Landau-Symbolen nicht aussagen, welcher Algorithmus schneller ist. Die Notation gibt immer nur eine Tendenz an. Genauer gesagt, liefert dir eine Aussage ala O(n²) ein Wachstumsverhalten, wenn du die Problemgröße änderst.

Beispielsweise könnte ein Sortieralgorithmus der Komplexität O(n²) für das Sortieren von 50 Elementen 10 ms brauchen. Dann braucht er für 100 Elemente 40 ms.
Allerdings kann es trotzdem sein, dass ein Algorithmus der Komplexität O(n log n) für 50 Elemente schon 20 ms braucht. Aber für irgendeine Problemgröße wird er trotzdem immer schneller sein, als der erste Algorithmus.

Das ist auch die Aussage, die man meist aus der Groß-O-Notation zieht: Welcher Algorithmus ist für ein großes Problem der schnellste. Denn da interessiert die Geschwindigkeit natürlich am meisten.

Grüße
kuda

PS: Das Beispiel oben is formell natürlich nicht korrekt, da ein Algorithmus aus O(n log n) natürlich auch immer in O(n²) liegt. Alle, die es korrekt haben wollen: Ersetzt alle O durch Thetas oder geht von möglichst engen Schranken aus 😉

Hallo,

einfach ausgedrückt geben diese Symbole wieder wie viele Operationen ein Algorithmus braucht um Berechnungen in einer Folge (zB Array) durchzuführen.

Beispiel:
O(n): bedeutet dass gleich viele Operation benötigt werden wie die Anzahl der Element. Also doppelt soviele Elemente -> doppelt so viele Operationen -> doppelt so lange

O(n²): bedeutet dass bei doppelt so vielen Elemente die vierfache Zeit benötigt wird

O(log n): bei Verdoppelung wächst die Rechenzeit nur logn(2), also um einen konstanten Betrag der weniger als das Doppelte ist -> ist gut.

Beispiel Suchfunktion in einem Array mit 100 Elementen:
O(n) benötigt max. 100 Operationen
O(log n) benötigt max. 7 Operationen (log²7 = 6,64)

Somit kann mit den Landau-Symbolen angegeben wie effizient ein Algorithmus sein wird.

Hoffe es ist ein bischen verständlicher geworden.

mfG Gü

Landau steht für die obere Schranke des Laufzeitverhältnises im Worst Case. Dann gibt es noch Theta für die durchschnittliche sowie Omega für die minimale Laufzeit.

Das bedeutet, wenn du n = 4 Datensätze zu sortieren hast und du verwendest z.B. den Insertion Sort der ein O(n^2) hat (bei einer umgekehrt sortierte Reihenfolge) würde es 16 Mal durchlaufen müssen um die 4 Zahlen zu sortieren.

Edit:
Wenn du Algorithmen vergleichen willst wirst du größenteils mit dem mathematischen Formalismus leben müssen, da die Algorithmik eine exakte Wissenschaft ist. Es gibt für C# ein Buch in dem Algorithmen behandelt werden, das sogar damit wirbt ohne dem großen O auszukommen, aber mir fällt gerade nicht ein wie es heißt. Vielleicht findest du es auf Amazon.