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(n^k) 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

Voorbeelden van polynomiale tijd zijn:

Tijd	Notatie	Voorbeeld
Constante tijd	O(1)
Lineaire tijd	O(n)	Het kleinste element in een ongeordende reeks zoeken
Kwadratische tijd	O(n2)	Bubblesort
Kubische tijd	O(n3)
Logaritmische tijd	O(log n)	binaire boom

Zie ook

• Complexiteitsgraad