Anàlisis d'amortisació

En ciències de la computació, especialment l'anàlisis d'algoritmes, el anàlisis d'amortisació considera el promig de temps d'eixecució per més d'una operació en el pijor dels casos, la seqüència de les operacions. L'anàlisis d'amortisació diferix del promig de rendiment en cas que no es tracte de provabilitat; l'anàlisis d'amortisació garantisa l'operació per més temps prenent en conte el pijor dels casos en el rendiment.

El método requerix el coneiximent d'esta série d'operacions que són possibles. Est és el cas més comú en estructures de senyes, que han estat que persistix entre les operacions. L'idea bàsica és que el pijor dels casos l'operació pot alterar l'estat de tal manera que el pijor dels casos no pot ocórrer de nou per un llarc temps, per lo tant queda "amortisat" el seu cost.

Com a eixemple simple, en una implementació específica d'array dinàmics, doblem el tamany del array cada volta que es reblixca. Per açò, és necessari reasignar el array, i en el pijor dels casos pot requerir una inserció O (n). No obstant, una seqüència de n insercions sempre es pot fer en O (n) temps, de modo que el temps d'amortisació per operació és O (n) / n = O (1).

L'anàlisis del case promig i anàlisis provabilístic no són lo mateix en anàlisis d'amortisació. En anàlisis del case promig, estem en un promig de totes les possibles entrades, en l'anàlisis provabilístic, estem en un promig de totes les possibles opcions a l'encert; en l'anàlisis d'amortisació, estem en promig més d'una seqüència d'operacions. Amortisen anàlisis assumix el pijor dels casos d'entrada i, normalment, no permet opcions a l'encert.

Existixen vàries tècniques utilisades en l'anàlisis amortisat:

• Anàlisis global determina el llímit superior T (n) en el cost total d'una seqüència de n operacions, i després calcula el cost mig a T (n) / n.

• Método Contable permet determinar el cost individual de cada operació, que combina el seu immediat temps d'eixecució i la seua influència en el temps d'eixecució de les futures operacions. Generalment, molts operacions de curta duració acumulen una "deute" de situació desfavorable en menuts increments, mentres que les operacions de llarga duració disminuïxen dràsticament.

• Método potencial és com el método, pero les operacions primerenques que sobrecarreguen la conte poden ser compensades cobrant menys del conte més vesprada.

Referències

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein. Introduction to Algorithms, Segona edició. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítul 17: Amortized Analysis, págs.405–430.