Asymptotische Aufwandsordnungen
Inhaltsverzeichnis |
Bit-Komplexität
Im Gegensatz zum uniformen Komplexitätsmaß (Registermaschine) betrachten wir im Allgemeinen die Bit-Komplexität (Turingmaschine). In der Berechenbarkeitstheorie werden die zugehörigen Maschinenmodelle behandelt. Bei der Bit-Komplexität werden die Problemgrößen durch die Stelligkeit der verwendeten Eingaben bestimmt.
Wie eine einfache Rechnung zeigt, spielt die Wahl der Zahlenbasis dabei keine Rolle, da sie die Stelligkeit einer natürlichen Zahl lediglich durch einen konstanten Faktor verändert.
Für eine höchstens m-stellige natürliche Zahl n im 10er System, gilt n\leq 10^{m}-1. Für eine höchstens p-stellige Dualzahl n gilt n\leq 2^p-1. Aus 2^p-1=10^m-1, mit m,p\in \mathbb{N} und 0\leq m,p, folgt 3m<p<4m.
Die Stelligkeit von n im Dualsystem ist also durch 4 mal deren Stelligkeit im Dezimalsystem beschränkt. Ist n höchstens 3-stellig, d.h. n\leq 999, so ist n im Dualsystem höchstens 11-stellig: n=1111100111 (10-stellig), s. Konverter.
Für die Bit-Komplexität wird die Eingabe im Allgemeinen als Dualzahlwort auf das Band der Turingmaschine geschrieben.
Definition und Notation
Groß-O
Die Groß-O (\mathcal{O}) Notation ist eine mathematische Notation, die das Verhalten einer Funktion für größer werdende Argumente beschreibt. Der sog. \mathcal{O}-Kalkül gehört zur Gruppe der Notationen, welche durch Paul Bachmann und Edmund Landau eingeführt wurden, und deshalb auch Bachmann-Landau Notationen genannt werden.
In der Informatik wird die Groß-O Notation genutzt, um Algorithmen bezüglich ihrer Laufzeit und ihres Speicherbedarfs zu klassifizieren.
Anmerkung
In den folgenden Definitionen wird traditionell f(n) auch dann geschrieben, wenn es sich nicht um einen Funktionswert, sondern um eine einstellige Funktion f mit n\mapsto f(n) handelt.
Definition 1.1
Diese Definition sagt aus, dass f genau dann zur Menge \mathcal{O}(g) gehört, wenn es eine positive reelle Zahl c gibt, sodass alle f(n) ab einem gewissen n_0 kleiner sind als c \cdot g(n). Die Funktion g, welche durch die Landau-Notation angegeben wird, dient also als obere Schranke für die Funktion f.
Da es sich um eine obere Schranke handelt, gilt beispielsweise: \mathcal{O}(n) \subset \mathcal{O}(n^2) oder \mathcal{O}(n^2) \subset \mathcal{O}(n^3) oder \mathcal{O}(n^2) \subset \mathcal{O}(2^n). Es ist also auch korrekt anstatt \mathcal{O}(n), \mathcal{O}(n^2) anzugeben, dies wäre jedoch für die Praxis nicht sehr sinnvoll.
Typische Laufzeiten sind:
| Effizienzklasse | Beschreibung |
|---|---|
| \mathcal{O}(1) | konstante Laufzeit (unabh. von Eingabegröße) |
| \mathcal{O}(\log n) | logarithmische Laufzeit |
| \mathcal{O}(n) | lineare Laufzeit, z.B. unverschachtelte Iteration |
| \mathcal{O}(n\log n) | logarithmisch-lineare Laufzeit |
| \mathcal{O}(n^c) | polynomiale Laufzeit (c=2: quadratisch, c=3: kubisch), z.B. verschachtelte Schleifen |
| \mathcal{O}(c^n), c>1 | exponentielle Laufzeit, z.B. mehrfach rekursive Funktionen |
| \mathcal{O}(n!) | exponentielle Laufzeit, Stirlingsche Formel: n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n, n\rightarrow\infty |
Es gibt viele weitere sog. Komplexitätsklassen. Außerdem muss es sich nicht immer um die Variable n handeln, es können auch mehrere Variablen innerhalb einer Komplexitätsklasse vorkommen. Zum Beispiel ist der Aufwand, um eine Wand der Höhe h und der Breite b zu bemalen, \mathcal{O}(hb). Hier befassen wir uns jedoch nur mit Zeitaufwänden in Abhängigkeit von einer Problemgröße n.
Groß-Omega
Die Groß-Omega (\Omega) Notation ähnelt Groß-O konzeptionell, beschreibt jedoch eine untere Schranke. Die formale Defintion lautet demnach folgendermaßen:
Definition 1.2
f(n) \in \Omega(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } \exists c \in \mathbb{R}^+ : \exists n_0 \in \mathbb{N} : \forall n \geqslant n_0 : f(n) \geqslant c \cdot g(n)f gehört genau dann zu \Omega(g), wenn es ein c gibt, für das alle f(n) ab einem bestimmten n_0 größer sind als c \cdot g(n).
Groß-Theta
Im Idealfall kann man eine asymptotische Beschränkung nach oben und unten durch ein und dieselbe Funktion mit verschiedenen Faktoren angeben. Grafisch wirkt dies wie ein Band, in dem die Graphen sämtlicher Funktionen aus \Theta(g) verlaufen. \Theta beschreibt damit die exakte Komplexitätsklasse.
Definition 1.3
f(n) \in \Theta(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } \exists c_1, c_2 \in \mathbb{R}^+ : \exists n_0 \in \mathbb{N} : \forall n \geqslant n_0 : c_1 \cdot f(n) \leqslant f(n) \leqslant c_2 \cdot g(n)bzw.
f(n) \in \Theta(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } f(n) \in \mathcal{O}(g(n)) \text{ und } f(n) \in \Omega(g(n))Klein-O
Die Klein-O (\mathcal{o}) Notation gibt wie die Groß-O Notation eine obere Schranke an. Jedoch handelt es sich hierbei um eine strikte obere Schranke, d.h. für alle Konstanten c ist die Funktion asymptotisch nach oben beschränkt, also ergibt sich folgende Definition:
Definition 1.4
f(n) \in \mathcal{o}(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } \forall c \in \mathbb{R}^+ : \exists n_0 \in \mathbb{N} : \forall n \geqslant n_0 : f(n) < c \cdot g(n)Dies hat zur Folge, dass n^2 \notin \mathcal{o}(n^2), aber n^2 \in \mathcal{o}(n^3).
Klein-Omega
Analog ist die Klein-Omega (\omega) Notation eine striktere Schranke als \Theta. Folgende Definition ergibt sich:
Definition 1.5
f(n) \in \omega(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } \forall c \in \mathbb{R}^+ : \exists n_0 \in \mathbb{N} : \forall n \geqslant n_0 : f(n) > c \cdot g(n)Auch hier muss die Ungleichung für alle c \in \mathbb{R}^+ gelten. Dies hat zur Folge, dass n^2 \notin \omega(n^2), aber n^2 \in \mathcal{o}(n) oder n^2 \in \mathcal{o}(n \log n).
Anmerkung
In der Praxis wird meistens die \mathcal{O}-Notation verwendet.
Definition über Grenzwerte
Es ist auch möglich den Zusammenhang zweier Funktionen bezüglich der Landau-Notationen über den Grenzwert des Quotienten der beiden Funktionen zu definieren.
Definition 1.6
f(n) \in \mathcal{O}(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } 0 \leqslant \lim_{n \to \infty} \frac{f(n)}{g(n)} < \inftyIst der Grenzwert endlich, so steigt f(n) asymptotisch höchstens so stark wie g(n).
Definition 1.7
f(n) \in \Omega(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } 0 < \lim_{n \to \infty} \frac{f(n)}{g(n)}Ist der Grenzwert größer als 0, so steigt f(n) asymptotisch mindestens so stark wie g(n).
Definition 1.8
f(n) \in \Theta(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } 0 < \lim_{n \to \infty} \frac{f(n)}{g(n)} < \inftyIst der Grenzwert größer als 0 und endlich, so steigt f(n) asymptotisch genauso stark wie g(n).
Definition 1.9
f(n) \in \mathcal{o}(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0Ist der Grenzwert 0, so steigt f(n) asymptotisch weniger stark als g(n).
Definition 1.10
f(n) \in \omega(g(n)) \text{ mit } n \rightarrow \infty \text{ genau dann, wenn } \lim_{n \to \infty} \frac{f(n)}{g(n)} = \inftyIst \frac{f(n)}{g(n)} divergent (\infty) für n\to\infty, so steigt f(n) asymptotisch stärker als g(n).
Best Case, Worst Case, Average Case
Die Groß-O (\mathcal{O}) Notation wird verwendet, um das Laufzeitverhalten eines Algorithmus zu charakterisieren. Hierfür kommen die folgenden drei Analyseformen in Betracht: worst case, average case und best case.
Sie unterscheiden sich in der Wahl der jeweiligen Laufzeit f(n) aus einer Liste von k Laufzeiten \underbrace{f(n),f(n),\ldots,f(n)}_{k\ Stück} für eine bestimmte Problemgröße n: Greift man bei einer solchen empirischen Analyse für jedes n den kleinsten der k Werte für f(n) heraus, führt dies zu einer Best-Case-Analyse. Bildet man das arithmetische Mittel aus den jeweils k Werten für f(n), gelangt man zum Average-Case. Nimmt man die jeweiligen Maximalwerte, ergibt das den Worst-Case. In den genannten drei Analyseformen steht am Ende eine den Zusammenhang zwischen n und Zeitaufwand T=f(n) beschreibende Funktion f, deren asymptotische Ordnung das gesuchte Ergebnis beschreibt.
Alle drei Analyseformen sind entweder Kern einer empirischen Analyse (Datenerhebung) oder verwenden Wahrscheinlichkeiten und erfordern den Einsatz statistischer Methoden.
Wir illustrieren die drei Fälle am Beispiel von Monkey sort, auch Bogosort, stupid sort, slowsort, permutaion sort oder shotgun sort genannt. Es handelt sich um eines der ineffektivsten Sortierverfahren, das man sich ausdenken kann.
Nehmen wir an, eine Liste mit n natürlichen Zahlen soll aufsteigend sortiert werden. Dann kann man folgendes Verfahren anwenden: 1. Falls die Liste bereits sortiert ist, dann STOPP. 2. Anderenfalls bringe die Liste durcheinander und gehe zu 1.