Asymptotická složitost: Porovnání verzí
Smazaný obsah Přidaný obsah
Vyhození textu přesunutého do článku "Landauova notace" |
m →Amortizovaná časová složitost: použití |
||
Řádek 72:
==Amortizovaná časová složitost==
Amortizovaná časová složitost je průměrný čas potřebný pro vykonání určité operace v sekvenci operací ''v nejhorším případě''. Na rozdíl od ''časové složitosti v průměrném případě'' nevyužívá [[pravděpodobnost]]i a předpokladů o rozložení dat. U amortizované složitosti je průměrný čas na operaci skutečně zaručený.
Tato metoda vyžaduje znalost toho, které sekvence operací jsou vůbec možné. Nejčastěji se to týká analýzy [[datová struktura|datových struktur]], které si mezi jednotlivými operacemi udržují určitý stav. Některé datové struktury mají totiž takovou vnitřní organizaci, že na ní závisí složitost, a organizovanost dat se může během posloupnosti operací měnit. Základní myšlenka amortizované analýzy tkví v tom, že operace s velkou složitostí změní stav struktury tak, že tento nejhorší případ nemůže nastat po dlouhý čas, tudíž ''amortizuje'' svou cenu.
Amortizovaná složitoast se používá v případě, kdy některá konkrétní operace (typicky na datové struktuře) má v nejhorším případě velkou složitost, ale na vykonání této operace si dokážeme našetřit z předchozích operací v (libovolné) posloupnosti.
Jako jednoduchý příklad můžeme uvést specifickou implementaci [[dynamické pole|dynamického pole]], která zdvojnásobuje velikost pole pokaždé, když dojde k jeho naplnění. V tomto případě je tedy nutná realokace, v nejhorším případě tato operace potřebuje čas až O(''N''). Samotné vkládání prvků (bez nutnosti realokace) vyžaduje čas O(1), pro ''N'' prvků tedy také O(''N''). Pro vložení ''N'' prvků (včetně realokace) je tedy potřeba O(''N'') + O(''N'') = O(''N''), amortizovaný čas na jedno vložení prvku je pak O(''N'')/''N'' = O(1).
| |||