Asymptotische Aufwandsordnungen
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.
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
f(n) \in \mathcal{O}(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) \leqslant c \cdot g(n)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.