Ugrás a tartalomhoz

amortized analysis

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

amortized analysis (tsz. amortized analysises)

  1. (informatika) Az amortized analysis (magyarul: átlagos (összesített) elemzési módszer) egy algoritmus-elemzési technika, amely azt vizsgálja, hogy egy algoritmus vagy adatstruktúra műveleteinek átlagos idő- vagy erőforrásigénye hogyan viselkedik hosszú futás során, nem csupán egyetlen művelet legrosszabb esetére fókuszálva.


Mi az az amortized analysis?

  • Nem a legrosszabb esetet (worst-case) nézi egyetlen műveletre, hanem az összes művelet költségének átlaga.
  • Megmutatja, hogy bár bizonyos műveletek drágák lehetnek, ezeket a költségeket “el lehet osztani” a többi olcsóbb művelet között.
  • Így a hosszú távú, átlagos teljesítmény sokkal jobb lehet, mint a legrosszabb eset.


Mikor használjuk?

  • Dinamikus adatstruktúráknál, például dinamikusan bővülő tömbök (dynamic arrays) esetén.
  • Amikor egy művelet néha nagyon drága, de ritka.
  • Például: halmazok, verem, sor, vagy bonyolultabb struktúrák működésének elemzésénél.


Példa: Dinamikusan bővülő tömb

  • Egy tömb, amely előre fix méretű, de ha megtelik, a méretét megduplázzuk.
  • A beszúrási művelet általában O(1) idő, de ha újra kell méretezni, akkor egy beszúrás drága lehet, O(n).
  • Az amortizált elemzés megmutatja, hogy n beszúrás összesített költsége O(n), így egy beszúrás amortizált időkomplexitása O(1).


Amortizált elemzési technikák

  1. Aggregate analysis (Összesített elemzés): Összes költséget nézzük műveletre, majd átlagoljuk.
  2. Accounting method (Számlázási módszer): Minden művelethez „költséget” rendelünk, előre fizetünk a drágább műveletekre.
  3. Potential method (Potenciál módszer): Egy potenciálfüggvényt használunk, amely a struktúra „energiaállapotát” méri, és ezt használjuk a költségek elosztására.


Összefoglaló

Az amortized analysis segítségével a ritkán előforduló drága műveletek költségeit elosztjuk a gyakrabban előforduló olcsó műveletek között, így reálisabb képet kapunk az algoritmus átlagos teljesítményéről hosszú távon.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=amortized_analysis&oldid=3497815”