Az amortizált idő az időbonyolultság kifejezési módja, amikor egy algoritmusnak a legtöbbször előforduló időbonyolultság mellett csak egyszer van nagyon rossz időbonyolultsága. Jó példa lehet egy ArrayList, amely egy tömböt tartalmazó és bővíthető adatszerkezet. A Stack Overflow másik definíciója az egy műveletre fordított átlagos idő, ha sok műveletet végzünk.
Amikor az ArrayList eléri a benne lévő tömbkapacitást, akkor létrehoz egy új tömböt a régi tömb duplájával, és a régi tömb összes elemét átmásolja az új tömbbe. Az ArrayListben két időbonyolultság létezik; az egyik O(1), a másik O(n).
Ha a benne lévő tömb nem érte el a kapacitását, és még van elég hely az elemek beszúrására
Az elem beszúrásához a tömbbe ebben az esetben csak az utolsó elem után kell helyeznünk az elemet. Még van helyünk az elemek beszúrására.
Ha a benne lévő tömb elérte a kapacitását, és újra létre kell hoznia magát a megduplázott mérettel
A tömb elérte a kapacitását, és nincs szabad helyünk. Ekkor egy teljesen új tömböt kell létrehoznunk a megduplázott mérettel. Majd a régiben lévő elemeket átmásolni az újba, ami O(n) időt vesz igénybe, ahol n a régi tömb kapacitása és a legrosszabb eset.
Az említett két időbonyolultság kifejezésére itt az amortizált idő szolgál. Azt teszi, hogy leírjuk, hogy a legrosszabb eset egyszer-egyszer megtörténik, valahányszor a belső tömb elérte a kapacitását.
De ha egyszer megtörténik, akkor olyan sokáig nem fog megismétlődni, hogy a költség “amortizálódik”. (Cracking the Coding Interview 6. kiadás 43)
Hogyan írjuk le tehát a két bonyolultságot?
Az ArrayList esetében azt mondhatjuk, hogy
A beszúrás O(n) időt vesz igénybe, amikor a kapacitás elérte, és az amortizált idő minden beszúrásnál O(1).
De legyünk pontosak a legrosszabb időbeli bonyolultságra anélkül, hogy ezt az időt egyszerűsítenénk. Ha a belső tömb kapacitása 1-gyel kezdődik, akkor a kapacitások 1, 2, 4, 8, 16… X lesz, amikor eléri a kapacitást és megduplázódik. Az elért kapacitástól függően 1, 2, 4, 8 16… X elemet kell az új tömbbe másolni. Tehát az időbonyolultság 1 + 2 + 4 + 8 + 16 +… X. Ha X-ből gondolkodik, akkor ez X + X/2 + X/4 + X/8… + 1 = 2X lesz körülbelül. Tehát más szóval pontosan,
A beszúrás O(2X) időt vesz igénybe, ha X kapacitását elértük, és az amortizált idő minden egyes beszúrásnál O(1).
