AuK/Asymptotische Aufwandsordnungen

Wiki-Quelltext dieser Seite.

==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 $10$er 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. [https://www.matheretter.de/rechner/zahlenkonverter 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$.

[[Bild:Big-O-notation.png|500px|center]]

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.