Amortized time är ett sätt att uttrycka tidskomplexiteten när en algoritm har en mycket dålig tidskomplexitet som bara inträffar en gång i tiden, förutom den tidskomplexitet som inträffar oftast. Ett bra exempel är en ArrayList som är en datastruktur som innehåller en array och som kan utökas. En annan definition från Stack Overflow är genomsnittlig tidsåtgång per operation, om man gör många operationer.
När ArrayList når arraykapaciteten i den, skapas en ny array med den dubbla storleken på den gamla arrayen och alla objekt i den gamla arrayen kopieras till den nya arrayen. I ArrayList finns två tidskomplexiteter; den ena är O(1) och den andra är O(n).
När arrayen i den inte har nått sin kapacitet och fortfarande har tillräckligt med utrymme för att infoga objekt
För att infoga ett objekt i arrayen i det här fallet behöver vi bara sätta objektet efter det sista objektet. Vi har fortfarande utrymme att infoga objekt.
När matrisen i den har nått sin kapacitet och behöver återskapa sig själv med den fördubblade storleken
Matrisen har nått sin kapacitet och vi har inga tillgängliga platser. Då måste vi skapa en helt ny array med den fördubblade storleken. Och sedan kopiera objekten i den gamla till den nya, vilket tar O(n) där n är kapaciteten hos den gamla matrisen och det värsta fallet.
För att uttrycka dessa två tidskomplexitet, är amorterad tid här. Vad den gör är att låta oss beskriva att det värsta fallet händer en gång i tiden varje gång den interna matrisen når sin kapacitet.
Men när det väl händer kommer det inte att hända igen på så lång tid att kostnaden är ”avskriven”. (Cracking the Coding Interview 6th edition 43)
Så hur beskriver vi de två komplexiteterna?
I fallet med ArrayList kan vi säga att
Insättningen tar O(n) när kapaciteten har nåtts och den avskrivna tiden för varje insättning är O(1).
Men låt oss vara exakta när det gäller värsta tidskomplexiteten utan att förenkla den här gången. Om den interna arraykapaciteten börjar med 1 kommer kapaciteten att vara 1, 2, 4, 8, 16… X när den når kapaciteten och blir dubblerad. Det tar 1, 2, 4, 8 16… X objekt att kopiera till den nya matrisen beroende på vilken kapacitet som har nåtts. Tidskomplexiteten blir alltså 1 + 2 + 4 + 8 + 16 + … X. Om man utgår från X blir det ungefär X + X/2 + X/4 + X/8 … + 1 = 2X. Med andra ord:
Införandet tar O(2X) när kapaciteten i X har uppnåtts, och den avskrivna tiden för varje införande är O(1).
