Základy teorie výpočetní složitosti EITC/IS/CCTF

Protože množství zdrojů potřebných ke spuštění algoritmu se mění s velikostí vstupu, složitost se obvykle vyjadřuje jako funkce f(n), kde n je velikost vstupu a f(n) je buď nejhorší případ složitosti ( maximální množství zdrojů požadovaných napříč všemi vstupy velikosti n) nebo průměrná složitost případu (průměr množství zdrojů na všech vstupech velikosti n). Počet požadovaných elementárních operací na vstupu o velikosti n se běžně uvádí jako časová složitost, kde se předpokládá, že elementární operace zabírají na konkrétním počítači konstantní množství času a mění se pouze konstantním faktorem, když jsou spuštěny na jiném stroji. Množství paměti požadované algoritmem na vstupu o velikosti n je známé jako prostorová složitost.

Čas je nejčastěji považovaný za zdroj. Když je termín „složitost“ použit bez kvalifikátoru, obvykle se vztahuje na složitost času.

Tradiční jednotky času (sekundy, minuty atd.) se v teorii složitosti nepoužívají, protože jsou příliš závislé na zvoleném počítači a technologickém pokroku. Počítač dnes může například provádět algoritmus podstatně rychleji než počítač ze 1960. let, ale je to způsobeno spíše technologickými průlomy v počítačovém hardwaru než vlastní kvalitou algoritmu. Cílem teorie složitosti je kvantifikovat inherentní časové potřeby algoritmů nebo základní časová omezení, která by algoritmus uvalil na jakýkoli počítač. Toho je dosaženo počítáním, kolik základních operací bylo provedeno během výpočtu. Tyto procedury se běžně označují jako kroky, protože se má za to, že zabírají konstantní čas na konkrétním stroji (tj. nejsou ovlivněny množstvím vstupu).

Dalším důležitým zdrojem je množství paměti počítače potřebné k provádění algoritmů.

Dalším často používaným zdrojem je množství aritmetických operací. V tomto scénáři se používá termín „aritmetická složitost“. Časová složitost je obecně součinem aritmetické složitosti konstantním faktorem, pokud je známo horní omezení velikosti binární reprezentace čísel, která se vyskytují během výpočtu.

Velikost celých čísel používaných během výpočtu není u mnoha metod omezena a je nerealistické předpokládat, že aritmetické operace vyžadují pevné množství času. V důsledku toho může být časová složitost, známá také jako bitová složitost, výrazně vyšší než aritmetická složitost. Aritmetická obtížnost výpočtu determinantu celočíselné matice nn je například O(n^3) pro standardní techniky (Gaussova eliminace). Protože se velikost koeficientů může během výpočtu exponenciálně rozšiřovat, bitová složitost stejných metod je v n exponenciální. Pokud jsou tyto techniky použity ve spojení s multimodulární aritmetikou, lze bitovou složitost snížit na O(n^4).

Bitová složitost, ve formálních termínech, odkazuje na počet operací na bitech potřebných ke spuštění algoritmu. Ve většině výpočetních paradigmat se rovná časové složitosti až do konstantního faktoru. Počet operací na strojových slovech požadovaných počítači je úměrný bitové složitosti. Pro realistické modely výpočtu jsou tedy časová a bitová složitost totožné.

Zdroj, který je často zvažován při třídění a vyhledávání, je množství porovnávání záznamů. Pokud jsou data dobře uspořádána, je to dobrý ukazatel časové náročnosti.

Na všech potenciálních vstupech je nemožné počítat počet kroků v algoritmu. Protože složitost vstupu roste s jeho velikostí, je běžně reprezentován jako funkce velikosti vstupu n (v bitech), a tak je složitost funkcí n. Pro stejně velké vstupy se však složitost algoritmu může podstatně lišit. V důsledku toho se rutinně používá celá řada funkcí složitosti.

Složitost nejhoršího případu je součet veškeré složitosti pro všechny vstupy velikosti n, zatímco složitost průměrného případu je součtem veškeré složitosti všech vstupů velikosti n (to dává smysl, protože počet možných vstupů dané velikosti je konečný). Je-li použit termín „složitost“, aniž by byl dále definován, bere se v úvahu nejhorší případ časové složitosti.

Složitost nejhoršího a průměrného případu je notoricky obtížné správně vypočítat. Navíc tyto přesné hodnoty mají jen malou praktickou aplikaci, protože jakákoli změna ve strojovém nebo výpočetním paradigmatu by mírně změnila složitost. Navíc využití zdrojů není důležité pro malé hodnoty n, proto je snadnost implementace často přitažlivější než nízká složitost pro malé n.

Z těchto důvodů je největší pozornost věnována chování složitosti pro vysoké n, tedy jejímu asymptotickému chování, když se n blíží nekonečnu. V důsledku toho se k označení složitosti běžně používá velká notace O.

Výpočtové modely

Pro stanovení složitosti je důležitý výběr výpočetního modelu, který spočívá ve specifikaci podstatných operací, které se provádějí za jednotku času. To je někdy označováno jako multipáskový Turingův stroj, když není konkrétně popsáno výpočetní paradigma.

Deterministický model výpočtu je model, ve kterém jsou následující stavy stroje a operace, které mají být provedeny, zcela definovány předchozím stavem. Rekurzivní funkce, lambda počet a Turingovy stroje byly prvními deterministickými modely. Stroje s náhodným přístupem (také známé jako RAM-stroje) jsou oblíbeným vzorem pro simulaci reálných počítačů.

Když výpočetní model není definován, obvykle se předpokládá vícepáskový Turingův stroj. Na vícepáskových Turingových strojích je časová složitost stejná jako na strojích RAM pro většinu algoritmů, i když k dosažení této ekvivalence může být zapotřebí značná pozornost v tom, jak jsou data uložena v paměti.

V některých krocích výpočtu v nedeterministickém modelu práce na počítači, jako jsou nedeterministické Turingovy stroje, lze provést různé volby. V teorii složitosti jsou všechny proveditelné možnosti zvažovány současně a nedeterministická časová složitost je množství času potřebného, ​​když jsou vždy učiněny nejlepší volby. Jinak řečeno, výpočet se provádí souběžně na tolika (identických) procesorech, kolik je potřeba, a nedeterministický výpočetní čas je čas, který první procesor potřebuje k dokončení výpočtu. Tento paralelismus lze použít v kvantovém počítání pomocí superponovaných zapletených stavů při spouštění specializovaných kvantových algoritmů, jako je například Shorova faktorizace malých celých čísel.

I když takový výpočetní model není v současné době proveditelný, má teoretický význam, zejména ve vztahu k problému P = NP, který se ptá, zda třídy složitosti vytvořené použitím „polynomiálního času“ a „nedeterministického polynomiálního času“ jsou nejméně horní. hranice jsou stejné. Na deterministickém počítači vyžaduje simulace NP-algoritmu „exponenciální čas“. Pokud lze úlohu vyřešit v polynomiálním čase na nedeterministickém systému, patří do třídy obtížnosti NP. Pokud je problém v NP a není jednodušší než jakýkoli jiný problém NP, říká se, že je NP-úplný. Problém batohu, problém cestujícího obchodníka a booleovský problém splnitelnosti jsou všechny NP-úplné kombinatorické problémy. Nejznámější algoritmus má exponenciální složitost pro všechny tyto problémy. Pokud by některý z těchto problémů mohl být vyřešen v polynomiálním čase na deterministickém stroji, pak by všechny NP problémy mohly být vyřešeny také v polynomiálním čase a bylo by stanoveno P = NP. Od roku 2017 se obecně předpokládá, že P NP, z čehož vyplývá, že nejhorší situace problémů NP se zásadně obtížně řeší, tj. trvají mnohem déle, než je jakékoli možné časové rozpětí (desítky let) při zajímavé délce vstupu.

Paralelní a distribuované výpočty

Paralelní a distribuované výpočty zahrnují rozdělení zpracování mezi více procesorů, které všechny pracují současně. Základním rozdílem mezi různými modely je způsob zasílání dat mezi procesory. Přenos dat mezi procesory je typicky velmi rychlý při paralelním počítání, zatímco přenos dat mezi procesory při distribuovaných počítáních probíhá po síti a je tedy podstatně pomalejší.

Výpočet na N procesorech zabere alespoň podíl N času, který zabere jeden procesor. Ve skutečnosti, protože některé dílčí úlohy nelze paralelizovat a některé procesory mohou muset čekat na výsledek od jiného procesoru, nebude této teoreticky ideální hranice nikdy dosaženo.

Klíčovým problémem složitosti je tedy vývoj algoritmů tak, aby součin výpočetního času počtem procesorů byl co nejblíže času potřebnému k provedení stejného výpočtu na jediném procesoru.

Kvantový výpočet

Kvantový počítač je počítač s výpočetním modelem založeným na kvantové mechanice. Churchova-Turingova teze platí pro kvantové počítače, z čehož vyplývá, že jakýkoli problém, který může kvantový počítač vyřešit, může být vyřešen také Turingovým strojem. Některé úlohy by však teoreticky mohly být řešeny spíše pomocí kvantového počítače než klasického počítače s výrazně nižší časovou složitostí. To je zatím přísně teoretické, protože nikdo neví, jak vyvinout praktický kvantový počítač.

Teorie kvantové složitosti byla vytvořena, aby prozkoumala různé typy problémů, které lze vyřešit pomocí kvantových počítačů. Využívá se v postkvantové kryptografii, což je proces vytváření kryptografických protokolů, které jsou odolné vůči útokům kvantových počítačů.

Složitost problému (spodní hranice)

Infimum složitosti algoritmů, které mohou problém vyřešit, včetně neobjevených technik, je složitost problému. V důsledku toho se složitost problému rovná složitosti jakéhokoli algoritmu, který jej řeší.

V důsledku toho jakákoli složitost uvedená ve velkém O znamená složitost jak algoritmu, tak doprovodného problému.

Na druhou stranu je často obtížné získat netriviální dolní meze složitosti problému a existuje jen málo strategií, jak toho dosáhnout.

Aby se vyřešila většina problémů, musí být načtena všechna vstupní data, což zabere čas úměrný velikosti dat. Výsledkem je, že takové problémy mají alespoň lineární složitost, nebo ve velké omega notaci složitost Ω(n).

Některé problémy, jako jsou problémy v počítačové algebře a výpočetní algebraické geometrii, mají velmi rozsáhlá řešení. Protože výstup musí být zapsán, je složitost omezena maximální velikostí výstupu.

Počet porovnání požadovaných pro třídicí algoritmus má nelineární dolní mez Ω(nlogn). V důsledku toho jsou nejlepší třídicí algoritmy nejúčinnější, protože jejich složitost je O(nlogn). Skutečnost, že existuje n! způsoby, jak organizovat n věcí, vedou k této spodní hranici. Protože každé srovnání rozděluje tuto sbírku n! objednávky na dva kusy, počet N porovnání potřebných k rozlišení všech objednávek musí být 2N > n!, což znamená O(nlogn) podle Stirlingova vzorce.

Snížení problému na jiný problém je běžnou strategií pro získání omezení složitosti.

Algoritmový vývoj

Vyhodnocení složitosti algoritmu je důležitým prvkem procesu návrhu, protože poskytuje užitečné informace o výkonu, který lze očekávat.

Je častým nedorozuměním, že v důsledku Moorova zákona, který předpovídá exponenciální růst výkonu moderního počítače, bude hodnocení složitosti algoritmů méně relevantní. To je nesprávné, protože zvýšený výkon umožňuje zpracování velkého množství dat (velká data). Například jakýkoli algoritmus by měl fungovat dobře za méně než sekundu při abecedním řazení seznamu několika stovek záznamů, jako je bibliografie knihy. Na druhou stranu, pro milion záznamů (například telefonní čísla velkého města) by základní algoritmy, které vyžadují porovnání O(n2), musely provést bilion porovnání, což by při rychlosti 10 zabralo tři hodiny. milionů srovnání za sekundu. Quicksort a merge sort na druhé straně vyžadují pouze porovnání nlogn (jako složitost průměrného případu pro první případ, jako složitost nejhoršího případu pro druhý). To vytváří přibližně 30,000,000 1,000,000 3 srovnání pro n = 10 XNUMX XNUMX, což by při XNUMX milionech srovnání za sekundu trvalo pouze XNUMX sekundy.

V důsledku toho může posouzení složitosti umožnit eliminaci mnoha neefektivních algoritmů před implementací. To lze také použít k doladění složitých algoritmů, aniž byste museli testovat všechny možné varianty. Studium složitosti umožňuje zaměřit úsilí na zvýšení efektivity implementace stanovením nejnákladnějších kroků složitého algoritmu.