Complexitatea computațională

Complexitatea computațională este un concept în informatică și în teoria algoritmilor , care denotă o funcție a dependenței cantității de muncă efectuată de un algoritm de dimensiunea datelor de intrare. Ramura care studiază complexitatea computațională se numește teoria complexității computaționale . Cantitatea de muncă este de obicei măsurată în termeni de concepte abstracte de timp și spațiu numite resurse de calcul . Timpul este determinat de numărul de pași elementari necesari pentru a rezolva o problemă, în timp ce spațiul este determinat de cantitatea de memorie sau spațiu de stocare . Astfel, în acest domeniu, se încearcă să se răspundă la întrebarea centrală a dezvoltării algoritmului: „cum se va schimba timpul de execuție și cantitatea de memorie ocupată în funcție de dimensiunea intrării?”. Aici, dimensiunea intrării este lungimea descrierii datelor problemei în biți (de exemplu, în problema vânzătorului ambulant , lungimea intrării este aproape proporțională cu numărul de orașe și drumuri dintre ele) și dimensiunea rezultatului este lungimea descrierii soluției problemei (cel mai bun traseu în problema vânzătorului ambulant).

În special, teoria complexității computaționale definește probleme NP-complete pe care o mașină Turing nedeterministă le poate rezolva în timp polinomial , în timp ce nu este cunoscut niciun algoritm polinom pentru o mașină Turing deterministă . De obicei, acestea sunt probleme complexe de optimizare , de exemplu, problema vânzătorului ambulant .

Strâns legate de informatica teoretică sunt domenii precum analiza algoritmilor și teoria computabilității . Legătura dintre informatica teoretică și analiza algoritmică este faptul că formarea lor este dedicată analizei cantității necesare de resurse a anumitor algoritmi pentru rezolvarea problemelor, în timp ce o problemă mai generală este posibilitatea utilizării algoritmilor pentru astfel de probleme. Pentru a fi concret, vom încerca să clasificăm problemele care pot fi rezolvate sau nu cu resurse limitate. O limitare puternică a resurselor disponibile distinge teoria complexității computaționale de teoria computațională, aceasta din urmă răspunde la întrebarea ce probleme, în principiu, pot fi rezolvate algoritmic.

Complexitatea timpului și spațiului

Teoria complexității computaționale a apărut din necesitatea de a compara viteza algoritmilor, de a descrie clar comportamentul acestora (timpul de execuție și cantitatea de memorie necesară) în funcție de dimensiunea intrării.

Numărul de operații elementare petrecute de algoritm pentru a rezolva o anumită instanță a problemei depinde nu numai de dimensiunea datelor de intrare, ci și de datele în sine. De exemplu, numărul de operații ale algoritmului de sortare prin inserție este mult mai mic dacă datele de intrare sunt deja sortate. Pentru a evita astfel de dificultăți, luați în considerare conceptul de complexitate temporală a algoritmului în cel mai rău caz .

Complexitatea temporală a unui algoritm (în cel mai rău caz) este o funcție de dimensiunea datelor de intrare, egală cu numărul maxim de operații elementare efectuate de algoritm pentru a rezolva o instanță de problemă de dimensiunea specificată.

Similar conceptului de complexitate în timp în cel mai rău caz , este definit conceptul de complexitate în timp a unui algoritm în cel mai bun caz . Ei iau în considerare și conceptul de timp mediu de rulare al algoritmului , adică așteptarea matematică a timpului de rulare al algoritmului. Uneori se spune pur și simplu: „ Complexitatea în timp a algoritmului ” sau „ Timpul de rulare a algoritmului ”, referindu-se la complexitatea în timp a algoritmului în cel mai rău, cel mai bun sau mediu caz (în funcție de context).

Prin analogie cu complexitatea timpului, ei determină complexitatea spațială a algoritmului , doar că aici se vorbește nu despre numărul de operații elementare, ci despre cantitatea de memorie utilizată.

Complexitatea asimptotică

În ciuda faptului că funcția de complexitate a timpului a unui algoritm poate fi determinată exact în unele cazuri, în majoritatea cazurilor este lipsită de sens să se caute valoarea exactă a acestuia. Faptul este că, în primul rând, valoarea exactă a complexității timpului depinde de definirea operațiilor elementare (de exemplu, complexitatea poate fi măsurată în numărul de operații aritmetice , operații pe biți sau operații pe o mașină Turing ) și, în al doilea rând, ca mărimea datelor de intrare crește, contribuția factorilor constante și a termenilor de ordin inferior care apar în expresia pentru timpul exact de funcționare devine extrem de nesemnificativă.

Luarea în considerare a datelor de intrare mari și estimarea ordinii de creștere a timpului de rulare a algoritmului conduce la conceptul de complexitate asimptotică a algoritmului. În același timp, un algoritm cu complexitate mai puțin asimptotică este mai eficient pentru toate datele de intrare, cu excepția, eventual, pentru datele de dimensiuni mici. Notația asimptotică este folosită pentru a scrie complexitatea asimptotică a algoritmilor :

Desemnare	Explicație intuitivă	Definiție
$f(n)\în O(g(n))$	$f$ este mărginită de sus de o funcție (până la un factor constant) asimptotic $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ sau $\există (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\in \Omega (g(n))$	$f$ este mărginită de jos de o funcție (până la un factor constant) asimptotic $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\în \Theta (g(n))$	$f$ mărginit de jos și de sus de funcție asimptotic $g$	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|\leq \|C' g(n)\|$
$f(n)\în o(g(n))$	$g$ domină asimptotic $f$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\in \omega (g(n))$	$f$ domină asimptotic $g$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
$f(n)\sim g(n)$	$f$ este echivalent asimptotic $g$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Exemple

„Aspirarea unui covor” durează timp liniar în funcție de zona sa ( ), adică un covor cu suprafața de două ori va dura de două ori mai mult. În consecință, cu o creștere a suprafeței covorului de o sută de mii de ori, volumul de muncă crește strict proporțional de o sută de mii de ori etc. $\Theta (A)$
„Găsiți un nume în agenda telefonică” necesită doar timp, dependent logaritmic de numărul de înregistrări ( ), deoarece prin deschiderea cărții aproximativ la mijloc reducem dimensiunea „problemei rămase” la jumătate (prin sortarea numelor alfabetic). Astfel, într-o carte cu un volum de 1000 de pagini, orice nume se găsește nu mai mult decât la un moment dat (deschideri de carte). La creșterea volumului de pagini la o sută de mii, problema se rezolvă în continuare în vizite. (Vezi căutare binară .) $O(\log _{2}(n))$ $\log _{2}1000\aproximativ 10$ $\log _{2}100000\aproximativ 17$

Note

Deoarece , în estimarea complexității asimptotice, „logaritmul” este adesea scris fără a menționa baza - de exemplu, . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

Trebuie subliniat faptul că rata de creștere a timpului de execuție în cel mai rău caz nu este singurul sau cel mai important criteriu de evaluare a algoritmilor și programelor. Iată câteva considerații care vă permit să priviți criteriul de rulare din alte puncte de vedere:

Dacă programul creat va fi folosit doar de câteva ori, atunci costul de scriere și depanare a programului va domina costul total al programului, adică timpul real de execuție nu va avea un impact semnificativ asupra costului total. În acest caz, ar trebui să fie preferat algoritmul care este cel mai simplu de implementat.

Dacă programul va funcționa numai cu date de intrare „mici”, atunci rata de creștere a timpului de rulare va fi mai puțin importantă decât constanta prezentă în formula timpului de rulare [1] . În același timp, conceptul de „micitate” a datelor de intrare depinde și de timpul exact de execuție al algoritmilor concurenți. Există algoritmi, cum ar fi algoritmul de multiplicare a întregilor , care sunt asimptotic cei mai eficienți, dar care nu sunt niciodată utilizați în practică, chiar și pentru probleme mari, deoarece constantele lor de proporționalitate sunt cu mult superioare celor ale altora, mai simple și mai puțin „eficiente” algoritmi. Un alt exemplu este grămada Fibonacci , în ciuda eficienței lor asimptotice, din punct de vedere practic, complexitatea software-ului de implementare și valorile mari ale constantelor din formulele timpului de rulare le fac mai puțin atractive decât arborii binari obișnuiți [1] .

Dacă rezolvarea unei probleme pentru un grafic cu n noduri cu un algoritm durează timp (număr de pași) de ordinul lui n C , iar cu altul - de ordinul lui n+n!/C, unde C este un număr constant , atunci conform „ideologiei polinomului” primul algoritm este practic eficient , iar al doilea nu este, deși, de exemplu, la C=10 (10 10 ) situația este exact invers [2] .A. A. Zykov

Există cazuri când algoritmii eficienți necesită cantități atât de mari de memorie a mașinii (fără posibilitatea utilizării mediilor de stocare externe) încât acest factor anulează avantajul „eficienței” algoritmului. Astfel, nu numai „complexitatea timpului” este adesea importantă, ci și „complexitatea memoriei” (complexitatea spațială).

În algoritmii numerici, acuratețea și stabilitatea algoritmilor nu sunt mai puțin importante decât eficiența lor în timp.

Clase de dificultate

O clasă de complexitate este un set de probleme de recunoaștere pentru care există algoritmi care sunt similari ca complexitate de calcul. Doi reprezentanți importanți:

Clasa P

Clasa P conține toate acele probleme a căror rezolvare este considerată „rapidă”, adică al căror timp de rezolvare depinde polinom de mărimea intrării. Aceasta include sortarea , căutarea într-o matrice, aflarea conectivității graficelor și multe altele.

Clasa NP

Clasa NP conține probleme pe care o mașină Turing nedeterministă le poate rezolva într-un număr polinom de pași de la dimensiunea intrării. Soluția lor poate fi verificată de o mașină Turing deterministă într-un număr polinomial de pași. Trebuie remarcat faptul că o mașină Turing nedeterministă este doar un model abstract, în timp ce calculatoarele moderne corespund unei mașini Turing deterministă cu memorie limitată. Deoarece o mașină Turing deterministă poate fi considerată un caz special al unei mașini Turing nedeterministe , clasa NP include clasa P, precum și unele probleme pentru care doar algoritmii care depind exponențial de dimensiunea intrării (adică sunt ineficienți pentru mari dimensiuni). intrări) se știe că rezolvă. Clasa NP include multe probleme celebre, cum ar fi problema vânzătorului ambulant , problema de satisfacție pentru formulele booleene , factorizarea etc.

Problema egalității claselor P și NP

Problema egalității acestor două clase este considerată una dintre cele mai dificile probleme deschise din domeniul informaticii teoretice. Institutul de Matematică Clay a inclus această problemă pe lista de probleme ale mileniului , oferind o recompensă de un milion de dolari SUA pentru soluția sa.

Vezi și

Note

↑ 1 2 Cormen, Thomas H.; Leizerson, Carol I.; Rivest, Ronald L.; Stein, Clifford. Algoritmi: Construcție și Analiză, ediția a 2-a = Introducere în algoritmi ediția a doua. - M . : „Williams” , 2005. - ISBN 5-8459-0857-4 .
↑ A. A. Zykov. Fundamentele teoriei grafurilor. - Ed. a 3-a. - M . : Vuzovskaya kniga, 2004. - S. 10. - 664 p. — ISBN 5-9502-0057-8 .

Link -uri

Girsh EA „ Complexitatea computațională și Fundamentele Criptografiei ” . Un curs de prelegeri care descriu elementele de bază ale complexității computaționale și criptografiei.
Yuri Lifshits " Probleme moderne ale informaticii teoretice " . Curs de prelegeri despre algoritmi pentru probleme NP-hard.
A. A. Razborov . Informatică teoretică: viziunea unui matematician // Computerra . - 2001. - Nr. 2 . (link în jos)(link alternativ)
A. A. RAZBOROV Despre complexitatea calculelor // Educația matematică . - MTSNMO , 1999. - Nr. 3 . - S. 127-141 .

Dicționare și enciclopedii	Rusă mare

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE