Amortized time er måden at udtrykke tidskompleksiteten på, når en algoritme kun har en meget dårlig tidskompleksitet en gang i mellem ud over den tidskompleksitet, der forekommer det meste af tiden. Et godt eksempel ville være en ArrayList, som er en datastruktur, der indeholder et array og kan udvides. Anden definition fra Stack Overflow er den gennemsnitlige tid, der tages pr. operation, hvis du udfører mange operationer.
Når ArrayList rammer arraykapaciteten i det, så opretter det et nyt array med den fordoblede størrelse af det gamle array og kopierer alle elementer i det gamle array til det nye array. I ArrayList findes der to tidskompleksiteter; den ene er O(1) og den anden er O(n).
Når arrayet i det ikke har nået sin kapacitet og stadig har plads nok til at indsætte elementer
For at indsætte et element til arrayet i dette tilfælde skal vi blot sætte elementet efter det sidste element. Vi har stadig plads til at indsætte elementer.
Når arrayet i det har nået sin kapacitet og skal genskabe sig selv med den fordoblede størrelse
Arrayet har nået sin kapacitet, og vi har ingen pladser til rådighed. Så er vi nødt til at oprette et helt nyt array med den fordoblede størrelse. Og derefter kopiere elementerne i det gamle til det nye, hvilket tager O(n), hvor n er kapaciteten af det gamle array og det værste tilfælde.
For at udtrykke disse to tidskompleksitet, er der her amortiseret tid. Det, det gør, er at lade os beskrive, at det værste tilfælde sker en gang imellem, hver gang det interne array rammer sin kapacitet.
Men når det sker, sker det ikke igen i så lang tid, at omkostningerne er “afskrevet”. (Cracking the Coding Interview 6th edition 43)
Så hvordan beskriver vi de to kompleksiteter?
I tilfældet ArrayList kan vi sige, at
Indsættelsen tager O(n), når kapaciteten er nået, og den amortiserede tid for hver indsættelse er O(1).
Men lad os være præcise for den værste tidskompleksitet uden at simplificere denne tid. Hvis den interne arraykapacitet starter med 1, så vil kapaciteterne være 1, 2, 4, 8, 16… X, når den rammer kapaciteten og bliver fordoblet. Det tager 1, 2, 4, 8, 16… X elementer at kopiere til det nye array afhængigt af den kapacitet, der er nået. Så tidskompleksiteten vil være 1 + 2 + 4 + 8 + 16 + … X. Hvis man tænker ud fra X, vil det være X + X/2 + X/4 + X/8 … + 1 = 2X cirka. Så med andre ord præcist,
Indsættelsen tager O(2X), når kapaciteten af X er nået, og den afskrevne tid for hver indsættelse er O(1).
