Ing Mathematik: Landau

• 
  Paul Gustav Heinrich Bachmann (deutscher Mathematiker, 1837-1920)
• 
  Edmund Georg Hermann Landau (deutscher Mathematiker, 1877-1938)

Landau-Symbole werden in der Mathematik und Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben oder auch um das Zeitverhalten von Algorithmen abzuschätzen. Konkrete Laufzeitmessungen sind abhängig von der verwendeten Hardware. Um das auf abstrakterer Ebene durchzuführen verwendet man die Landau-Notation (auch O-Notation, auf englisch Big Oh Notation genannt). Eingeführt wurde das $O$-Symbol durch den Zahlentheoretiker Paul Bachmann. Bekannt wurde diese Notation durch den Mathematiker Edmund Landau. Es gibt mehrere Landau-Symbole, von denen die Gebräuchlichsten im Nachfolgenden kurz vorgestellt werden.

Das $O$-Symbol

Die Definition $f(n)=O(g(n))$ bedeutet: $f(n)\le c\cdot g(n)$ für alle $n\ge n_0$ und ein $c\in {ℝ}^{+}$.

Genaugenommen ist das Gleichheitssymbol bei $f(n)=O(g(n))$ nicht korrekt. Es müsste heißen $f(n)\in 𝒪(g(n))$. Aber in der Literatur ist meistens die Variante mit dem Gleichheitszeichen zu finden und das wird auch hier so gehandhabt. Dieses $O$-Symbol ist das von den Landau-Symbolen am meisten verwendete.

Beispiel 1

Gilt $2^{n+1}=O(2^n)$?

Lösung:

Es muss gelten: $f(n)\le c\cdot g(n)$, mit $f(n)=2^{n+1},g(n)=2^n$, d.h.,

$2^{n+1}\le c\cdot 2^n$

$2\cdot 2^n\le c\cdot 2^n$

Mit $c\ge 2$ gilt für alle $n\ge 0$: $2^{n+1}=O(2^n)$, was zu zeigen war.

Nachfolgende Grafik zeigt obigen Sachverhalt für eine Konstante c=3.

Das zugehörige Python-Programm:

import matplotlib.pyplot as plt
import numpy as np

n = np.arange(0, 20, .1)
f = 2**(n+1)
g = 2**n
c = 3

plt.plot(n, f, label = "f = 2**(n+1)", color="orange")
plt.plot(n, c*g, label = "g = 2**n", color ="blue")
plt.grid()
plt.title("O-Notation")
plt.xlabel("n")
plt.ylabel("f,g")
plt.legend(loc="best")
plt.text(10,1e6,"mit c=3")

plt.show()

Beispiel 2

Gilt $2^n=O(3^n)$?

Lösung:

Ja, denn $2^n\le c\cdot 3^n$ gilt für alle $n\ge 0$ und z.B. $c=1$.

Das $\mathrm{\Omega }$-Symbol

Die Definition $f(n)=\mathrm{\Omega }(g(n))$ bedeutet: $f(n)\ge c\cdot g(n)$ für alle $n\ge n_0$ und ein $c\in {ℝ}^{+}$.

Beispiel

Gilt $n^n=\mathrm{\Omega }(n!)$?

Lösung:

Wir müssen zeigen, dass $n^n\ge c\cdot n!$ mit einem beliebigen $c\in {ℝ}^{+}$, bspw. $c=1$. Am einfachsten machen wir das mit einer vollständigen Induktion.

Induktionsanfang: $n=1$

$1^1\ge 1!$

$1\ge 1$ passt!

Induktionsschritt:

$(n+1{)}^{n+1}\ge (n+1)!$

$(n+1)(n+1{)}^n\ge ((n+1)\cdot n!$

$(n+1{)}^n\ge n!$

Die Induktionsvoraussetzung war aber, dass $(n{)}^n\ge n!$, somit gilt auch immer $(n+1{)}^n\ge n!$, was zu zeigen war. Es gilt somit $n^n=\mathrm{\Omega }(n!)$.

Python-Code:

import matplotlib.pyplot as plt
import numpy as np
import scipy.special as scs

n = np.arange(0.5, 5, 0.1)
f = n**n
g = scs.factorial(n)
c = 1

plt.plot(n, f, label = "f = n**n", color="orange")
plt.plot(n, c*g, label = "g = n!", color ="blue")
plt.grid()
plt.title("Omega-Notation")
plt.xlabel("n")
plt.ylabel("f,g")
plt.legend(loc="best")
plt.text(2,20,"mit c=1")
plt.semilogy()

plt.show()

Das $\mathrm{\Theta }$-Symbol

Die Definition $f(n)=\mathrm{\Theta }(g(n))$ bedeutet: $c_2\cdot g(n)\le f(n)\le c_1\cdot g(n)$ für alle $n\ge n_0$ und $c_1,c_2\in {ℝ}^{+}$.

Hier gilt es zu zeigen, dass $f(n)$ ab einem $n_0$ zwischen $c_1\cdot g(n)$ und $c_2\cdot g(n)$ liegt.

Aufgaben

• Gilt $\sqrt{n}=\mathrm{\Theta }(\log n^3)$?
• Gilt $100=\mathrm{\Theta }(log100)$?

Rechnen mit der Landau-Notation

Addition

$O(f(n)+g(n))\to O(\max (f(n),g(n))$

$\mathrm{\Omega }(f(n)+g(n))\to \mathrm{\Omega }(\max (f(n),g(n))$

$\mathrm{\Theta }(f(n)+g(n))\to \mathrm{\Theta }(\max (f(n),g(n))$

Beispiel: $O(n^3+n^2+1)=O(n^3)$

Multiplikation

$O(c\cdot f(n))\to O(f(n))$

$\mathrm{\Omega }(c\cdot f(n))\to \mathrm{\Omega }(f(n))$

$\mathrm{\Theta }(c\cdot f(n))\to \mathrm{\Theta }(f(n))$

mit c > 0.

Beispiel: $O(500n^3)=O(n^3)$

$O(f(n))\cdot O(g(n))\to O(f(n)\cdot g(n))$

$\mathrm{\Omega }(f(n))\cdot \mathrm{\Omega }g(n))\to \mathrm{\Omega }(f(n)\cdot g(n))$

$\mathrm{\Theta }(f(n))\cdot \mathrm{\Theta }g(n))\to \mathrm{\Theta }(f(n)\cdot g(n))$

Beispiel: $O(n)\cdot O(n!)=O(n\cdot n!)$

Grenzwertregeln

Ab und zu finden sich auch folgende Regeln zur Definition von $O$ und $\mathrm{\Omega }$.

$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}<\mathrm{\infty }\to f(n)=O(g(n))$

$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}>0\to f(n)=\mathrm{\Omega }(g(n))$

Komplexitätsklassen

Nachfolgend eine leicht überarbeitete Tabelle aus Vorlage:W mit gebräuchlichen Komplexitätsklassen. Wenn Sie am Anfang nicht alles verstehen - kein Problem, die Tabelle geht schon sehr ins Detail und ist eher für Informatiker von Interesse.

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
$f\in 𝒪(1)$	$f$ ist beschränkt.	$f$ überschreitet einen konstanten Wert nicht (ist unabhängig vom Wert des Arguments $n$).	Feststellen, ob eine Binärzahl gerade ist Nachschlagen des $n$-ten Elementes in einem Feld in einer Registermaschine
$f\in 𝒪(\log \log n)$	$f$ wächst doppel-logarithmisch.	Bei Basis 2 erhöht sich $f$ um 1, wenn $n$ quadriert wird.	Interpolationssuche im sortierten Feld mit $n$ gleichförmig verteilten Einträgen
$f\in 𝒪(\log n)$	$f$ wächst logarithmisch.	$f$ wächst ungefähr um einen konstanten Betrag, wenn sich $n$ verdoppelt. Die Basis des Logarithmus ist dabei egal.	Binäre Suche im sortierten Feld mit $n$ Einträgen
$f\in 𝒪(\sqrt{n})$	$f$ wächst wie die Wurzelfunktion.	$f$ wächst ungefähr auf das Doppelte, wenn sich $n$ vervierfacht.	Anzahl der Divisionen des naiven Primzahltests (Teilen durch jede ganze Zahl $\le \sqrt{n}$)
$f\in 𝒪(n)$	$f$ wächst linear.	$f$ wächst ungefähr auf das Doppelte, wenn sich $n$ verdoppelt.	Suche im unsortierten Feld mit $n$ Einträgen (Bsp. Lineare Suche)
$f\in 𝒪(n\log n)$	$f$ hat super-lineares Wachstum.		Vergleichbasierte Algorithmen zum Sortieren von $n$ Zahlen Mergesort, Heapsort
$f\in 𝒪(n^2)$	$f$ wächst quadratisch.	$f$ wächst ungefähr auf das Vierfache, wenn sich $n$ verdoppelt.	Einfache Algorithmen zum Sortieren von $n$ Zahlen Selectionsort
$f\in 𝒪(n^m)$	$f$ wächst polynomiell.	$f$ wächst ungefähr auf das $2^m$-Fache, wenn sich $n$ verdoppelt.	„Einfache“ Algorithmen
$f\in 𝒪(2^n)$	$f$ wächst exponentiell.	$f$ wächst ungefähr auf das Doppelte, wenn sich $n$ um 1 erhöht.	Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels erschöpfender Suche
$f\in 𝒪(n!)$	$f$ wächst faktoriell.	$f$ wächst ungefähr auf das $(n+1)$-Fache, wenn sich $n$ um 1 erhöht.	Problem des Handlungsreisenden (mit erschöpfender Suche)
$f\in 𝒪(A(n))$	$f$ wächst wie die modifizierte Ackermannfunktion.		Problem ist berechenbar, aber nicht notwendig primitiv-rekursiv

Abschätzungen mit der Landau-Notation

Meist wird man an der worst-case-Laufzeit interessiert sein, d.h. die Abschätzungen erfolgen mit dem $O$-Symbol, z.B.

n = 5                       # O(1)
m = 5                       # O(1)

for i in range(0, n, 1):    # O(n)
    print("Hallo Welt")     # O(1)
    print(m)                # O(1)    
    m += 1                  # O(1)

print("Ende")               # O(1)

Es ergibt sich $O(1)+O(1)+O(n)*(O(1)+O(1)+O(1))+O(1)=$ $O(2)+O(n)*O(3)+O(1)=O(2)+O(3n)+O(1)=O(n)$.

Dieses Beispiel ist von der Komplexitätsklasse $O(n)$. Auch wenn hier die print-Befehle sicher mehr Ressourcen verbrauchen wie einfache Zuweisungen, so wird dies bei der Auswertung mit der Landau-Notation vernachlässigt.