Základy teórie výpočtovej zložitosti EITC/IS/CCTF

Pretože množstvo zdrojov potrebných na spustenie algoritmu sa mení s veľkosťou vstupu, zložitosť sa zvyčajne vyjadruje ako funkcia f(n), kde n je veľkosť vstupu a f(n) je buď najhorší prípad zložitosti ( maximálne množstvo zdrojov požadovaných naprieč všetkými vstupmi veľkosti n) alebo priemerná zložitosť prípadu (priemer množstva zdrojov na všetkých vstupoch veľkosti n). Počet požadovaných elementárnych operácií na vstupe s veľkosťou n sa bežne uvádza ako časová zložitosť, pričom sa predpokladá, že elementárne operácie zaberajú na konkrétnom počítači konštantný čas a menia sa iba konštantným faktorom, keď sú spustené na inom stroji. Množstvo pamäte, ktorú vyžaduje algoritmus na vstupe veľkosti n, sa nazýva priestorová zložitosť.

Čas je najčastejšie považovaný za zdroj. Keď sa výraz „zložitosť“ používa bez kvalifikátora, zvyčajne sa vzťahuje na zložitosť času.

Tradičné jednotky času (sekundy, minúty atď.) sa v teórii zložitosti nepoužívajú, pretože sú príliš závislé od zvoleného počítača a technologického pokroku. Napríklad počítač dnes dokáže vykonať algoritmus podstatne rýchlejšie ako počítač zo 1960-tych rokov XNUMX. storočia, ale je to skôr vďaka technologickým prelomom v počítačovom hardvéri, než kvôli vlastnej kvalite algoritmu. Cieľom teórie zložitosti je kvantifikovať inherentné časové potreby algoritmov alebo základné časové obmedzenia, ktoré by algoritmus uvalil na akýkoľvek počítač. To sa dosiahne spočítaním, koľko základných operácií sa vykoná počas výpočtu. Tieto postupy sa bežne označujú ako kroky, pretože sa predpokladá, že na konkrétnom stroji zaberajú konštantný čas (tj nie sú ovplyvnené množstvom vstupu).

Ďalším dôležitým zdrojom je množstvo počítačovej pamäte potrebnej na vykonávanie algoritmov.

Ďalším často využívaným zdrojom je množstvo aritmetických operácií. V tomto scenári sa používa termín „aritmetická zložitosť“. Časová zložitosť je vo všeobecnosti súčinom aritmetickej zložitosti konštantným faktorom, ak je známe horné obmedzenie veľkosti binárnej reprezentácie čísel, ktoré sa vyskytujú počas výpočtu.

Veľkosť celých čísel použitých počas výpočtu nie je pre mnohé metódy obmedzená a je nereálne predpokladať, že aritmetické operácie vyžadujú pevné množstvo času. V dôsledku toho môže byť časová zložitosť, známa aj ako bitová zložitosť, výrazne vyššia ako aritmetická zložitosť. Aritmetická náročnosť výpočtu determinantu celočíselnej matice nn je napríklad O(n^3) pre štandardné techniky (Gaussova eliminácia). Pretože veľkosť koeficientov sa môže počas výpočtu exponenciálne rozširovať, bitová zložitosť rovnakých metód je exponenciálna v n. Ak sa tieto techniky použijú v spojení s multimodulárnou aritmetikou, bitová zložitosť sa môže znížiť na O(n^4).

Bitová zložitosť vo formálnom vyjadrení označuje počet operácií na bitoch potrebných na spustenie algoritmu. Vo väčšine výpočtových paradigiem sa rovná časovej zložitosti až po konštantný faktor. Počet operácií na strojových slovách požadovaných počítačmi je úmerný bitovej zložitosti. Pre realistické modely výpočtu sú teda časová a bitová zložitosť totožné.

Zdrojom, ktorý sa často zvažuje pri triedení a vyhľadávaní, je množstvo porovnávaní záznamov. Ak sú údaje dobre usporiadané, je to dobrý indikátor časovej zložitosti.

Na všetkých potenciálnych vstupoch nie je možné spočítať počet krokov v algoritme. Pretože zložitosť vstupu rastie s jeho veľkosťou, je bežne reprezentovaný ako funkcia veľkosti vstupu n (v bitoch), takže zložitosť je funkciou n. Pre vstupy rovnakej veľkosti sa však zložitosť algoritmu môže podstatne líšiť. V dôsledku toho sa bežne používajú rôzne funkcie zložitosti.

Zložitosť najhoršieho prípadu je súčet všetkej zložitosti pre všetky vstupy veľkosti n, zatiaľ čo zložitosť priemerného prípadu je súčtom všetkej zložitosti pre všetky vstupy veľkosti n (to dáva zmysel, pretože počet možných vstupov danej veľkosti je konečný). Keď sa výraz „zložitosť“ použije bez toho, aby bol bližšie definovaný, berie sa do úvahy najhorší prípad časovej zložitosti.

Zložitosť najhoršieho a priemerného prípadu je notoricky ťažké správne vypočítať. Okrem toho tieto presné hodnoty majú malé praktické využitie, pretože akákoľvek zmena v stroji alebo výpočtovej paradigme by mierne zmenila zložitosť. Okrem toho využitie zdrojov nie je dôležité pre malé hodnoty n, preto je jednoduchosť implementácie často príťažlivejšia ako nízka zložitosť pre malé n.

Z týchto dôvodov sa väčšina pozornosti venuje správaniu sa zložitosti pre vysoké n, to znamená jej asymptotickému správaniu, keď sa n blíži k nekonečnu. V dôsledku toho sa na označenie zložitosti bežne používa veľká notácia O.

Výpočtové modely

Pri určovaní zložitosti je dôležitý výber výpočtového modelu, ktorý pozostáva zo špecifikácie podstatných operácií, ktoré sa vykonávajú za jednotku času. Toto sa niekedy označuje ako viacpáskový Turingov stroj, keď nie je špecificky opísaná výpočtová paradigma.

Deterministický model výpočtu je model, v ktorom sú nasledujúce stavy stroja a operácie, ktoré sa majú vykonať, úplne definované predchádzajúcim stavom. Rekurzívne funkcie, lambda počet a Turingove stroje boli prvými deterministickými modelmi. Stroje s náhodným prístupom (tiež známe ako RAM-stroje) sú populárnou paradigmou na simuláciu počítačov v reálnom svete.

Keď nie je definovaný výpočtový model, zvyčajne sa predpokladá viacpáskový Turingov stroj. Na multipáskových Turingových strojoch je časová zložitosť rovnaká ako na strojoch RAM pre väčšinu algoritmov, aj keď na dosiahnutie tejto ekvivalencie môže byť potrebná značná pozornosť pri ukladaní údajov v pamäti.

V niektorých krokoch výpočtu v nedeterministickom výpočtovom modeli, ako sú nedeterministické Turingove stroje, možno urobiť rôzne voľby. V teórii zložitosti sa všetky možné možnosti zvažujú súčasne a nedeterministická časová zložitosť je množstvo času potrebného na to, aby sa vždy urobili najlepšie rozhodnutia. Inými slovami, výpočet sa vykonáva súčasne na toľkých (identických) procesoroch, koľko je potrebných, a nedeterministický čas výpočtu je čas, ktorý prvý procesor potrebuje na dokončenie výpočtu. Tento paralelizmus možno použiť v kvantových výpočtoch pomocou superponovaných zapletených stavov pri spúšťaní špecializovaných kvantových algoritmov, ako je napríklad Shorova faktorizácia malých celých čísel.

Aj keď takýto výpočtový model nie je v súčasnosti uskutočniteľný, má teoretický význam, najmä vo vzťahu k problému P = NP, ktorý sa pýta, či triedy zložitosti vytvorené použitím „polynomického času“ a „nedeterministického polynómového času“ sú najmenej vyššie. hranice sú rovnaké. Na deterministickom počítači si simulácia NP-algoritmu vyžaduje „exponenciálny čas“. Ak je možné úlohu vyriešiť v polynomiálnom čase na nedeterministickom systéme, patrí do triedy obtiažnosti NP. Ak je problém v NP a nie je jednoduchší ako ktorýkoľvek iný problém NP, hovorí sa, že je NP-úplný. Problém batohu, problém obchodného cestujúceho a booleovský problém uspokojiteľnosti sú všetky NP-úplné kombinatorické problémy. Najznámejší algoritmus má exponenciálnu zložitosť pre všetky tieto problémy. Ak by sa niektorý z týchto problémov dal vyriešiť v polynomiálnom čase na deterministickom stroji, potom by sa všetky NP problémy dali vyriešiť aj v polynomiálnom čase a bolo by stanovené P = NP. Od roku 2017 sa všeobecne predpokladá, že P NP, čo znamená, že najhoršie situácie problémov NP je zásadne ťažké vyriešiť, tj trvá oveľa dlhšie ako akékoľvek možné časové rozpätie (desaťročia) vzhľadom na zaujímavú dĺžku vstupu.

Paralelné a distribuované výpočty

Paralelné a distribuované výpočty zahŕňajú rozdelenie spracovania medzi viacero procesorov, ktoré všetky pracujú súčasne. Základným rozdielom medzi rôznymi modelmi je spôsob odosielania údajov medzi procesormi. Prenos údajov medzi procesormi je typicky veľmi rýchly pri paralelných výpočtoch, zatiaľ čo prenos údajov medzi procesormi pri distribuovaných výpočtoch prebieha cez sieť a je teda podstatne pomalší.

Výpočet na N procesoroch trvá aspoň podiel N času, ktorý zaberie jeden procesor. V skutočnosti, pretože niektoré čiastkové úlohy nemožno paralelizovať a niektoré procesory môžu musieť čakať na výsledok od iného procesora, táto teoreticky ideálna hranica sa nikdy nedosiahne.

Kľúčovým problémom zložitosti je teda vyvinúť algoritmy tak, aby súčin výpočtového času počtom procesorov bol čo najbližšie k času potrebnému na vykonanie rovnakého výpočtu na jednom procesore.

Kvantový výpočet

Kvantový počítač je počítač s výpočtovým modelom založeným na kvantovej mechanike. Churchova-Turingova téza platí pre kvantové počítače, z čoho vyplýva, že akýkoľvek problém, ktorý kvantový počítač dokáže vyriešiť, môže vyriešiť aj Turingov stroj. Niektoré úlohy by sa však teoreticky dali vyriešiť skôr pomocou kvantového počítača ako klasického počítača s výrazne nižšou časovou zložitosťou. Zatiaľ je to čisto teoretické, keďže nikto nevie, ako vyvinúť praktický kvantový počítač.

Teória kvantovej zložitosti bola vytvorená s cieľom preskúmať rôzne typy problémov, ktoré môžu kvantové počítače vyriešiť. Používa sa v postkvantovej kryptografii, čo je proces vytvárania kryptografických protokolov, ktoré sú odolné voči útokom kvantových počítačov.

Zložitosť problému (dolné hranice)

Minimálna zložitosť algoritmov, ktoré môžu vyriešiť problém, vrátane neobjavených techník, je zložitosť problému. V dôsledku toho sa zložitosť problému rovná zložitosti akéhokoľvek algoritmu, ktorý ho rieši.

V dôsledku toho akákoľvek zložitosť uvedená vo veľkom zápise O predstavuje zložitosť algoritmu aj sprievodného problému.

Na druhej strane je často ťažké získať netriviálne spodné hranice zložitosti problému a existuje len málo stratégií, ako to dosiahnuť.

Na vyriešenie väčšiny problémov je potrebné prečítať všetky vstupné údaje, čo si vyžaduje čas úmerný veľkosti údajov. Výsledkom je, že takéto problémy majú prinajmenšom lineárnu zložitosť alebo vo veľkej omega notácii zložitosť Ω(n).

Niektoré problémy, ako napríklad problémy v počítačovej algebre a výpočtovej algebraickej geometrii, majú veľmi rozsiahle riešenia. Pretože výstup musí byť zapísaný, zložitosť je obmedzená maximálnou veľkosťou výstupu.

Počet porovnaní požadovaných pre triediaci algoritmus má nelineárnu spodnú hranicu Ω(nlogn). V dôsledku toho sú najlepšie triediace algoritmy najefektívnejšie, pretože ich zložitosť je O(nlogn). Skutočnosť, že existuje n! spôsoby organizácie vecí vedú k tejto spodnej hranici. Pretože každé porovnanie rozdeľuje túto zbierku n! objednávky na dva kusy, počet N porovnaní potrebných na rozlíšenie všetkých objednávok musí byť 2N > n!, čo znamená O(nlogn) podľa Stirlingovho vzorca.

Zmenšenie problému na iný problém je bežnou stratégiou na dosiahnutie znížených obmedzení zložitosti.

Vývoj algoritmu

Hodnotenie zložitosti algoritmu je dôležitým prvkom procesu návrhu, pretože poskytuje užitočné informácie o očakávanom výkone.

Je častým nedorozumením, že v dôsledku Moorovho zákona, ktorý predpovedá exponenciálny rast moderného počítačového výkonu, bude hodnotenie zložitosti algoritmov menej relevantné. Toto je nesprávne, pretože zvýšený výkon umožňuje spracovanie obrovského množstva údajov (veľké údaje). Napríklad pri abecednom triedení zoznamu niekoľkých stoviek záznamov, ako je bibliografia knihy, by mal každý algoritmus fungovať dobre za menej ako sekundu. Na druhej strane, pre milión záznamov (napríklad telefónne čísla veľkého mesta) by základné algoritmy, ktoré vyžadujú porovnanie O(n2), museli vykonať bilión porovnaní, čo by trvalo tri hodiny pri rýchlosti 10 milión porovnaní za sekundu. Na druhej strane rýchle triedenie a zlučovacie triedenie vyžadujú iba porovnania nlogn (ako zložitosť priemerného prípadu pre prvé, ako zložitosť najhoršieho prípadu pre druhú). To vytvára približne 30,000,000 1,000,000 3 porovnaní pre n = 10 XNUMX XNUMX, čo by pri XNUMX miliónoch porovnaní za sekundu trvalo len XNUMX sekundy.

V dôsledku toho môže posúdenie zložitosti umožniť elimináciu mnohých neefektívnych algoritmov pred implementáciou. To sa dá použiť aj na doladenie zložitých algoritmov bez toho, aby ste museli testovať všetky možné varianty. Štúdium zložitosti umožňuje zamerať úsilie na zvýšenie efektívnosti implementácie určením najnákladnejších krokov zložitého algoritmu.