Amortized time is de manier om de tijdcomplexiteit uit te drukken wanneer een algoritme slechts af en toe een zeer slechte tijdcomplexiteit heeft naast de tijdcomplexiteit die het grootste deel van de tijd voorkomt. Een goed voorbeeld zou een ArrayList zijn, een datastructuur die een array bevat en uitgebreid kan worden. Een andere definitie van Stack Overflow is de gemiddelde tijd die nodig is per bewerking, als je veel bewerkingen uitvoert.
Wanneer ArrayList de capaciteit van de array bereikt, dan maakt het een nieuwe array met de verdubbelde grootte van de oude array en kopieert alle items in de oude array naar de nieuwe array. In ArrayList bestaan twee tijdscomplexiteiten; de ene is O(1) en de andere is O(n).
Als de array in de array zijn capaciteit nog niet heeft bereikt en nog genoeg ruimte heeft om items in te voegen
Om in dit geval een item in de array in te voegen, hoeven we het item alleen maar na het laatste item te plaatsen. We hebben nog ruimte om items in te voegen.
Wanneer de array zijn capaciteit heeft bereikt en zichzelf opnieuw moet aanmaken met de verdubbelde grootte
De array heeft zijn capaciteit bereikt en we hebben geen slots meer beschikbaar. Dan moeten we een geheel nieuwe array maken met de verdubbelde grootte. En dan de items in de oude naar de nieuwe kopiëren, wat O(n) kost waarbij n de capaciteit van de oude array is en het slechtste geval.
Om deze twee tijdscomplexiteiten uit te drukken, wordt hier geamortiseerde tijd gebruikt. Wat het doet is ons laten beschrijven het ergste geval gebeurt een keer in de zoveel tijd elke keer dat de interne array raakte zijn capaciteit.
Maar een het gebeurt, zal het niet weer gebeuren voor zo lang dat de kosten is “afgeschreven.” (Cracking the Coding Interview 6th edition 43)
Dus hoe beschrijven we de twee complexiteiten?
In het geval van de ArrayList kunnen we zeggen dat
De insertie duurt O(n) als de capaciteit is bereikt, en de geamortiseerde tijd voor elke insertie is O(1).
Maar laten we nauwkeurig zijn voor de slechtste tijdcomplexiteit zonder deze tijd te vereenvoudigen. Als de capaciteit van de interne array begint met 1, dan zal de capaciteit 1, 2, 4, 8, 16… X zijn wanneer de capaciteit wordt bereikt en wordt verdubbeld. Het duurt 1, 2, 4, 8 16… X items om naar de nieuwe array te kopiëren, afhankelijk van de capaciteit die is bereikt. Dus de tijd complexiteit zal zijn 1 + 2 + 4 + 8 + 16 +… X. Als je denkt vanuit X, zal dit zijn X + X/2 + X/4 + X/8… + 1 = 2X ongeveer. Dus met andere woorden nauwkeurig,
De invoeging duurt O(2X) als de capaciteit van X is bereikt, en de geamortiseerde tijd voor elke invoeging is O(1).
