Asymptoticky optimální algoritmus - Asymptotically optimal algorithm

Ve výpočetní technice se o algoritmu říká, že je asymptoticky optimální, pokud zhruba řečeno pro velké vstupy vykonává v nejhorším případě konstantní faktor (nezávislý na velikosti vstupu) horší než nejlepší možný algoritmus. Jedná se o termín, s nímž se ve výzkumu počítačových věd běžně setkáváme v důsledku rozšířeného používání notace big-O .

Formálněji je algoritmus asymptoticky optimální s ohledem na konkrétní zdroj, pokud bylo prokázáno, že problém vyžaduje Ω (f (n)) daného zdroje a bylo prokázáno, že algoritmus používá pouze O (f (n)).

Tyto důkazy vyžadují předpoklad konkrétního modelu výpočtu , tj. Určitá omezení operací povolená se vstupními údaji.

Jako jednoduchý příklad je známo, že všechny druhy porovnání vyžadují v průměrných a nejhorších případech alespoň Ω ( n log n ) srovnání. Mergesort a heapsort jsou srovnávací druhy, které provádějí srovnání O ( n log n ), takže jsou v tomto smyslu asymptoticky optimální.

Pokud mají vstupní data nějaké apriorní vlastnosti, které lze využít při konstrukci algoritmů, kromě srovnání, mohou být možné asymptoticky rychlejší algoritmy. Například, pokud je známo, že N objekty jsou celá čísla z rozsahu [1, N], pak mohou být tříděny podle času O (N), např. Podle kbelíku .

Důsledkem asymptoticky optimálního algoritmu je, že pro dostatečně velké vstupy ho žádný algoritmus nemůže překonat o více než konstantní faktor. Z tohoto důvodu jsou asymptoticky optimální algoritmy ve výzkumu často považovány za „konec řádku“, za dosažení výsledku, který nelze dramaticky zlepšit. Naopak, pokud algoritmus není asymptoticky optimální, znamená to, že jak se velikost vstupu zvětšuje, algoritmus funguje stále horší než nejlepší možný algoritmus.

V praxi je užitečné najít algoritmy, které fungují lépe, i když nemají žádnou asymptotickou výhodu. Nové algoritmy mohou také představovat výhody, jako je lepší výkon na konkrétních vstupech, snížené využití zdrojů nebo jednodušší popis a implementace. Asymptoticky optimální algoritmy tedy nejsou vždy „koncem řádku“.

Ačkoli asymptoticky optimální algoritmy jsou důležité teoretické výsledky, asymptoticky optimální algoritmus nemusí být použit v řadě praktických situací:

  • Překonává pouze běžněji používané metody pro n nad rozsah praktických velikostí vstupů, jako jsou vstupy s více bity, než by se vešlo do jakéhokoli počítačového úložného systému.
  • Je příliš složitý, takže obtížnost jeho správného pochopení a implementace převažuje nad jeho potenciálním přínosem v rozsahu uvažovaných vstupních velikostí.
  • Vstupy, se kterými se v praxi setkáváme, spadají do zvláštních případů, které mají efektivnější algoritmy nebo které heuristické algoritmy se špatnými nejhoršími časy mohou přesto efektivně vyřešit.
  • Na moderních počítačích může být hardwarová optimalizace, jako je mezipaměť paměti a paralelní zpracování, „narušena“ asymptoticky optimálním algoritmem (za předpokladu, že analýza tyto hardwarové optimalizace nezohlednila). V tomto případě by mohly existovat neoptimální algoritmy, které lépe využijí tyto funkce a překonají optimální algoritmus na realistických datech.

Příkladem asymptoticky optimální algoritmus v praxi nepoužívá, je Bernard Chazelle lineární čase algoritmus je pro triangulaci jednoho jednoduchého polygonu . Dalším je datová struktura s možností změny velikosti publikovaná v dokumentu „Resizable Arrays in Optimal Time and Space“, který může indexovat v konstantním čase, ale na mnoha strojích přináší ve srovnání s běžným indexováním pole velkou praktickou pokutu.

Formální definice

Formálně předpokládejme, že máme teorém s dolní mezí, který ukazuje, že problém vyžaduje čas Ω (f ( n )) k vyřešení pro instanci (vstup) o velikosti n ( definici Ω viz notace big-O ). Potom se říká , že algoritmus, který řeší problém v čase O (f ( n )), je asymptoticky optimální. To lze také vyjádřit pomocí limitů: Předpokládejme, že b ( n ) je dolní mez doby běhu a daný algoritmus potřebuje čas t ( n ). Pak je algoritmus asymptoticky optimální, pokud:

Všimněte si, že pokud je tento limit, je vždy alespoň 1, jako t ( n ) ≥ b ( n ).

I když se obvykle používá pro časovou efektivitu, lze o algoritmu říci, že používá asymptoticky optimální prostor, náhodné bity, počet procesorů nebo jakýkoli jiný zdroj běžně měřený pomocí notace big-O.

Někdy mohou vágní nebo implicitní předpoklady způsobit, že není jasné, zda je algoritmus asymptoticky optimální. Například věta se spodní mezí může předpokládat konkrétní model abstraktního stroje , jako je tomu v případě srovnávacích druhů, nebo konkrétní organizaci paměti. Porušením těchto předpokladů by nový algoritmus mohl potenciálně asymptoticky překonat dolní mez a „asymptoticky optimální“ algoritmy.

Zrychlit

Neexistence asymptoticky optimálního algoritmu se nazývá zrychlení. Blumova věta o urychlení ukazuje, že s urychlením existují uměle vytvořené problémy. Je však otevřeným problémem, zda jsou dnes mnohé z nejznámějších algoritmů asymptoticky optimální nebo ne. Například existuje algoritmus O ( n α ( n )) pro hledání minimálních rozpětí stromů , kde α ( n ) je velmi pomalu rostoucí inverzní funkce Ackermanna , ale nejznámější dolní mez je triviální Ω ( n ) . Zda je tento algoritmus asymptoticky optimální, není známo, a pokud by byl vyřešen oběma způsoby, pravděpodobně by byl oslavován jako významný výsledek. Coppersmith a Winograd (1982) dokázali, že násobení matic má slabou formu zrychlení u omezené třídy algoritmů (bilineární identity typu Strassen s výpočtem lambda).

Viz také

Reference