Die '''Landau-Notation''' bezeichnet eine Schreibweise, um die Laufzeitabhängigkeit eines Programmes? von gewissen Parametergrößen anzugeben.

Berechnung der Laufzeitordnung

Zwei Algorithmen haben nach Landau die gleiche Laufzeitordnung, wenn sich ihre Laufzeiten nur um konstante Faktoren unterscheiden. Wenn mehrere Algorithem hintereinander gehängt werden, so ist die Laufzeitordnung des Gesammtalgorithmuses diejenige des langsamsten Teiles. Wird ein Algorithmus mehrmals ausgeführt, so hat der Gesammtalgorithmus eine Laufzeit von Laufzeit des Teilalgorithmuses mal Anzahl.

Beispiele:

• Summieren mit Math::BigInt (n die Stellenzahl): O(n)
• Multiplizieren mit Math::BigInt (n die Stellenzahl): O(n^2)
• Multiplizieren mit FFT (keine Perl-implementierung bekannt) (n die Stellenzahl): O(n log n log log n)
• Sortieren (n die Anzahl der Elemente des Arrays): O(n log n)
• Array-Zugriffe (n die Anzahl der Array-Elemente): O(1)
• Hash-Zugriffe (n die Anzahl der Hash-Elemente): O(log n)

Jedoch muß man sich bei der Landau-Notation stets dessen bewusst sein, daß sie nur die Änderung der Laufzeit für sehr große Werte angibt, jedoch keine Aussage darüber macht, welcher Algorithmus bei einem gegebenen Problem schneller ist.

-- IshKa - 30 Apr 2004