În informatică, teoria complexității computaționale este o ramură a teoriei de calcul, studiind costul lucrărilor necesare pentru a rezolva probleme de calcul. Costul este de obicei măsurată prin concepte abstracte de timp și spațiu, numite resurse de calcul. Timpul determinat de numărul de pași triviale necesare pentru a rezolva problema, în timp ce spațiul este definit dimensiunea memoriei sau locație pe un mediu de stocare. Astfel, în această încercare de domeniu pentru a răspunde la întrebarea centrală a dezvoltării de algoritmi, „cum să se schimbe timpul de execuție și cantitatea de memorie, în funcție de mărimea de intrare 1) și de ieșire 2)?“.
În special, teoria complexității computaționale determină probleme de tip NP-complete, care sunt non-determinist mașină Turing poate fi rezolvată în timp polinomial, în timp ce o mașină deterministă Turing este un algoritm polinomial este necunoscut.
Numărul de operații elementare, a petrecut un algoritm de rezolvare un caz particular al problemei nu depinde numai de dimensiunea datelor de intrare, dar, de asemenea, din datele în sine. De exemplu, numărul de operații de sortare algoritm introduce în mod semnificativ mai puțin în cazul în care datele de intrare deja sortate. Pentru a evita aceste probleme, luați în considerare conceptul de complexitate timp, în cel mai rău caz.
complexitatea timp (cel mai rău caz) - o funcție de dimensiunea datelor de intrare și de ieșire, care este egal cu numărul maxim de operații elementare, efectuate algoritm pentru rezolvarea problemei instanță dimensiunea specificată. În multe probleme dimensiunea de ieșire nu depășește sau este proporțională cu mărimea de intrare - în acest caz, poate fi considerată ca fiind complexitatea timp a dimensiunii funcției numai a datelor de intrare.
Complexitatea spațială a algoritmului (cel mai rău caz) - este o funcție de mărimea de intrare și ieșire a datelor, egală cu valoarea maximă a memoriei consumate, algoritmul consumat pentru rezolvarea problemei instanța de dimensiunea specificată. În multe probleme dimensiunea de ieșire nu depășește sau este proporțională cu mărimea de intrare - în acest caz, poate fi considerată ca fiind mărimea funcției de complexitate spațială doar a datelor de intrare.
În ciuda faptului că funcția de complexitate timp, în unele cazuri, pot fi definite în mod precis, în cele mai multe cazuri, uita-te pentru o exact valoarea sa este lipsită de sens. Adevărul este că, în primul rând, valoarea actuală a complexității timpului depinde de definirea operațiunilor elementare (de exemplu, complexitatea poate fi măsurată într-o cantitate de operații aritmetice sau operații pe o mașină Turing), și în al doilea rând, prin creșterea datelor de intrare de contribuție mărimea factorilor constante și la comenzi mai mici care apar în expresia pentru ora exactă de funcționare devine neglijabil.
Asimptotic complexitate - având în vedere introducerea și evaluarea ordinii mare de creștere a timpului de algoritm. De obicei algoritm la complexitatea asimptotic este mai eficient pentru toate datele de intrare, cu excepția, eventual, o cantitate mică de date.
următoarele simboluri sunt folosite pentru a scrie complexitatea asimptotică algoritmilor:
Dacă create de program va fi folosit doar de câteva ori, atunci costul programelor de scriere și de depanare va domina în costul total al programului. În acest caz, ar trebui să alegeți un algoritm, cel mai ușor de implementat.
În cazul în care programul va funcționa doar cu datele de intrare „mici“, gradul de creștere în timpul de execuție va avea o valoare mai mică decât în prezent constantă în formula runtime-ul. Cu toate acestea, conceptul de „micimea“ a datelor de intrare depinde exact de algoritmi timp de execuție concurente. Există algoritmi, cum ar fi algoritmul de multiplicare întreg, un asimptotic cel mai eficient, dar care nu este utilizat în practică, chiar și pentru sarcini mari, deoarece constanta lor de proporționalitate este semnificativ superioară față de alte constante similare, mai simple și mai puțin algoritmi „eficace“.
algoritmi de eficace, dar complexe pot fi nedorite în cazul în care programul va fi gata să sprijine persoana care nu este implicat în scrierea acestor programe.
Există mai multe exemple de algoritmi eficiente necesită astfel de cantități mari de memorie de calculator (fără posibilitatea de a folosi suportul de stocare extern mai lent), că acest factor ar anula avantajul de „eficiență“ a algoritmului.
În algoritmi numerici, precizia și stabilitatea algoritmului nu este mai puțin importantă decât timpul lor în mod eficient.
clasa P include toate aceste probleme soluția de care este considerat „rapid“, care este polinomial în mărimea de intrare. Aceasta include sortarea, căutarea într-o varietate, găsirea grafice de conectivitate, și multe altele.
Clasa NP conține probleme care sunt non-determinist mașină Turing poate rezolva în cantitate de timp polinomial. Trebuie remarcat faptul că nederminirovannaya mașină Turing este doar un model abstract, în timp ce computerele moderne îndeplinesc determinist Turing cu memorie limitată. Astfel, clasa NP include clasa P, precum și unele probleme, la care soluțiile sunt cunoscute numai algoritmi dependente exponențial de mărimea de intrare (adică ineficientă pentru intrările mari). Clasa NP includ multe probleme bine cunoscute, cum ar fi o problemă de călătorie agent de vânzări, problema satisfiabilitate booleană, etc Factorizarea.
dacă dimensiunea matrice de intrare este crescut de 2 ori mai mare decât numărul de iterații ale algoritmului tratamentului său va crește de 4 ori, este - dependența pătratică.
Puteți obține această funcție și experimentală - trebuie doar pentru a măsura timpul algoritmului pe diferite volume de date de intrare și de a trage un grafic.
Se poate ca algoritmul este mai consumatoare de a fi mai eficiente în cantități mai mici de date, deoarece coeficienții de calcul sa omis de obicei, și se consideră evaluarea marginală la timp. De exemplu, algoritmul va fi, evident, mult mai eficace în cantități mai mici decât. Prin urmare, s-ar putea fi interesant pentru a măsura performanța reală și de a obține un grafic al experimental.
1) lungimea datelor descrierii problemei în biți
2) lungimea descrierii soluției problemei