Polynomiale tijd
In de complexiteitstheorie kan een algoritme in polynomiale tijd uitgevoerd worden als de benodigde tijd, als functie van de grootte van de invoer, begrensd wordt door een polynoom. Polynomiale tijd wordt vaak genoteerd als O(nk) waarbij n de grootte van de invoer weergeeft en k een constante die per probleem kan verschillen. Zie complexiteitsgraad voor een definitie en een toelichting bij deze notatie.
Beslissingsproblemen waarvoor een algoritme in polynomiale tijd bestaat voor een deterministische turingmachine behoren tot de complexiteitsklasse P. De beslissingsproblemen die in polynomiale tijd door een niet-deterministische turingmachine opgelost kunnen worden, behoren tot NP.
Een algoritme dat in polynomiale tijd uitgevoerd kan worden, wordt doorgaans gezien als "snel". Dit in tegenstelling tot super-polynomiale algoritmen die meer tijd vergen dan polynomiale algoritmen. Een voorbeeld van super-polynomiale tijd is exponentiële tijd.
Voorbeelden
[bewerken | brontekst bewerken]Voorbeelden van polynomiale tijd zijn:
| Tijd | Notatie | Voorbeeld |
|---|---|---|
| Constante tijd | O(1) | |
| Lineaire tijd | O(n) | Het kleinste element in een ongeordende reeks zoeken |
| Logaritmische tijd | O(log n) | Bisectie |
| Lineair logaritmische tijd | O(n log n) | Mergesort |
| Kwadratische tijd | O(n2) | Bubblesort |
| Kubische tijd | O(n3) |
Zie ook
[bewerken | brontekst bewerken]
· 
· 