Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Amortizovaná složitost

Definice (Amortizovaná složitost)

Amortizovaná časová složitost počítá průměrný čas na jednu operaci při provedení posloupnosti operací. Používá se typicky pro počítání časové složitosti operací nad datovými strukturami. Dává realističtější horní odhad složitosti posloupnosti operací, než počítání s nejhorším případem u každé operace.

Agregační metoda

Spočítáme (nejhorší možný) čas pro posloupnost operací. Amortizovaná cena jedné operace je potom .

Účetní metoda

Od každé operace vybereme určitý obnos, ze kterého zaplatíme za danou operaci a pokud něco zbude, dáme to na účet. Pokud je operace dražší než kolik je její obnos, tak potřebný rozdíl vybereme z účtu. Zůstatek na účtu musí být stále nezáporný. Pokud uspějeme, tak obnos = amortizovaná cena jedné operace.

Poznámka

Jde o to, že některá operace může trvat krátce, ale rozháže datovou strukturu, takže následující operace potřebují víc času. Nebo naopak trvá dlouho a datovou strukturu uspořádá, takže ostatní operace jsou kratší.