Amortizovaná analýza - Amortized analysis

V počítačové vědě je amortizovaná analýza metodou pro analýzu složitosti daného algoritmu nebo toho, kolik zdroje, zejména času nebo paměti, potřebuje ke spuštění . Motivací pro amortizovanou analýzu je, že pohled na dobu nejhoršího případu může být příliš pesimistický. Namísto toho amortizovaná analýza průměruje dobu provozu operací v sekvenci přes tuto sekvenci. Na závěr: „Amortizovaná analýza je užitečný nástroj, který doplňuje další techniky, jako je analýza nejhorších a průměrných případů .“

Pro danou operaci algoritmu mohou určité situace, např. Vstupní parametrizace nebo obsah datové struktury, znamenat značné náklady na zdroje, zatímco jiné situace nemusí být tak nákladné. Amortizovaná analýza zohledňuje jak nákladné, tak méně nákladné operace společně v celém sledu operací. To může zahrnovat účtování různých typů vstupů, délky vstupu a dalších faktorů, které ovlivňují jeho výkon.

Dějiny

Amortizovaná analýza původně vzešla z metody zvané agregovaná analýza, která je nyní zahrnuta do amortizované analýzy. Tato technika byla poprvé formálně představena Robertem Tarjanem v jeho článku z roku 1985 Amortized Computational Complexity , který řešil potřebu užitečnější formy analýzy než používané běžné pravděpodobnostní metody. Amortizace byla původně použita pro velmi specifické typy algoritmů, zejména pro ty, které zahrnovaly binární stromy a sjednocovací operace. Nyní je však všudypřítomný a vstupuje do hry také při analýze mnoha dalších algoritmů.

Metoda

Amortizovaná analýza vyžaduje znalost toho, které série operací jsou možné. To je nejčastěji případ datových struktur , které mají stav, který přetrvává mezi operacemi. Základní myšlenkou je, že operace nejhoršího případu může změnit stav takovým způsobem, že k nejhoršímu případu již dlouho nemůže dojít, a tím „amortizovat“ své náklady.

Obecně existují tři metody provádění amortizované analýzy: agregační metoda, účetní metoda a potenciální metoda . Všechny tyto poskytují správné odpovědi; výběr, který použít, závisí na tom, který je pro konkrétní situaci nejvhodnější.

Souhrnná analýza určuje horní hranici T ( n ) z celkových nákladů na sekvenci n operací, poté vypočítá amortizovanou cenu na T ( n ) / n .
Způsob účtování je forma souhrnné analýze, která přiřazuje každému provozu systém zůstatkové náklady , které se může lišit od jeho skutečné náklady. Počáteční operace mají amortizované náklady vyšší než jejich skutečné náklady, což akumuluje ušetřený „kredit“, který platí za pozdější operace s amortizovanými náklady nižšími než jejich skutečné náklady. Protože kredit začíná nulou, skutečné náklady na sekvenci operací se rovnají amortizovaným nákladům minus akumulovaný kredit. Protože je vyžadováno, aby kredit nebyl záporný, jsou amortizované náklady horní hranicí skutečných nákladů. Mnoho krátkodobých operací obvykle takový kredit akumuluje v malých přírůstcích, zatímco vzácné dlouhodobé operace jej drasticky snižují.
Potenciál metoda je forma účetní metody, kde je uložen úvěr vypočtenou jako funkce (dále jen „potenciální“) stavu datové struktury. Amortizovaná cena je okamžitá cena plus změna potenciálu.

Příklady

Dynamické pole

Amortizovaná analýza operace push pro dynamické pole

Zvažte dynamické pole, které roste s tím, jak se do něj přidává více prvků, například ArrayListv Javě nebo std::vectorv C ++. Pokud bychom začali s dynamickým polem velikosti 4, mohli bychom na něj natlačit 4 prvky a každá operace by trvala konstantní čas . Přesunutí pátého prvku do tohoto pole by však trvalo déle, protože pole by muselo vytvořit nové pole dvojnásobku aktuální velikosti (8), zkopírovat staré prvky do nového pole a poté přidat nový prvek. Další tři push operace by podobně trvaly konstantní čas a pak by následné přidání vyžadovalo další pomalé zdvojnásobení velikosti pole.

Obecně pokud vezmeme v úvahu libovolný počet stisknutí n + 1 na pole velikosti n , všimneme si, že operace push vyžadují konstantní čas, kromě posledního, který potřebuje čas na provedení operace zdvojnásobení velikosti. Protože bylo celkem n + 1 operací, můžeme vzít průměr z toho a zjistit, že tlačení prvků do dynamického pole trvá :, konstantní čas. ${\ displaystyle \ Theta (n)}$ ${\ Displaystyle {\ tfrac {n \ Theta (1)+\ Theta (n)} {n+1}} = \ Theta (1)}$

Fronta

Zobrazena je Ruby implementace Queue , datové struktury FIFO :

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

Operace zařazování jen tlačí prvek na vstupní pole; tato operace nezávisí na délkách vstupu ani výstupu, a proto běží ve stálém čase.

Operace vyřazení je však komplikovanější. Pokud výstupní pole již obsahuje některé prvky, pak dequeue běží v konstantním čase; jinak dequeue potřebuje čas na přidání všech prvků do výstupního pole ze vstupního pole, kde n je aktuální délka vstupního pole. Po zkopírování n prvků ze vstupu můžeme provést n dequeue operací, z nichž každá trvá konstantní čas, než bude výstupní pole opět prázdné. Můžeme tedy provést sekvenci n dequeue operací pouze za čas, což znamená, že amortizovaný čas každé operace dequeue je . ${\ Displaystyle O (n)}$ ${\ Displaystyle O (n)}$ ${\ displaystyle O (1)}$

Alternativně můžeme účtovat náklady na kopírování libovolné položky ze vstupního pole do výstupního pole do dřívější operace zařazování pro danou položku. Toto schéma nabíjení zdvojnásobuje amortizovaný čas pro zařazení do fronty, ale zkracuje amortizovaný čas pro dequeue na . ${\ displaystyle O (1)}$

Běžné použití

V běžném používání je „amortizovaný algoritmus“ algoritmus, u kterého amortizovaná analýza prokázala dobrou výkonnost.
Online algoritmy běžně používají amortizovanou analýzu.

Reference

Literatura

„Přednáška 7: Amortizovaná analýza“ (PDF) . Univerzita Carnegie Mellon . Citováno 14. března 2015 .
Allan Borodin a Ran El-Yaniv (1998). Online výpočet a konkurenční analýza . s. 20, 141.

Languages

In other projects