WikiDer > Polynomzeit
In dem Komplexitätstheorie kann a Algorithmus im Polynomzeit ausgeführt werden, wenn die benötigte Zeit in Abhängigkeit von der Größe der Eingabe durch a . begrenzt ist Polynom. Polynomialzeit wird oft als O(neink) bei welchem nein zeigt die Größe der Eingabe an und k eine Konstante, die je nach Problem unterschiedlich sein kann. sehen Komplexitätsgrad für eine Definition und Erklärung dieser Notation.
Entscheidungsprobleme für die ein Algorithmus in polynomieller Zeit existiert für a deterministische Turingmaschine Gehören zur Komplexitätsklassep. Die in polynomieller Zeit gelösten Entscheidungsprobleme durch a nichtdeterministische Turingmaschine kann gelöst werden, gehören zu NP.
Ein Algorithmus, der in polynomieller Zeit ausgeführt werden kann, wird normalerweise als "schnell" angesehen. Dies steht im Gegensatz zu superpolynomialen Algorithmen, die mehr Zeit benötigen als polynomiale Algorithmen. Ein Beispiel für superpolynomielle Zeit ist exponentielle Zeit.
Beispiele
Beispiele für polynomielle Zeit sind:
| Zeit | Notation | Beispiel |
|---|---|---|
| Konstante Zeit | O(1) | |
| Lineare Zeit | Ö(nein) | Finde das kleinste Element in einer ungeordneten Folge |
| Logarithmische Zeit | O(log nein) | Halbierung |
| Lineare logarithmische Zeit | Ö(nein Log nein) | Zusammenführen, sortieren |
| quadratische Zeit | Ö(nein2) | Blasensortierung |
| Kubikzeit | Ö(nein3) |
Siehe auch
| Zeitkomplexität von Algorithmen |
|---|
konstante Zeit · lineare Zeit · Polynomzeit · exponentielle Zeit |