Zeitkomplexität

Laufzeit

Konstante Laufzeit

Algorithmen der Zeitkomplexität $O(1)$ sind die effizientesten. Egal wie groß die Eingabemenge, Algorithmen mit konstanter Laufzeit brauchen immer dieselbe Zeit. Ein Beispiel für solche einen Algorithmus ist der Zugriff auf einen Array.

Loglineare Laufzeit

Algorithmen der Zeitkomplexität $O(n\log(n))$ gelten als sehr effizient, da diese mit größeren Datenmengen ausgezeichnet umgehen können. Ein Beispiel für solch einen Algorithmus ist Binary Search, da eine Verdoppelung der Datenmenge zu einer weiteren Iteration führt.

Lineare Laufzeit

Die Zeitkomplexität $O(n)$ beschreibt z.B. das Durchlaufen einer Liste.

Polynomiale Laufzeit

Einfache Algorithmen, wie z.B. Bubblesort, haben eine polynomiale Laufzeit $O(n^k)$.

Nicht-polynomiale Laufzeit

Algorithmen mit exponentieller $O(2^n)$ oder sogar fakultärer $O(n!)$ Laufzeit sind für größere Datenmengen grundsätzlich unpraktikabel.

Probleme als eine auf den natürlichen Zahlen definierte Funktion

Dieser Grundsatz der Berechenbarkeitstheorie besagt, dass alle Probleme als Funktionen umgewandelt werden können, wobei die Eingabe zu einer natürlichen Zahl umgewandelt wird.

Diese Funktion kann entweder einen Wahrheitswert $f: \mathbb{N} \rightarrow \{0,1\}$ oder eine natürliche Zahl $f: \mathbb{N} \rightarrow \mathbb{N}$ zurückgeben.

Warum?

• Vereinheitlichung, da alle Probleme, egal mit welchen Eingaben (Bild, Ton, Video) als Zahlen ausgedrückt werden können.
• Berechenbarkeitsbeweise: gibt es für eine Funktion $f: \mathbb{N} \rightarrow \mathbb{N}$ einen Algorithmus?
• Eine Turingmaschine arbeitet auf Bändern mit Zeichen, was dem Verarbeiten von natürlichen Zahlen ähnelt.

Abzählbarkeit der Computerprogramme zur Lösung von Problemen

Weil Programme durch eine endliche Zeichenfolge über einem endlichen Alphabet (z.B. Unicode) dargestellt werden können, könnte man alle theoretisch möglichen Programme aufzählen. Dasselbe ist allerdings nicht für Probleme wahr, da diese unendlich sind. Daraus lässt sich schließen, dass nicht alle Probleme durch Programme gelöst werden können.

Das Halteproblem

Kann man bei jedem Programm voraussagen, ob dieses irgendwann anhält oder ewig weiterläuft? Das Problem besteht darin, dass ein Algorithmus, welcher dieses Problem versucht zu lösen, in einen theoretischen Widerspruch geraten würde, wenn dieser auf sich selber angewendet werden würde.

Die Bedeutung dieses Problems ist, dass die Berechenbarkeit Grenzen hat und nicht alle logischen Probleme maschinell lösbar sind.