Constante tijd

In de complexiteitstheorie kan een algoritme in constante tijd of O(1) tijd worden uitgevoerd als de benodigde tijd niet afhangt van de grootte van de invoer. Het uitvoeren van zo'n algoritme vereist een constante hoeveelheid tijd ongeacht de grootte van de invoer. Voorbeelden hiervan zijn het opvragen van een element uit een array, het opvragen van het eerste element van een gelinkte lijst of het controleren of een natuurlijk getal in binaire notatie een even getal is.

Het vinden van een element in een ongesorteerde lijst verloopt niet in constante tijd want daarvoor moet mogelijk de gehele lijst doorlopen worden en de benodigde tijd hangt dus af van het aantal elementen in de lijst. Het opzoeken van een element in een ongesorteerde lijst verloopt in lineaire tijd, aangezien het lineair van het aantal elementen in de invoer afhangt. Deze manier van zoeken wordt daarom ook wel lineair zoeken genoemd.

Definitie

Een algoritme kan in constante tijd worden uitgevoerd als er een constante c bestaat zodanig dat het aantal operaties door deze c wordt begrensd. Deze constante c kan verschillen per algoritme. De complexiteitsgraad wordt ook genoteerd als O(1).

Een algoritme dat A(n) operaties vereist, waarbij n de grootte van de invoer is, wordt uitgevoerd in O(1) tijd als geldt dat 0 ≤ A(n) ≤ c, voor alle n en een constante c.

Kenmerken

Herhaling

Wanneer een algoritme in constante tijd wordt uitgevoerd, betekent dat niet dat bepaalde bewerkingen niet meer keren gebeuren. Het is best mogelijk om een operatie in constante tijd meer keren uit te voeren, zolang dit aantal maar niet van de invoer afhangt. Bijvoorbeeld: het opvragen van precies 100 elementen uit een array, het opvragen van een element uit een array gebeurt in constante tijd en 100 is een vaste constante die niet afhangt van de grootte van de array. Het algoritme als geheel gebeurt dus in constante tijd. Men noteert dit nog steeds als O(1) en niet als O(100).

Het volgende gebeurt in constante tijd:

for x = 1 to 100:
for y = 1 to 200:
   voer operatie in constante tijd uit

Het aantal keer dat de operatie wordt uitgevoerd is namelijk 100 * 200 keer, een constant aantal, en de operatie zelf gebeurt ook in constante tijd.

Benodigde tijd kan verschillen

Het is wel mogelijk dat de benodigde tijd verschilt afhankelijk van de invoer, zolang de benodigde tijd altijd begrensd wordt door een constante c. Een voorbeeld is de volgende pseudocode, waarbij a en b getallen zijn:

if b < a
   verwissel a en b

Na het uitvoeren van deze code geldt dat a ≤ b. Mocht het al zo zijn dat voor de ingevoerde getallen a en b geldt dat a ≤ b, dan worden de getallen niet verwisseld. Het algoritme verloopt dan nog steeds in constante tijd want er is een constante c te geven zodanig dat de benodigde tijd begrensd wordt door deze constante. In het andere geval zal zowel het controleren van a en b als het verwisselen plaatsvinden, de benodigde tijd hiervoor bestaat uit hooguit c operaties. In het beste geval zal alleen de controle op a en b worden uitgevoerd, wat zeker minder is dan de constante c.