Potenciální metoda - Potential method
v teorie výpočetní složitosti, potenciální metoda je metoda používaná k analýze amortizovaná časová a prostorová složitost a datová struktura, míra jeho výkonu nad sekvencemi operací, která vyhlazuje náklady na občasné, ale drahé operace.[1][2]
Definice amortizovaného času
V potenciální metodě je zvolena funkce that, která mapuje stavy datové struktury na nezáporná čísla. Li S je stav datové struktury, Φ (S) představuje práci, která byla v amortizované analýze zaúčtována („zaplacena“), ale dosud nebyla provedena. Tedy Φ (S) lze považovat za výpočet částky potenciální energie uložené v tomto stavu[1][2]. Potenciální hodnota před operací inicializace datové struktury je definována jako nula. Alternativně Φ (S) lze považovat za představující množství poruchy ve stavu S nebo jeho vzdálenost od ideálního stavu.
Nechat Ó být jakákoli jednotlivá operace v posloupnosti operací na nějaké datové struktuře, s Spřed označující stav datové struktury před operací Ó a Spo označující jeho stav po operaci Ó dokončil. Jakmile je vybráno Φ, je amortizovaná doba provozu Ó je definován jako
kde C je nezáporná konstanta proporcionality (v jednotkách času), která musí během analýzy zůstat pevná. To znamená, že amortizovaný čas je definován jako skutečný čas potřebný pro operaci plus C násobek rozdílu v potenciálu způsobeném operací.[1][2]
Při studiu asymptotická výpočetní složitost použitím velká O notace, konstantní faktory jsou irelevantní a tak konstantní C je obvykle vynechán.
Vztah mezi amortizovaným a skutečným časem
Přes svůj umělý vzhled poskytuje celková amortizovaná doba sledu operací platný horní hranice na skutečný čas pro stejnou posloupnost operací.
Pro jakoukoli posloupnost operací , definovat:
- Celková amortizovaná doba:
- Celkový skutečný čas:
Pak:
kde posloupnost hodnot potenciálních funkcí tvoří a teleskopická řada ve kterém se všechny výrazy kromě počátečních a konečných hodnot potenciální funkce ruší ve dvojicích. Přeskupením tohoto získáme:
Od té doby a , , takže amortizovaný čas lze použít k zajištění přesné horní hranice skutečného času sekvence operací, i když se amortizovaný čas pro jednotlivou operaci může od jeho skutečného času značně lišit.
Amortizovaná analýza vstupů v nejhorším případě
Zpravidla se amortizovaná analýza používá v kombinaci s a nejhorší případ předpoklad o vstupní posloupnosti. S tímto předpokladem, pokud X je typ operace, kterou může provádět datová struktura, a n je celé číslo definující velikost dané datové struktury (například počet položek, které obsahuje), poté amortizovaný čas pro operace typu X je definován jako maximum ze všech možných posloupností operací na datových strukturách velikosti n a všechny operace Ói typu X v pořadí, naběhlé doby provozu Ói.
S touto definicí lze čas provést sekvenci operací odhadnout vynásobením amortizovaného času pro každý typ operace v sekvenci počtem operací tohoto typu.
Příklady
Dynamické pole
A dynamické pole je datová struktura pro udržování pole položek, umožňující obojí náhodný přístup na pozice v rámci pole a schopnost zvětšit velikost pole o jednu. Je k dispozici v Jáva jako typ "ArrayList" a v Krajta jako typ „list“.
Dynamické pole může být implementováno datovou strukturou sestávající z pole A předmětů, nějaké délky N, spolu s číslem n ≤ N představující pozice v poli, které byly dosud použity. S touto strukturou mohou být náhodné přístupy k dynamickému poli implementovány přístupem ke stejné buňce interního pole A, a kdy n < N operace, která zvyšuje velikost dynamického pole, může být implementována jednoduše zvýšenímn. Kdy však n = N, je nutné změnit velikost Aa běžnou strategií je zdvojnásobení jeho velikosti a nahrazení A o nové pole o délce 2n.[3]
Tuto strukturu lze analyzovat pomocí potenciální funkce:
- Φ = 2n − N
Protože strategie změny velikosti vždy způsobí A aby byla alespoň z poloviny plná, je tato potenciální funkce vždy podle potřeby nezáporná.
Když operace zvětšení nevede k operaci změny velikosti, Φ se zvýší o 2, konstanta. Konstantní skutečný čas operace a konstantní nárůst potenciálu se proto spojí, aby operaci tohoto typu poskytly konstantní amortizovaný čas.
Když však operace zvětšení způsobí změnu velikosti, potenciální hodnota n po změně velikosti klesá na nulu. Přidělení nového interního pole A a kopírování všech hodnot ze starého interního pole do nového trvá O (n) skutečný čas, ale (s vhodnou volbou konstanty proporcionality C) toto je zcela zrušeno snížením potenciální funkce, což ponechává opět konstantní celkovou amortizovanou dobu pro operaci.
Ostatní operace datové struktury (čtení a zápis buněk pole bez změny velikosti pole) nezpůsobí změnu potenciální funkce a mají stejnou konstantní amortizovanou dobu jako jejich skutečný čas.[2]
Proto s touto volbou strategie změny velikosti a potenciální funkce potenciální metoda ukazuje, že všechny operace dynamického pole vyžadují konstantní amortizovaný čas. V kombinaci s nerovností související s amortizovaným časem a skutečným časem přes sekvence operací to ukazuje, že libovolná sekvence n operace dynamického pole trvá O (n) skutečný čas v nejhorším případě, a to navzdory skutečnosti, že některé z jednotlivých operací mohou samy trvat lineárně.[2]
Když dynamické pole zahrnuje operace, které zmenšují a zvětšují velikost pole, musí být potenciální funkce upravena tak, aby se zabránilo jejímu zániku. Jedním ze způsobů, jak to udělat, je nahradit výše uvedený vzorec pro Φ jeho absolutní hodnota.
Multi-Pop Stack
Zvažte a zásobník který podporuje následující operace:
- Inicializovat - vytvoří prázdný zásobník.
- Push - přidejte jeden prvek na hromádku a zvětšete hromádku o 1.
- Pop (k) - odstranit k prvky z horní části zásobníku, kde k není větší než aktuální velikost zásobníku
Pop (k) vyžaduje O (k) času, ale chceme ukázat, že všechny operace vyžadují O (1) amortizovaný čas.
Tuto strukturu lze analyzovat pomocí potenciální funkce:
- Φ = počet prvků v zásobníku
Toto číslo je podle potřeby vždy nezáporné.
Operace Push trvá konstantní čas a zvyšuje se o 1, takže jeho amortizovaná doba je konstantní.
Popová operace vyžaduje čas O (k), ale také snižuje o k, takže jeho amortizovaná doba je také konstantní.
To dokazuje, že jakákoli posloupnost m operace trvá O (m) skutečný čas v nejhorším případě.
Binární čítač
Zvažte a čelit reprezentován jako binární číslo a podpora následujících operací:
- Inicializovat: vytvoření čítače s hodnotou 0.
- Inc: přidejte 1 do počítadla.
- Číst: vrací aktuální hodnotu čítače.
V tomto příkladu jsme ne za použití transdichotomický model stroje, ale místo toho vyžadují jednu jednotku času na bitovou operaci v přírůstku. Chtěli bychom ukázat, že Inc trvá O (1) amortizovaný čas.
Tuto strukturu lze analyzovat pomocí potenciální funkce:
- Φ = počet bitů rovný 1 = hammingová váha (čelit)
Toto číslo je vždy nezáporné a začíná podle potřeby 0.
Operace Inc převrátí nejméně významný bit. Pak, pokud byly LSB převráceny z 1 na 0, je převrácen také další bit. To pokračuje, dokud se konečně bit nepřevrátí z 0 na 1, a v tomto okamžiku se převrácení zastaví. Pokud počitadlo původně končí v k 1 bit, otočíme celkem k+1 bity, přičemž skutečný čas k+1 a snížení potenciálu o k−1, takže amortizovaný čas je 2. Skutečný čas pro běh m Inc operace je O (m).
Aplikace
K analýze se běžně používá metoda potenciálních funkcí Fibonacci se hromadí, forma prioritní fronta ve kterém odebrání položky trvá logaritmický amortizovaný čas a všechny ostatní operace trvají konstantní amortizovaný čas.[4] Lze jej také použít k analýze roztáhnout stromy, samonastavovací forma binární vyhledávací strom s logaritmickou amortizovanou dobou na operaci.[5]
Reference
- ^ A b C Goodrich, Michael T.; Tamassia, Roberto (2002), „1.5.1 Amortisation Techniques“, Návrh algoritmu: základy, analýza a příklady internetu, Wiley, str. 36–38.
- ^ A b C d E Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „17.3 Potenciální metoda“. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. 412–416. ISBN 0-262-03293-7.
- ^ Goodrich a Tamassia, 1.5.2 Analýza implementace rozšiřitelného pole, str. 139–141; Cormen a kol., 17.4 Dynamické tabulky, str. 416–424.
- ^ Cormen a kol., 20. kapitola, „Fibonacciho hromady“, s. 476–497.
- ^ Goodrich a Tamassia, Oddíl 3.4, „Splay Trees“, str. 185–194.