Alle fag › Videregående programmering › Tidskompleksitet, O-notasjon

Tidskompleksitet, O-notasjon

O-notasjon beskriver hvordan kjøretiden til en algoritme vokser med antall elementer nn, for store nn. O(1)O(1) er konstant, O(log⁡n)O(\log n) vokser sakte, O(n)O(n) lineært og O(n2)O(n^2) kvadratisk. Det er dette som avgjør om en algoritme takler store datamengder.

O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2)vanlig rekkefølge, fra raskest til tregest

Symboler

nnantall elementer

Eksempel

Oppslag i en dict er O(1)O(1): nesten uavhengig av størrelsen.

Binærsøk i en sortert liste er O(log⁡n)O(\log n): søkeområdet halveres hvert steg.

Dobler du nn i en O(n2)O(n^2)-algoritme, firedobles kjøretiden — ikke bare dobles.
Øv på algoritmer og datastrukturer gratis →

← @property · Rekursjon →

Del av Videregående programmering: Algoritmer og datastrukturer.