Estimarea complexității în timp a algoritmului. Tipuri de funcție de complexitate a algoritmilor

Timp constant

Se spune că un algoritm este un algoritm timp constant(înregistrat ca timp O (1)) dacă valoarea T(n) este limitată la o valoare care nu depinde de dimensiunea intrării. De exemplu, obținerea unui element dintr-o matrice necesită timp constant, deoarece o singură comandă este executată pentru a-l găsi. Totuși, găsirea valorii minime într-o matrice nesortată nu este o operație în timp constant, deoarece trebuie să scanăm fiecare element al matricei. Deci această operație necesită timp liniar, O (n). Dacă numărul de elemente este cunoscut în prealabil și nu se modifică, un astfel de algoritm poate fi denumit algoritm de timp constant.

În ciuda numelui „timp constant”, timpul de rulare nu trebuie să fie independent de dimensiunea sarcinii, dar limita superioară a timpului de rulare nu ar trebui să fie. De exemplu, sarcina „schimb valori Ași b, dacă este necesar ca drept rezultat să obținem A≤b", este considerată o problemă în timp constant, deși timpul de rulare al algoritmului poate depinde de inegalitatea A ≤ b sau nu. Cu toate acestea, există o anumită constantă t, pentru care timpul de executare a sarcinii este întotdeauna nu depășește t.

Mai jos sunt câteva exemple de cod care rulează în timp constant:

Index int = 5; int item = listă; dacă(condiția este adevărată) atuncialtfel efectuează unele operații cu timp de rulare constant pentru i = 1 la 100 pentru j = 1 la 200 efectuează unele operații cu timp de rulare constant

Dacă T(n) este O ( o valoare constantă), aceasta este echivalentă cu T(n) este O (1).

Timp logaritmic

timp logaritmic, dacă T(n) = O (log n) ... Deoarece computerele folosesc sistemul binar, 2 este folosit ca bază a logaritmului (adică log 2 n). Cu toate acestea, cu înlocuirea bazei jurnalul de logaritmi a nși jurnal b n diferă doar printr-un factor constant, care este eliminat în notația O-mare. Deci O (log n) este notația standard pentru algoritmii de timp logaritmici, indiferent de baza logaritmului.

Algoritmii de timp logaritmici se găsesc în mod obișnuit în operațiunile arborelui binar sau când se utilizează căutarea binară.

Algoritmii O (log n) sunt considerați foarte eficienți, deoarece timpul de execuție per element scade odată cu creșterea numărului de elemente.

Un exemplu foarte simplu de un astfel de algoritm este împărțirea unui șir în jumătate, cealaltă jumătate este din nou înjumătățită și așa mai departe. Aceasta durează O (log n) timp (unde n este lungimea șirului, presupunem aici că console.logși str.subşir ia timp constant). Aceasta înseamnă că pentru a crește numărul de imprimări, lungimea liniei trebuie dublată.

// Funcție pentru tipărirea recursive a jumătății drepte a liniei var dreapta = function (str) (var length = str. lungime; // funcția de ajutor var ajutor = functie (index) ( // Recurs: tipăriți jumătatea dreaptă dacă (index< length ) { // Imprimă caractere de la index până la sfârșitul rândului consolă. log (str. subșir (index, lungime)); // apel recursiv: apelați funcția de ajutor cu partea dreaptă ajutor (Math.ceil ((lungime + index) / 2)); )) ajutor (0); )

Timp polilogaritmic

Se spune că algoritmul rulează timp polilogaritmic, dacă T(n) = O ((log n) k), pentru unii k... De exemplu, problema ordinului înmulțirii matricei poate fi rezolvată în timp polilogaritmic prin mașină PAM paralelă .

Timp subliniar

Se spune că algoritmul rulează timp subliniar, dacă T(n) = o ( n). În special, aceasta include algoritmii de complexitate temporală enumerați mai sus, precum și alții, de exemplu, căutarea Grover cu complexitatea O ( n ½).

Algoritmi tipici care, deși sunt precisi, încă rulează în timp subliniar, utilizează paralelizarea proceselor (la fel ca algoritmul NC 1 pentru calcularea determinantului unei matrice), calcule neclasice (ca în căutarea lui Grover) sau au o ipoteză garantată despre structura intrării (ca operând într-un timp logaritmic, algoritmi de căutare binari și mulți algoritmi de procesare arborescentă). Cu toate acestea, constructele formale, cum ar fi setul tuturor șirurilor care au un 1 bit în poziția determinată de primii log (n) biți ai șirului, pot depinde de fiecare bit al intrării, dar rămân totuși subliniare în timp.

Termen algoritm de rulare subliniar folosit de obicei pentru algoritmi care, spre deosebire de exemplele de mai sus, funcționează pe modele convenționale de mașini secvențiale și nu necesită cunoștințe a priori ale structurii de intrare. Cu toate acestea, pentru ei, utilizarea metodelor probabilistice este permisă și, cu atât mai mult, algoritmii trebuie să fie probabilistici pentru majoritatea problemelor banale.

Deoarece un astfel de algoritm trebuie să răspundă fără a citi complet datele de intrare, depinde foarte mult de metodele de acces permise în fluxul de intrare. De obicei, pentru un flux de șiruri b 1 ,...,b k, se presupune că algoritmul poate solicita valoarea b i pentru oricine i.

Algoritmii de timp subliniari, de regulă, sunt probabilistici și oferă doar o soluție aproximativă. Algoritmii subliniari de rulare apar în mod natural atunci când investigăm verificări de proprietate.

Timp liniar

timp liniar, sau O ( n) dacă complexitatea sa este O ( n). În mod informal, aceasta înseamnă că pentru o dimensiune de intrare suficient de mare, timpul de rulare crește liniar cu dimensiunea de intrare. De exemplu, o procedură care însumează toate elementele unei liste durează timp proporțional cu lungimea listei. Această descriere nu este complet exactă, deoarece timpul de funcționare poate diferi semnificativ de proporționalitatea exactă, în special pentru valori mici. n.

Timpul liniar este adesea privit ca un atribut de dorit al unui algoritm. Au fost făcute multe cercetări pentru a crea algoritmi cu timp de rulare (aproape) liniar sau mai bun. Aceste studii au inclus atât abordări software, cât și hardware. În cazul execuției hardware, unii algoritmi care din punct de vedere matematic nu pot atinge niciodată timp de execuție liniar în modelele de calcul standard pot rula în timp liniar. Există unele tehnologii hardware care folosesc concurența pentru a atinge acest obiectiv. Un exemplu este memoria asociativă. Acest concept de timp liniar este utilizat în algoritmii de comparare a șirurilor, cum ar fi algoritmul Boyer-Moore și algoritmul Ukkonen.

Timp cvasiliniar

Se spune că un algoritm rulează în timp cvasiliniar dacă T(n) = O ( n Buturuga k n) pentru unele constante k... Timpul liniar-logaritmic este un caz special cu k= 1. Când se utilizează notația O slabă, acești algoritmi sunt Õ ( n). Algoritmii de timp cvasiliniari sunt, de asemenea, o ( n 1 + ε) pentru orice ε> 0 și funcționează mai repede decât orice polinom în n

Algoritmii care rulează în timp cvasiliniar, pe lângă algoritmii liniar-logaritmici menționați mai sus, includ:

• Sortare la locul fuzionarii, O ( n Buturuga 2 n)
• Sortare rapidă, O ( n Buturuga n), în varianta probabilistică are un timp de execuție liniar-logaritmic în cel mai rău caz. Versiunea improbabilă are un timp de rulare liniar-log doar pentru a măsura dificultatea în medie.
• Heapsort, O ( n Buturuga n), sortare îmbinare, sortare introductivă, sortare în arbore binar, sortare uniformă, sortare solitaire, etc. în cel mai rău caz
• Transformate Fourier rapide, O ( n Buturuga n)
• Calculul matricelor Monge, O ( n Buturuga n)

Timp logaritmic liniar

Linear-logaritmic este un caz special de timp cvasiliniar cu exponent k= 1 pe termenul logaritmic.

Funcția logaritmică liniară este o funcție a formei n Buturuga n(adică produsul liniarși termeni logaritmici). Se spune că algoritmul funcționează pentru timp liniar-logaritmic, dacă T(n) = O ( n Buturuga n) ... Astfel, elementul liniar-logaritmic crește mai repede decât termenul liniar, dar mai lent decât orice polinom din n cu un grad strict mai mare de 1.

În multe cazuri, timpul de rulare n Buturuga n este pur și simplu rezultatul operației Θ (log n) n o singura data. De exemplu, sortarea cu un arbore binar creează un arbore binar prin inserarea fiecărui element într-o matrice de dimensiune n unul câte unul. De când operația de inserare în arbore de căutare binar echilibrat ia O (log n), timpul total de execuție al algoritmului va fi liniar-logaritmic.

Sortează prin comparație necesită cel puțin numărul de log liniar al comparațiilor din cel mai rău caz, deoarece log ( n!) = Θ( n Buturuga n) prin formula Stirling. Același timp de execuție apare adesea din ecuația de recurență T(n) = 2 T(n/ 2) + O ( n).

Timp pătrat

Câteva exemple de algoritmi de timp polinomial:

Timp polinom strict și slab

În unele contexte, în special în optimizare, algoritmii se disting cu timp polinom strictși timp slab polinomial... Aceste două concepte se aplică numai intrărilor care constă din numere întregi.

Timpul strict polinomial este definit în modelul de calcul aritmetic. În acest model, operațiile aritmetice de bază (adunare, scădere, înmulțire, împărțire și comparare) sunt luate ca unități de execuție, indiferent de lungimea operanzilor. Algoritmul funcționează în timp strict polinomial dacă

1. numărul de operații în modelul de calcul aritmetic este limitat de un polinom în numărul de numere întregi din fluxul de intrare și
2. memoria folosită de algoritm este mărginită de un polinom în dimensiunea intrării.

Orice algoritm cu aceste două proprietăți poate fi redus la un algoritm de timp polinomial prin înlocuirea operațiilor aritmetice cu algoritmii corespunzători pentru efectuarea operațiilor aritmetice pe o mașină Turing. Dacă a doua dintre cerințele de mai sus nu este îndeplinită, acest lucru nu va mai fi adevărat. Având în vedere un număr întreg (care ocupă memorie proporțională cu n în mașina Turing), acesta poate fi calculat în n operații folosind exponențiarea repetată. Cu toate acestea, memoria obișnuia să reprezinte 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), proporțional cu 2 n (\ displaystyle 2 ^ (n)), și depinde mai degrabă exponențial decât polinom de memoria utilizată pentru intrare. Prin urmare, este imposibil să se efectueze aceste calcule în timp polinomial pe o mașină Turing, dar este posibil să se efectueze un număr polinomial de operații aritmetice.

Dimpotrivă, există algoritmi care funcționează în numărul de pași al mașinii Turing, limitat de lungimea polinomului intrării codificate binar, dar nu funcționează în numărul de operații aritmetice, limitat de polinomul în numărul de numere din Intrarea. Algoritmul lui Euclid pentru calcularea celui mai mare divizor comun a două numere întregi este un exemplu. Pentru două numere întregi a (\ displaystyle a)și b (\ displaystyle b) timpul de rulare al algoritmului este limitat O ((log ⁡ a + log ⁡ b) 2) (\ displaystyle O ((\ log \ a + \ log \ b) ^ (2))) pașii mașinii Turing. Acest număr este un polinom al mărimii reprezentării binare a numerelor a (\ displaystyle a)și b (\ displaystyle b), care poate fi reprezentat aproximativ ca log ⁡ a + log ⁡ b (\ displaystyle \ log \ a + \ log \ b)... În același timp, numărul de operații aritmetice nu poate fi limitat de numărul de numere întregi din intrare (care în acest caz este o constantă - există doar două numere în intrare). Având în vedere această remarcă, algoritmul nu funcționează în timp strict polinomial. Timpul real de rulare al algoritmului depinde de valori a (\ displaystyle a)și b (\ displaystyle b), nu doar numărul de numere întregi din intrare.

Dacă un algoritm rulează în timp polinomial, dar nu în timp strict polinom, se spune că rulează în timp polinom slab... Un exemplu binecunoscut de problemă pentru care se cunoaște un algoritm slab polinomial, dar nu este cunoscut un algoritm strict polinom, este programarea liniară. Timpul slab polinom nu trebuie confundat cu timpul pseudo polinom.

Clase de dificultate

Conceptul de timp polinomial conduce la mai multe clase de complexitate în teoria complexității computaționale. Unele clase importante definite folosind timpul polinomial sunt prezentate mai jos.

• : Clasa de complexitate a problemelor de rezolvare care pot fi rezolvate într-o mașină Turing deterministă în timp polinomial.
• : Clasa de complexitate a problemelor de rezolvare care pot fi rezolvate într-o mașină Turing nedeterministă în timp polinomial.
• ZPP: Clasa de complexitate a problemelor de rezolvare care pot fi rezolvate cu eroare zero într-o mașină Turing probabilistică în timp polinomial.
• : Clasa de complexitate a problemelor de rezolvare care pot fi rezolvate cu erori unilaterale într-o mașină Turing probabilistică în timp polinomial.
• BPP mașină de Turing probabilistică în timp polinomial.
• BQP: Clasa de complexitate a problemelor de solubilitate care pot fi rezolvate cu erori cu două fețe într-o mașină cuantică Turing în timp polinomial.

P este cea mai mică clasă de complexitate a timpului pe o mașină deterministă, adică durabilîn ceea ce priveşte schimbarea modelului maşinii. (De exemplu, trecerea de la o mașină Turing cu o singură bandă la o mașină Turing cu mai multe benzi poate duce la o accelerare pătratică, dar orice algoritm care rulează în timp polinomial pe un model va rula în timp polinom pe altul.)

Timpul super polinomial

Se spune că algoritmul funcționează pentru timp superpolinom, dacă T(n) nu este mărginită mai sus de un polinom. Acest timp este egal cu ω ( n c) pentru toate constantele c, Unde n este un parametru de intrare, de obicei numărul de biți de intrare.

De exemplu, un algoritm care implementează 2 n pași pentru a introduce dimensiunea n necesită timp superpolinom (mai precis, timp exponențial).

Este clar că un algoritm care utilizează resurse exponențiale este superpolinom, dar unii algoritmi sunt foarte slab superpolinom. De exemplu, Test de simplitate Adleman-Pomeranza-Roumeli * functioneaza pentru vremea respectiva n O (jurnal de jurnal n) pe n-bit de intrare. Crește mai repede decât orice polinom pentru un suficient de mare n, dar dimensiunea intrării trebuie să devină foarte mare, astfel încât să nu fie dominată de un polinom de grad mic.

Un algoritm care necesită timp superpolinom este în afara clasei de complexitate. teza lui Cobham susține că acești algoritmi sunt nepractici și, în multe cazuri, sunt. Deoarece problema egalității claselor P și NP nu a fost rezolvată, nu se cunosc în prezent algoritmi de rezolvare a problemelor NP-complete în timp polinomial.

Timp cvasi-polinom

Algoritmi timp cvasi-polinom sunt algoritmi care rulează mai lent decât timpul polinomial, dar nu la fel de lent ca algoritmii de timp exponențial. Timpul de rulare în cel mai rău caz pentru algoritmul cvasi-polinom este c... Un algoritm clasic binecunoscut pentru factorizarea unui număr întreg în factori, nu este cvasi-polinom, deoarece timpul de rulare nu poate fi reprezentat ca 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c)))) pentru unele fixe c... Dacă constanta „c” din definiția algoritmului de timp cvasi-polinomial este 1, obținem algoritmul de timp polinomial, iar dacă este mai mică de 1, obținem algoritmul de timp subliniar.

Algoritmii de timp cvasi-polinomi apar de obicei atunci când reduc o problemă NP-hard la o altă problemă. De exemplu, puteți lua o problemă NP-hard, să spunem 3SAT și să o reduceți la o altă problemă B, dar dimensiunea problemei devine 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... În acest caz, reducerea nu dovedește că problema B este NP-hard; o astfel de reducere arată doar că nu există un algoritm polinom pentru B, cu excepția cazului în care există un algoritm cvasi-polinom pentru 3SAT (și apoi pentru toate -problemele). În mod similar, există unele probleme pentru care se cunosc algoritmi cu timp cvasi-polinomial, dar pentru care algoritmi cu timp polinomial sunt necunoscuți. Astfel de probleme apar în algoritmii de aproximare. Un exemplu celebru este problema direcționată Steiner, pentru care există un algoritm cvasi-polinom de aproximare cu un coeficient de aproximare O (log 3 ⁡ n) (\ displaystyle O (\ log ^ (3) n))(unde n este numărul de vârfuri), dar existența unui algoritm de timp polinomial este o problemă deschisă.

Clasa de dificultate QP constă din toate problemele cu algoritmi de timp cvasi-polinomi. Poate fi definit în termeni de DTIME după cum urmează

QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\ displaystyle (\ mbox (QP)) = \ bigcup _ (c \ in \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\ log n) ^ (c))))

Relația cu problemele NP-complete

În teoria complexității, problema nerezolvată a egalității dintre clasele P și NP întreabă dacă toate problemele din clasa NP au algoritmi de rezolvare în timp polinomial. Toți algoritmii cunoscuți pentru probleme NP-complete, cum ar fi 3SAT, au timp exponențial. Mai mult, există o ipoteză că pentru multe probleme naturale NP-complete nu există algoritmi cu timp de execuție subexponențial. Aici „timp subexponențial” este luat în sensul celei de-a doua definiții de mai jos. (Pe de altă parte, multe probleme de teoria grafurilor reprezentate în mod natural de matrici de adiacență sunt rezolvabile în timp subexponențial pur și simplu pentru că dimensiunea intrării este egală cu pătratul numărului de vârfuri.) Această ipoteză (pentru problema k-SAT) este cunoscut ca ipoteza timpului exponenţial... Deoarece se presupune că problemele NP-complete nu au algoritmi de timp cvasi-polinomi, unele rezultate de neaproximabilitate în domeniul algoritmilor de aproximare presupun că problemele NP-complete nu au algoritmi de timp cvasi-polinomi. De exemplu, a se vedea rezultatele binecunoscute privind neaproximabilitatea problemei de acoperire a mulțimii.

Timp subexponenţial

Termen subexponenţială timp este folosit pentru a exprima faptul că timpul de execuție al unui algoritm poate crește mai repede decât orice polinom, dar rămâne semnificativ mai mic decât exponențial. În acest sens, problemele cu algoritmi de timp subexponențial sunt mai maleabile decât algoritmii cu timp doar exponențial. Definiția precisă a „sub-exponențialului” nu este încă general acceptată și oferim mai jos două dintre cele mai comune definiții.

Prima definiție

Se spune că o problemă este rezolvată în timp subexponențial dacă este rezolvată de un algoritm al cărui logaritm al timpului de rulare crește mai puțin decât orice polinom dat. Mai exact, problema are timp subexponenţial dacă pentru orice ε> 0 există un algoritm care rezolvă problema în timp O (2 n ε). Setul tuturor acestor probleme alcătuiește clasa de complexitate SUBEXP, care în termeni de DTIME poate fi exprimat ca.

SUBEXP = ⋂ ε> 0 DTIME (2 n ε) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ stânga (2 ^ (n ^ (\ varepsilon) )) \ dreapta))

Rețineți că aici ε nu face parte din datele de intrare și pentru fiecare ε poate exista propriul algoritm pentru rezolvarea problemei.

A doua definiție

Unii autori definesc timpul subexponențial ca fiind timpul de rulare 2 o ( n). Această definiție permite un timp de rulare mai lung decât prima definiție. Un exemplu de astfel de algoritm de timp subexponențial este bine-cunoscutul algoritm clasic pentru factorizarea numerelor întregi în factori, metoda de sită a câmpului numeric general, care rulează în aproximativ 2 O ~ (n 1/3) (\ displaystyle 2 ^ ((\ tilde (O)) (n ^ (1/3)))), unde este lungimea intrării n... Un alt exemplu este binecunoscutul algoritm pentru probleme de izomorfism grafic al cărui timp de funcţionare este 2 O ((n log ⁡ n)) (\ displaystyle 2 ^ (O ((\ sqrt (()) n \ log n)))).

Rețineți că face o diferență dacă algoritmul este subexponențial în numărul de vârfuri sau în numărul de muchii. V complexitate parametrizată această diferență este prezentă în mod explicit prin specificarea unei perechi, a unei probleme de solubilitate și a unui parametru k. SUBEPT este clasa tuturor problemelor parametrizate care rulează în timp subexponențial în k iar pentru polinom în n :

SUBEPT = DTIME (2 o (k) ⋅ poli (n)). (\ displaystyle (\ text (SUBEPT)) = (\ text (DTIME)) \ stânga (2 ^ (o (k)) \ cdot (\ text (poli)) (n) \ dreapta).)

Mai precis, SUBEPT este clasa tuturor sarcinilor parametrizate (L, k) (\ displaystyle (L, k)) pentru care există o funcție calculabilă f: N → N (\ displaystyle f: \ mathbb (N) \ la \ mathbb (N)) cu f ∈ o (k) (\ displaystyle f \ in o (k))și un algoritm care rezolvă L pe parcursul 2 f (k) ⋅ poly (n) (\ displaystyle 2 ^ (f (k)) \ cdot (\ text (poly)) (n)).

Capitolul 2. Complexitatea algoritmilor.

2.1 Timpul și complexitatea de calcul a algoritmilor.

Complexitatea temporală a algoritmului (T(N) , Unde N- dimensiunea sarcinii) este timpul de execuție al algoritmului, măsurat în pași (instrucțiuni ale algoritmului care trebuie executate pentru a obține rezultatul). Adică acesta este numărul de operații elementare care alcătuiesc algoritmul de rezolvare a problemei (: =,<>, =, +, -, *, /; și, sau, nu, xor; suna, intoarce).

Există trei tipuri de complexitate temporală, care depind de combinația datelor de intrare atunci când se rezolvă o problemă (echivalență, raritate, ordonare și alte proprietăți ale datelor de intrare).

https://pandia.ru/text/78/183/images/image002_151.gif "width =" 178 height = 60 "height =" 60 ">

Se întâmplă T(N)= C* N2 aplicabil pentru o matrice pătrată.

Operațiile elementare în acest caz sunt o combinație de „+” și „*”.

Dacă matricea originală este cea de identitate, atunci obținem cel mai bun caz.

Dacă în matrice jumătate dintre elemente sunt 0, jumătate sunt 1, atunci obținem Cazul mediu.

Constant CU, care nu poate fi exprimat cu acuratețe, caracterizează influența factorilor externi asupra timpului de execuție a algoritmilor (viteza computerului, viteza de compilare). Prin urmare, utilizarea unităților de timp pentru a evalua complexitatea timpului a algoritmilor nu este în întregime corectă. În acest caz, complexitatea în timp a algoritmului de multiplicare matrice-vector este proporțională cu N2 .

2.2 Oși Ω sunt notații.

Natura comportamentului complexității timpului la creștere N (N® ¥ ) numit complexitatea asimptotică a algoritmului.

Pentru a descrie rata de creștere a complexității asimptotice, folosim Notație O. Când se spune că complexitatea temporală a unui algoritm este de ordinul a N2 :

T(N)= O(N2 )= O(f(N)),

Apoi se presupune că există constante pozitive C, n0 =const (C>0), astfel încât pentru toată lumea N ³ N0 inegalitatea este valabilă

T(N) £ C* f(N)

Aceasta este limita superioară a estimării complexității.

Exemplul 2:

Lasa Т (0) = 1, Т (1) = 4, ..., Т (N)=(N+1) 2, atunci complexitatea temporală a acestui algoritm este de ordinul creșterii T(N)= O(N2 ).

Se poate demonstra că pentru toți N > n0 la n0 = 1, C = 4 inegalitatea (1) este valabilă.

(N+1)2 £ 4* N2

Exemplul 3:

Dacă complexitatea timpului este scrisă ca polinom

T(N)= C1 N2 + C2 N+ C3 ,

atunci un astfel de algoritm are un ordin de complexitate care este un multiplu al gradului elementului maxim al polinomului, deoarece crește cel mai rapid pentru N® ¥ :

T(N)= O(N2 ).

De exemplu:

3 n2 +5 n+1 £ 5 n2

" n ³ 1

Exemplul 4:

Dacă un algoritm are complexitate multiplă 3 n, atunci se poate arăta că ordinea de creștere a vitezei nu poate fi multiplu al O(2 n):

T(N)=3 n¹ O(2 n).

Să fie constante C, n0 , astfel încât să fie valabilă următoarea inegalitate:

3n £ C*2 n, n > n0 .

De aici obținem:

CU³ (3/2)2, n > n0 .

Dar cu n® ¥ nu există o astfel de constantă CU care ar satisface această inegalitate.

Pe lângă limita superioară a complexității, există și o limită inferioară pentru rata de creștere a complexității temporale:

T(N) ³ W(f(N))

Inegalitatea (2) implică faptul că există o constantă CU pentru care la N® ¥ complexitatea timpului

T(N) ³ C* f(N).

Ținând cont de complexitatea determinării exacte a lui T (N) (complexitatea timpului asimptotic), în funcție de dimensiunea datelor inițiale, în practică, se folosesc limitele inferioare și superioare ale complexității temporale a algoritmului:

T(N) = q (f(N))

În funcţie de valoarea constantei CU rata de creștere a complexității algoritmului poate varia semnificativ.

Exemplul 5:

Fie ca complexitatea timpului să fie scrisă prin formula

T (N) = 3n2 –100n + 6 = O (n2)

3n2> 3n2 –100n + 6, n³ 1, C = 3.

Dacă C1» 0 (C1 = 0,00001), apoi inegalitatea

10-5 n2 > 3 n2 –100 n+6, n³ 1

neexecutat.

Dar se poate demonstra că ordinea de creștere a complexității

3n2 –100n + 6¹ PE).

C*N< 3N2, N>C.

3n2 –100n + 6 = (n2)

C=2.29, n ³ n0.

2.99* n2 < 3 n2 –100 n+6

Se poate arăta că limita inferioară

3 n2 –100 n+6 ¹ W(n3 ) la C = 1.

Inegalitate 3 n2 –100 n+6 ³ n3 neexecutat.

3 n2 –100 n+6= W(n)

C1 = , n> n0 .

https://pandia.ru/text/78/183/images/image007_89.gif "width =" 305 "height =" 247 src = ">

f1 (N)=100 n2

f2 (N)=5 n3

n0 =20 – punct critic.

Un alt motiv pentru a prefera algoritmi cu un ordin mai mic de complexitate este că, cu cât este mai mic ordinul de complexitate, cu atât dimensiunea problemei este mai mare. N se poate rezolva practic.

0 "style =" margin-left: 5,4pt; border-collapse: collapse; border: none ">

n!

Exemplul 6:

Trebuie avut în vedere că o ordine mai mare de creștere a complexității algoritmilor, de regulă, are o constantă mai mică. C1în comparație cu ordinul mic de creștere a complexității, caracterizat prin constantă C2.

În acest caz, un algoritm cu o complexitate în creștere rapidă poate fi de preferat pentru rezolvarea problemelor cu dimensiuni mici ale datelor ( n® 0 ).

Să fie dați cinci algoritmi pentru rezolvarea aceleiași probleme, care au dificultăți:

A1: 100 N

A2: 100 N* logN

A3: 10 N2

A4: N3

A5: 2 N

Apoi, pentru probleme cu N=2 ¸ 9 mai rapid va fi A5 ( f(N) ~ 4 ¸ 512 ). Alți algoritmi, atunci când sunt înlocuiți, vor da rate semnificativ mai mici.

La N=10 ¸ 58 A3 este de preferat.

La N=59 ¸ 1024 cel mai eficient va fi A2.

La N>1024 A1 este de preferat.

Pentru programele care constau din mai mulți algoritmi care execută secvențial sau concomitent, complexitatea este estimată prin regula sumeiși regula lucrărilor.

Regula sumei : Fie ca programul să fie format din doi algoritmi executați secvențial Р1 și Р2, pentru care dificultățile sunt determinate O(f(n)) și O(g(n)) respectiv. Apoi, complexitatea de timp a întregului program va fi determinată ca suma complexității de timp a fiecărui algoritm:

T(n) = T1 (n)+ T2 (n)

În general, obținem:

T (n)Þ O (max f (n), g (n))

Regula de lucru: Fie complexitatea temporală a unui program constând din doi algoritmi de execuție paralel cu ordinea complexității O(f(n)) și O(g(n)) în consecință, este definit ca produsul complexității în timp a fiecărui algoritm:

T(n) = T1 (n)* T2 (n)

În general:

T(n) Þ O(f(n)* g(n))

Logaritmi.

2.3. Recursiune.

Complexitatea algoritmilor recursivi nu este ușor de estimat din cauza imbricației structurilor algoritmice

f(n) Þ f(n* f(n-1))

De exemplu, pentru a evalua recursiv algoritmul n! Complexitatea va depinde de complexitatea fiecăruia dintre algoritmii incluși în recursivitate.

În general T(n) ~ O(N).

Alți algoritmi recursivi au, în general, complexitate în timp T(n) ~ O(un) , Unde A= const, ceea ce are ca rezultat o complexitate totală mai mare decât complexitatea unui algoritm nerecursiv pentru rezolvarea aceleiași probleme.

2.4 Estimarea complexității algoritmilor și programelor.

2.4.2 Algoritmi de recuperare a dependenței.

În unele cazuri, structura programului este necunoscută și puteți determina timpul funcționării acestuia doar pentru diferite dimensiuni de date de intrare. T(N) (sec.)

Pentru a construi o dependență analitică a complexității programului, a funcției T(N) la un anumit interval [ Nmin, Nmax] ... Apoi, curba găsită a unei funcții analitice este aproximată cu o modificare a parametrilor funcției și o estimare a erorii de aproximare.

De regulă, funcțiile binecunoscute ale complexității timpului sunt utilizate ca atare funcție: O(n!), O(XN), O(NX), O(logN), O(https://pandia.ru/text/78/183/images/image010_72.gif "width =" 307 "height =" 225 src = "> Ca urmare a experimentului pe program, a fost un tabel cu dificultăți de timp obținut:

Ca urmare a căutării aproximării funcției, s-a obținut următoarea dependență analitică:

https://pandia.ru/text/78/183/images/image012_68.gif "width =" 321 "height =" 143 src = ">

Exemplul 2:

Se întâmplă adesea ca timpul de funcționare al aceluiași algoritm, pe lângă dimensiunea problemei, să fie influențat de alți parametri introduși de utilizator.

În acest caz, se construiește o familie de funcții de aproximare și se găsește analitic complexitatea algoritmului.

Intensitatea muncii "href =" / text / categorie / trudoemkostmz / "rel =" bookmark "> intensitatea muncii (timp de muncă).

Natura polinomială sau exponențială a algoritmului este invariabilă în raport cu forma datelor de intrare (binară, zecimală sau alt sistem numeric).

Se spune că un algoritm este polinom dacă timpul său de rulare, adică complexitatea timpului, este mărginit de sus de un polinom de un anumit grad. T(N)= O(Nm) ... Apoi, toate problemele care sunt rezolvate de un astfel de algoritm formează o clasă P de probleme. Se spune că aceste sarcini sunt incluse în R.

Probleme cu complexitatea exponențială a timpului ( T(N)= O(KN) ) nu sunt incluse în R.

cometariu : Se poate demonstra că problemele cu complexitate liniară sunt incluse în P

T(N)= O(N1 )

Să introducem o clasă de NP-probleme care pot fi rezolvate în timp polinomial folosind un algoritm nedeterminist.

Să definim starea algoritmului ca un set al adresei comenzii care se execută în momentul de față și al valorilor tuturor variabilelor, ceea ce este echivalent cu vectorul stării procesului. Prin urmare, majoritatea algoritmilor sunt determiniști, adică în ei, pentru orice stare, există o singură stare următoare admisibilă (inclusiv operațiuni de condiție și selecție). Aceasta înseamnă că un astfel de algoritm poate face un lucru la un moment dat.

V algoritm nedeterminist (NDA) pentru orice stare dată poate exista mai mult de o stare următoare admisibilă, adică, un astfel de algoritm poate executa mai mult de un operator la un moment dat.

NDA nu este un algoritm aleator sau probabilistic. Este un algoritm care poate fi în mai multe stări (aceasta echivalează cu rezolvarea unei probleme în paralel cu multe opțiuni).

Exemplu:

Un algoritm determinist (DA) ar rezolva această problemă secvenţial (enumerarea tuturor opţiunilor, compararea cu criteriul de optimitate K0 până când alege alternativa A0).

NDA poate obține simultan (în paralel) toate alternativele și poate compara cu K0, copiendu-se ca proces separat pentru fiecare alternativă, care este realizat independent.

În acest caz, dacă orice copie descoperă că a fost primit un rezultat incorect sau rezultatul nu a fost obținut, atunci oprește executarea acesteia. Dacă copia găsește o soluție care satisface K0, atunci anunță succesul și toate celelalte copii nu mai funcționează.

Acea. NDA este caracterizat de trei parametri:

1. alegere- funcție multivalorică, ale cărei valori sunt elemente ale mulțimii S;

2. eșec determină terminarea copiei algoritmului;

3. succes face ca toate copiile algoritmului să se termine și să producă un rezultat.

Evident, niciun dispozitiv fizic nu este capabil de un comportament nedeterminist nelimitat, ceea ce înseamnă că NDA este o metodă teoretică.

Problemele care pot fi rezolvate folosind un polinom NDA formează o clasă de probleme NP.

2.5.2 NP- dificilă şiNP- Finalizarea sarcinilor.

Problema în P este NP- dificil dacă există un polinom DA (PDA) al soluției sale, care poate fi folosit pentru a obține o soluție la toate problemele incluse în NP. Adică, o astfel de problemă este NP-hard dacă este cel puțin la fel de grea ca orice problemă din NP.

Se numește o problemă NP-hard aparținând lui NP NP-deplin sarcină. Astfel de probleme nu sunt mai puțin dificile decât orice problemă NP. Mai mult, existența unui PDA pentru o problemă NP-hard sau NP-completă înseamnă că clasele P și NP coincid, adică este posibil să se rezolve toate problemele din clasa a 3-a printr-un algoritm rapid.

Pentru a demonstra că problema este NP-hard, este necesar să arătăm că dacă există un PDA pentru problemă, atunci acesta poate fi folosit pentru a obține o altă soluție PDA la problemele incluse în NP.

Pentru a stabili că o problemă este NP-completă, este necesar să se demonstreze că aparține lui NP.

Ideea de a folosi un algoritm pentru rezolvarea unei probleme pentru a obține un algoritm pentru rezolvarea alteia este unul dintre cei mai importanți algoritmi din teoria algoritmilor.

Definiția 1: Problema Р1 se transformă în problema Р2, dacă orice caz special al problemei Р1 poate fi transformat în timp polinomial într-un caz special al problemei Р2. Atunci soluția Р1 poate fi obținută în timp polinomial din soluția cazului particular al problemei Р2.

https://pandia.ru/text/78/183/images/image024_39.gif "lățime =" 158 înălțime = 56 "înălțime =" 56 ">

De exemplu:

f2 (xi)=(X1 Ú X2 ) Ù ( ) Ù ()

nu este fezabil, deoarece pentru oricare xi f2 (xi)= fals.

Teorema :

Problema de satisfacție este NP-complet.

selecție xi (adevărat, fals)

dacă E (x1, x2,…, xN) atunci succes

altfel eșec

Folosind transformarea problemei P1 în P2, se poate arăta că chiar și un caz limitat al problemei de satisfacție este NP-complet.

K-fezabilitate .

K-satisfiabilitatea înseamnă că orice clauză inclusă în CNF conține cel mult K variabile logice.

Cazul minim este K = 3. Pentru o funcție booleană reprezentată în CNF, în timp polinomial se poate găsi funcția E * (x2) conţinând cel mult trei variabile în fiecare clauză. Atunci E realizabil dacă este realizabil E*.

E* (X1 , X2 ,…, xn) ® E* (xi)

Pentru aceasta se folosește metoda scăderii ordinii clauzelor

(A1 Ú A2 Ú … Ú Ak)=(A1 Ú A2 Ú z) Ù (A3 Ú A4 Ú … Ú Ak Ú )

Aplicând un proces de descompunere iterativă, se poate obține E *.

Găsiți un algoritm de soluție E * mai simplu decât funcțiile E... Dar, în același timp, a dovedit fezabilitatea E *, demonstrăm satisfacabilitatea funcției originale E.

Un caz special: pentru K = 2, funcția E incluse în R.

Exemple de probleme de clasa NP sunt de asemenea probleme grafice :

1) Determinarea maximului de clicuri ale unui graf nedirecționat (problema NP-hard).

2) Problema determinării unui subgraf complet (problema NP-completă).

3) Determinarea acoperirii vârfurilor a cardinalității L pentru un graf nedirecționat (problema NP-completă).

4) Determinarea acoperirilor maxime de vârf ale unui graf nedirecționat (problema NP-hard).

5) Problema determinării existenței unui ciclu hamiltonian pentru un graf (problema NP-completă).

6) Problema vânzătorului ambulant: determinarea mișcării optime de-a lungul graficului cu o singură apariție la fiecare vârf (problema NP-hard).

7) Problemă de programare (problema NP-completă).

2.6 Probleme nerezolvabile din punct de vedere algoritmic

Distribuiți probleme singurși masiv.

De exemplu:

5 + 7 =? Este o singură problemă.

x + y =? Este o problemă masivă.

Algoritmii de obținere a obiectelor paradoxale sau de rezolvare a problemelor, din care ar urma existența obiectelor paradoxale, ar trebui să fie fundamental de nerezolvat.

De exemplu, paradoxurile sunt:

Exemplul 1:

A 10-a problemă a lui Hilbert.

D. Hilbert în 1901, la rezolvarea ecuațiilor diofantine, a propus o problemă care spune:

Găsiți un algoritm care determină o soluție întreagă pentru o ecuație diofantică arbitrară

F(X, y, …)=0

Acesta este un polinom cu exponenți întregi și coeficienți întregi pentru necunoscute

anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0

Pentru ecuația de mai sus, există o soluție specială, care constă în faptul că fiecare rădăcină întreagă xi este un divizor A0 ... în care A0 descompuneți în factori primi și verificați fiecare factor pentru conformitatea cu rădăcina.

În 1970, matematicianul de la Leningrad Yu. Matiyasevich a dovedit matematic imposibilitatea algoritmică de a rezolva ecuația diofantină în formă generală.

Exemplul 2:

Teorema lui Fermat:

Nu există astfel de numere întregi A, b, s, n (n>2) pentru care egalitatea

un + bn = cn

Această teoremă a fost dovedită pentru multe valori nși verificat pentru cazuri speciale, dar o demonstrație generală a teoremei nu a fost încă creată.

Exemplul 3:

Problema lui Goldbach.

H. Holbach în 1742 într-o scrisoare către Euler a formulat problema:

Demonstrați că fiecare număr întreg N³ 6 poate fi reprezentat ca suma a trei numere prime

N= A+ b+ c

Aceasta înseamnă că trebuie să găsiți un algoritm care să permită orice număr întreg N³ 6 găsiți cel puțin o descompunere în trei termeni simpli.

Euler a sugerat o soluție frecventă la această problemă: pentru chiar N această problemă este rezolvabilă și este echivalentă cu descompunerea în doi termeni simpli.

I. Vinogradov în 1937 a dovedit că pentru impar N se pot găsi trei termeni simpli, dar pentru numerele pare nu s-a găsit încă o soluție.

O (1) - Majoritatea operațiunilor dintr-un program sunt efectuate o singură dată sau doar de câteva ori. Algoritmi de complexitate constantă. Orice algoritm care necesită întotdeauna același timp, indiferent de dimensiunea datelor are complexitate constantă.

PE) - Timpul de rulare a programului liniar de obicei atunci când fiecare element al intrării trebuie procesat doar de un număr liniar de ori.

O (N 2), O (N 3), O (N a) - Complexitatea polinomială.

O (N 2) - complexitate pătratică, O (N 3) - complexitate cubică

O (Jurnal (N)) - Când este timpul de rulare a programului logaritmică, programul începe să ruleze mult mai lent odată cu creșterea N. Astfel de timpi de rulare se găsesc de obicei în programele care împart o problemă mare în unele mici și le rezolvă separat.

O (N * log (N)) - Un astfel de timp de rulare are acei algoritmi care împărțiți o mare problemă în mici, iar apoi, după ce le-a rezolvat, combină soluțiile lor.

O (2 N) = Complexitate exponențială. Astfel de algoritmi rezultă cel mai adesea dintr-o abordare numită forță brută.

Programatorul trebuie să fie capabil să analizeze algoritmii și să le determine complexitatea. Complexitatea temporală a algoritmului poate fi calculată pe baza analizei structurilor sale de control.

Algoritmii fără bucle și apeluri recursive au o complexitate constantă. Dacă nu există recursivitate și bucle, toate structurile de control pot fi reduse la structuri de complexitate constantă. În consecință, întregul algoritm este, de asemenea, caracterizat de o complexitate constantă.

Determinarea complexității unui algoritm se reduce în principal la analiza buclelor și apelurilor recursive.

De exemplu, luați în considerare un algoritm pentru procesarea elementelor matricei.
Pentru i: = 1 la N do
Începe
...
Sfârșit;

Complexitatea acestui algoritm este O (N), deoarece corpul buclei este executat de N ori, iar complexitatea corpului buclei este O (1).

Dacă un ciclu este imbricat în altul și ambele cicluri depind de mărimea aceleiași variabile, atunci întreaga construcție este caracterizată de complexitate pătratică.
Pentru i: = 1 la N do
Pentru j: = 1 la N do
Începe
...
Sfârșit;
Complexitatea acestui program este O (N 2).

Există două moduri de a analiza complexitatea unui algoritm: de jos în sus (de la structurile interne de conducere la cele externe) și Descendentă (din exterior și intern).

O (H) = O (1) + O (1) + O (1) = O (1);
O (I) = O (N) * (O (F) + O (J)) = O (N) * O (condiții dominante) = O (N);
O (G) = O (N) * (O (C) + O (I) + O (K)) = O (N) * (O (1) + O (N) + O (1)) = O (N2);
O (E) = O (N) * (O (B) + O (G) + O (L)) = O (N) * O (N 2) = O (N 3);
O (D) = O (A) + O (E) = O (1) + O (N 3) = O (N 3)

Complexitatea acestui algoritm este O (N 3).

De regulă, aproximativ 90% din timpul de rulare al programului necesită repetări și doar 10% este calculat direct. O analiză a complexității programelor arată ce fragmente se încadrează în aceste 90% - acestea sunt ciclurile cu cea mai mare adâncime de cuibărit. Repetițiile pot fi organizate ca bucle imbricate sau recursiuni imbricate.

Aceste informații pot fi folosite de programator pentru a construi un program mai eficient, după cum urmează. În primul rând, puteți încerca să reduceți adâncimea de cuibărire a repetărilor. Atunci ar trebui să luați în considerare reducerea numărului de declarații în buclele cele mai profunde. Dacă 90% din timpul de execuție este în execuția buclelor interioare, atunci o reducere de 30% a acestor secțiuni mici are ca rezultat o reducere de 90% * 30% = 27% a timpului de execuție a întregului program.

Acesta este cel mai simplu exemplu.

O secțiune separată de matematică se ocupă de analiza eficienței algoritmilor și nu este atât de ușor să găsiți cea mai optimă funcție.

Să evaluăm algoritm de căutare binar într-o matrice - dihotomie.

Esența algoritmului: mergem la mijlocul matricei și căutăm corespondența cheii cu valoarea elementului din mijloc. Dacă nu putem găsi o potrivire, ne uităm la dimensiunea relativă a cheii și la valoarea mediană și apoi trecem la jumătatea inferioară sau superioară a listei. În această jumătate, căutăm din nou mijlocul și comparăm din nou cu cheia. Dacă nu funcționează, împărțiți din nou intervalul curent la jumătate.

funcția de căutare (low, high, key: integer): întreg;
var
mijloc, date: întreg;
începe
în timp ce scăzut<=high do
începe
mid: = (jos + mare) div 2;
date: = a;
dacă cheie = date atunci
căutare: = mid
altfel
dacă cheie< data then
ridicat: = mijlocul-1
altfel
scăzut: = mijloc + 1;
Sfârșit;
căutare: = - 1;
Sfârșit;

Prima iterație a buclei se ocupă de întreaga listă. Fiecare iterație ulterioară reduce la jumătate dimensiunea sublistei. Deci, dimensiunile listei pentru algoritm sunt

n n / 2 1 n / 2 2 n / 2 3 n / 2 4 ... n / 2 m

În cele din urmă, va exista un întreg m astfel încât

n/2 m<2 или n<2 m+1

Deoarece m este primul întreg pentru care n / 2 m<2, то должно быть верно

n / 2 m-1> = 2 sau 2 m =

Rezultă că
2 m = Luăm logaritmul fiecărei părți a inegalității și obținem
m = Valoarea m este cel mai mare număr întreg care =<х.
Deci O (log 2 n).

De obicei, problema care se rezolvă are o „dimensiune” naturală (de obicei cantitatea de date pe care o prelucrează) pe care o numim N. În cele din urmă, am dori să obținem o expresie pentru timpul necesar unui program pentru a procesa date de dimensiunea N, ca funcția lui N. De obicei nu ne interesează cazul mediu - timpul de rulare așteptat al programului pe intrări „tipice”, iar cel mai rău caz este timpul de rulare așteptat al programului pe cea mai proastă intrare.

Unii algoritmi sunt bine studiați, în sensul că se cunosc formule matematice exacte pentru cazuri medii și cele mai grave. Astfel de formule sunt dezvoltate prin studierea atentă a programelor pentru a găsi timpul de rulare din punct de vedere al caracteristicilor matematice, iar apoi efectuarea analizei lor matematice.

Există mai multe motive importante pentru acest tip de analiză:
1. Programele scrise într-un limbaj de nivel înalt sunt traduse în coduri de mașină și poate fi dificil de înțeles cât timp va dura executarea unuia sau altul.
2. Multe programe sunt foarte sensibile la datele de intrare, iar performanța lor poate fi foarte dependentă de acestea. Cazul mediu se poate dovedi a fi o ficțiune matematică care nu are legătură cu datele pe care este utilizat programul, iar cel mai rău caz este puțin probabil.

Cele mai bune, medii și cele mai rele cazuri joacă un rol important în sortare.
Calcul de sortare

Analiza O-complexității a devenit larg răspândită în multe aplicații practice. Cu toate acestea, este necesar să înțelegem clar limitările sale.

LA principalele dezavantaje ale abordării includ următoarele:
1) pentru algoritmi complecși, obținerea de estimări O, de regulă, este fie foarte consumatoare de timp, fie aproape imposibilă,
2) este adesea dificil să se determine complexitatea „în medie”,
3) Estimările O sunt prea grosiere pentru a reflecta diferențe mai subtile dintre algoritmi,
4) Analiza O furnizează prea puține informații (sau nu le furnizează deloc) pentru analizarea comportamentului algoritmilor la procesarea unor cantități mici de date.

Determinarea complexității în notația O este departe de a fi banală. În special, eficiența căutării binare este determinată nu de adâncimea de imbricare a buclelor, ci de metoda de alegere a fiecărei încercări succesive.

O altă parte dificilă este definirea „cazului mediu”. Acest lucru este de obicei destul de dificil de realizat din cauza imposibilității de a prezice condițiile de funcționare ale algoritmului. Uneori, un algoritm este folosit ca parte a unui program mare și complex. Uneori, eficiența hardware-ului și/sau a sistemului de operare, sau a unei componente a compilatorului, afectează semnificativ complexitatea algoritmului. Adesea, același algoritm poate fi utilizat în multe aplicații diferite.

Din cauza dificultăților asociate cu analiza complexității de timp a unui algoritm „în medie”, este adesea necesar să ne mulțumim cu estimări pentru cele mai rele și cele mai bune cazuri. Aceste estimări definesc în esență limitele inferioare și superioare pentru dificultatea „medie”. De fapt, dacă nu se poate analiza complexitatea algoritmului „în medie”, rămâne de urmat una dintre legile lui Murphy, conform căreia estimarea obținută pentru cel mai rău caz poate servi ca o bună aproximare a complexității „în medie”. ".

Poate că principalul dezavantaj al funcțiilor O este că sunt prea brute. Dacă algoritmul A realizează o sarcină în 0,001 * N s, în timp ce pentru soluția sa folosind algoritmul B este nevoie de 1000 * N s, atunci B este de un milion de ori mai rapid decât A. Cu toate acestea, A și B au același timp complexitatea este O (N).

Cea mai mare parte a acestei prelegeri a fost dedicată analizei complexității în timp a algoritmilor. Există și alte forme de complexitate care nu trebuie uitate: complexitatea spațială și intelectuală.

Complexitatea spațială, ca cantitate de memorie necesară pentru a executa un program, a fost menționată mai devreme.

Atunci când se analizează complexitatea intelectuală a unui algoritm, se investighează inteligibilitatea algoritmilor și complexitatea dezvoltării lor.

Toate cele trei forme de complexitate sunt de obicei legate. De obicei, atunci când se dezvoltă un algoritm cu o estimare bună a complexității temporale, trebuie să-și sacrifice complexitatea spațială și/sau intelectuală. De exemplu, algoritmul de sortare rapidă este semnificativ mai rapid decât algoritmul de sortare a mostrelor. Plata pentru creșterea vitezei de sortare este exprimată în mai multă memorie necesară pentru sortare. Nevoia de memorie suplimentară pentru sortarea rapidă este asociată cu apeluri recursive multiple.

Quicksort este, de asemenea, mai inteligent complex decât sortarea prin inserare. Dacă ceri sute de oameni să sorteze o secvență de obiecte, atunci cel mai probabil majoritatea dintre ei folosesc un algoritm de sortare a mostrelor. De asemenea, este puțin probabil ca oricare dintre ei să folosească quicksort. Motivele pentru complexitatea intelectuală și spațială mai mare a sortării rapide sunt evidente: algoritmul este recursiv, este destul de dificil de descris, algoritmul este mai lung (adică textul programului) decât algoritmii de sortare mai simpli.

Mai mult de un algoritm poate fi adesea conceput pentru a rezolva aceeași problemă. În acest sens, se pune întrebarea: care dintre algoritmi este „mai bun”?

În cele mai multe cazuri, „mai bine”, aparent, este un algoritm care, folosind aceleași date de intrare, ajunge la rezolvarea problemei, consumând mai puține resurse de calcul (memorie și timp). Acesta este, desigur, un raționament vag. Pentru un raționament mai riguros, introducem mai multe concepte.

Procesul de calcul al unui algoritm este o secvență de pași care au trecut prin execuția algoritmului pentru unele date de intrare.

Este important să înțelegem diferența dintre algoritmul în sine și procesul de calcul generat de acest algoritm. Prima este numai Descriere al doilea.

Complexitatea de timp a algoritmului este timpul \ (T \) necesar pentru a finaliza procesul de calcul al algoritmului pentru unele date de intrare.

Este clar că timpul de execuție depinde de executorul specific. Să presupunem că un calculator electronic și un supercomputer sunt probabil să ruleze același algoritm în momente diferite.

Totuși, timpul \ (T \) poate fi exprimat în termeni de numărul de acțiuni elementare \ (k \) și timpul mediu de execuție al unei acțiuni elementare \ (t \):

Mai mult, \ (k \) este o proprietate cel mai algoritm, și \ (t \) - proprietatea executorului.

Deoarece \ (t \) poate fi considerată o constantă pentru un executant dat, de obicei complexitatea algoritmilor este estimată până la un factor constant. Cu alte cuvinte, complexitatea algoritmului este estimată ordinea de creștere.

Ordinea de creștere O funcție definită pozitivă \ (g (x) \) are o ordine de creștere \ (f (x) \) (scrisă \ (g (x) = \ mathcal (O) (f (x)) \)) dacă \ (\ există c> 0: \: \ forall x> x_0, \, g (x) \ leq c f (x) \).

În funcție de datele de intrare, algoritmul poate rula în momente diferite. De obicei notat in medie complexitate și complexitate în cel mai rău caz... Există și o dependență de cantitate date de intrare \ (n \). De obicei, este evaluată ordinea de creștere a lui \ (n \).

Deci, de exemplu, citirea datelor și stocarea lor în memorie ca o matrice va avea complexitate \ (\ mathcal (O) (n) \), sau complexitate liniară, iar înmulțirea matricei este deja cub\ (\ mathcal (O) (n ^ 3) \).

Pe lângă complexitatea temporală a algoritmului, este de asemenea important spațială complexitatea algoritmului.

Complexitatea spațială a algoritmului este numărul adiţional memorie \ (S \), pe care algoritmul o cere pentru a funcționa. Memoria \ (D \) necesară pentru stocarea datelor de intrare nu este inclusă în \ (S \).

\ (S \) depinde în general și de actuator. De exemplu, dacă două actuatoare acceptă numere întregi de 4 și, respectiv, 8 octeți, atunci complexitatea spațială a algoritmului pentru numerele întregi de 8 octeți va fi de două ori mai mare decât pentru numerele întregi de 4 octeți. Prin urmare, complexitatea spațială este estimată în aceeași ordine de creștere.

Clasele de complexitate ale algoritmului

Anumit clase de dificultate: Acestea sunt categorii care au dificultăți similare.

Se disting următoarele clase principale de dificultate:

DTIME O mașină Turing găsește o soluție la o problemă într-un timp finit (număr de pași). Asimptotica algoritmului este adesea specificată, deci, să zicem, dacă ordinea de creștere a timpului de rulare este \ (T (n) = \ mathcal (O) (f (n)) \), atunci \ (DTIME (f) (n)) \) este indicat. P Mașina Turing găsește o soluție la problema în timp polinomial (număr de pași), i.e. \ (T (n) = \ mathcal (O) (n ^ k) \), unde \ (k \ in \ mathbb (N) \). \ (P = DTIME (n ^ k) \) EXPTIME Mașina Turing găsește o soluție la problema în timp exponențial (număr de pași), adică. \ (T (n) = \ mathcal (O) (2 ^ (n ^ k)) \), unde \ (k \ în \ mathbb (N) \). \ (EXPTIME = DTIME (2 ^ (n ^ k)) \). DSPACE O mașină Turing găsește o soluție la o problemă folosind o cantitate finită de memorie suplimentară (celule). Asimptotica algoritmului este adesea specificată, de exemplu, dacă ordinea de creștere a consumului de memorie este \ (S (n) = \ mathcal (O) (f (n)) \), atunci \ (DSPACE (f (n) )) \) este indicat. L Mașina Turing găsește o soluție la o problemă cu complexitate spațială logaritmică, i.e. \ (S (n) = \ mathcal (O) (\ log n) \)... \ (L = DSPACE (\ log n) \). PSPACE Mașina Turing găsește o soluție la o problemă cu complexitate spațială polinomială, adică \ (S (n) = \ mathcal (O) (n ^ k) \), unde \ (k \ in \ mathbb (N) \ ). \ (PSPACE = DSPACE (n ^ k) \). EXPSPACE O mașină Turing găsește o soluție la o problemă cu complexitate spațială exponențială, de ex. \ (S (n) = \ mathcal (O) (2 ^ (n ^ k)) \), unde \ (k \ în \ mathbb (N) \). \ (EXPSPACE = DSPACE (2 ^ (n ^ k)) \).

În plus, există clase teoretice de complexitate care operează pe concept nedeterminat mașini Turing (TMT). Definițiile lor coincid cu cele de mai sus, cu înlocuirea mașinii Turing cu НМТ, iar numele au prefixul N (de exemplu NP), cu excepția NTIME și NSPACE, unde D este înlocuit cu N.

NMT este o construcție pur teoretică, care, din punct de vedere al principiilor sale de funcționare, este similară cu MT, cu diferența că pentru fiecare dintre stări pot exista mai multe acțiuni posibile. În același timp, NMT alege întotdeauna dintre acțiunile posibile pe cea care duce la o soluție în numărul minim posibil de pași. În mod echivalent, HMT calculează dintre toate se ramifică și selectează ramura care duce la soluție în numărul minim posibil de pași.

Se aude uneori că computerele cuantice sunt implementări ale HMT. Deși acest lucru poate părea a fi adevărat în unele cazuri, în general, un HMT este un sistem mai puternic decât un computer cuantic.

Se știe că \ (P \ subseteq NP \ subseteq PSPACE \ subseteq EXPTIME \ subseteq NEXPTIME \ subseteq EXPSPACE \)

De asemenea, \ (P \ subsetneq EXPTIME \), \ (NP \ subsetneq NEXPTIME \), \ (PSPACE \ subsetneq EXPSPACE \)

De asemenea, se știe că dacă \ (P = NP \), atunci \ (EXPTIME = NEXPTIME \).

Întrebarea egalității dintre P și NP este una dintre principalele întrebări nerezolvate ale informaticii moderne.

Exemple de algoritm

Iată câteva exemple de algoritmi simpli și luați în considerare complexitatea acestora.

Exponentiatie

Acest algoritm a fost descris în India antică înainte de era noastră și este folosit pentru a calcula puterea naturală \ (n \) a unui număr real \ (x \)

1. Scrieți \ (n \) în notație binară
2. Înlocuiți în această înregistrare fiecare din 1 cu o pereche de litere KX și fiecare 0 cu o litera K
3. Tăiați perechea din stânga KX
4. Citind șirul rezultat de la stânga la dreapta, întâlnirea cu litera K, rezultatul la pătrat și întâlnirea cu litera X, înmulțiți rezultatul cu x. La început, rezultatul este x.

În acest algoritm, avem numărul de operații de înmulțire egal cu numărul de cifre în reprezentarea binară \ (n \) în cel mai bun caz și \ (2 (n-1) \) în cel mai rău caz. Oricum complexitatea timpului.

Într-o implementare eficientă a algoritmului, memoria suplimentară nu este practic necesară și nu depinde de datele de intrare, prin urmare complexitatea spațială este \ (S (n) = \ mathcal (O) (1) \).

Trebuie remarcat faptul că există algoritmi mai eficienți. Totuși, în comparație cu implementarea „naivă” care necesită operații de multiplicare \ (\ mathcal (O) (n) \), acest algoritm este relativ eficient.

Înmulțirea numerelor întregi

Acest algoritm de multiplicare este uneori numit rus sau țăran, deși era cunoscut încă din Egiptul Antic.

Primul factor este înmulțit secvențial cu doi, iar al doilea este împărțit în întregime cu 2. Rezultatele sunt înregistrate în două coloane până când al doilea este 1.

Rezultatul înmulțirii este suma numerelor din prima coloană, vizavi de care sunt numerele impare din a doua coloană.

Deoarece împărțirea întregului și înmulțirea cu 2 pot fi efectuate prin deplasare, acest algoritm oferă operații de deplasare \ (2 \ log_2 n \), unde \ (n \) este cea mai mică dintre cele două numere. În cel mai rău caz, se obțin și operații de adunare \ (\ log_2 n - 1 \). Oricum, complexitatea timpului \ (T (n) = \ mathcal (O) (\ log n) \).

Pentru implementarea eficientă a algoritmului, practic nu este necesară memorie suplimentară și nu depinde de datele de intrare, prin urmare \ (S (n) = \ mathcal (O) (1) \)

Din nou, trebuie remarcat faptul că există algoritmi mai eficienți. Totuși, în comparație cu implementarea „naivă” care necesită operații de adunare \ (\ mathcal (O) (n) \), acest algoritm este relativ eficient.

Exemplu

Înmulțiți 23 cu 43.

Să luăm 23 ca al doilea factor.

43	23	ciudat
86	11	ciudat
172	5	ciudat
344	2
688	1	ciudat

Rezultat \ (43 + 86 + 172 + 688 = 989 \)

Avem 10 operațiuni în schimburi și 4 operațiuni de adăugare. Pentru referință, \ (\ log_2 (23) \ aproximativ 4,52 \).

Determinarea complexității unui algoritm

Estimarea funcției de complexitate obținută în analiza asimptotică se numește complexitatea algoritmului.

Trebuie avut în vedere faptul că există mai multe estimări ale complexității algoritmului.

Comportamentul asimptotic al funcției de complexitate este complexitatea operațională. În plus față de acesta, puteți specifica următoarele tipuri de dificultăți.

Temporar complexitatea este o estimare asimptotică a timpului de rulare a algoritmului pe datele de intrare de lungime NS. Evident, în absența paralelizării procedurilor de calcul, timpul de rulare al algoritmului este determinat în mod unic de numărul de operații efectuate. Coeficienții constanți care exprimă durata operațiunilor nu afectează ordinea complexității timpului, astfel încât formulele pentru complexitatea operațională și temporală coincid adesea între ele.

Capacitiv complexitate - o estimare asimptotică a numărului de scalari existenți simultan atunci când se execută algoritmul pe datele de intrare de lungime NS.

Structural complexitatea - o caracteristică a numărului de structuri de control din algoritm și specificul interpunerii acestora.

Cognitiv complexitate - o caracteristică a disponibilității unui algoritm pentru înțelegere de către specialiști în domenii aplicate.

Tipuri și notații de asimptotice

În analiza asimptotică a algoritmilor, se obișnuiește să se folosească notația analizei asimptotice matematice. În acest caz, sunt luate în considerare trei estimări (asimptotice) ale complexității algoritmilor, care sunt notate după cum urmează:

• 1) / (i) = O ^ (n))- o estimare precisă asimptotic a funcției de complexitate / («), sau a complexității operaționale a algoritmului;
• 2) /(n) = 0 (§ (n)) - o limită superioară asimptotic clară pentru funcția de complexitate / ( NS);
• 3) / (n) =? 2 (# (n)) este o estimare mai mică exactă asimptotic pentru funcția de complexitate / ( NS).

În loc de notație C1 ^ (n)) de foarte multe ori mai simplu o (^ (")) cu litera" o "este folosit cu litere italice mici.

Să explicăm semantica formulelor folosind un exemplu: dacă se scrie / (i) = 0 (^ 2 (l)), ATUNCI ASTA înseamnă că funcția g (n) = og2 (n) este o estimare precisă asimptotic pentru funcția de complexitate / (α). De fapt, există o definiție cu două poziții sub forma unei declarații:

Dacă f (n)= @ (log 2 ("")),

mo g (n)= log 2 (l) - estimare asimptotic clară pentru f (n).

Rețineți că factorul constant nu afectează ordinea de complexitate a algoritmului, prin urmare, baza logaritmului este omisă atunci când se indică complexitatea logaritmică și pur și simplu scrie / (n) = @ (log (n)), implicând o bază arbitrară mai mare decât unu pentru logaritm.

Definiții formale ale asimptoticelor

Estimare asimptotic clară a funcției de intensitate a forței de muncă cu, cu 2, n 0 astfel încât pentru n> n 0 funcția f (n), până la factori constanți, nu diferă de funcția g ( l), apoi funcția g (n) se numește estimare asimptotic clară pentru funcția f (x).

• 3 s], s 2 e F, cu x > 0, cu 2> 0:
  • (3 l 0 e K, l 0> 0: (/ l e K, l> l 0: 0 g (n) / (l) = 0 (? (L)),

unde 9 ^, N sunt mulțimile tuturor numerelor reale și, respectiv, naturale.

Limită superioară asimptotic ascuțită pentru funcția de complexitate definit verbal astfel: dacă există numere pozitive cuși n 0 astfel încât pentru n> n 0 funcția f (n) nu crește mai repede decât funcția g (n) până la un factor constant c, apoi funcția g (n) se numește o limită superioară asimptotic ascuțită pentru funcție Ap).

O notație formală mai precisă a definiției este următoarea:

• 3 cu e % s> 0:
  • (3 l 0 e X, l 0> 0: (/ l e K, l> l 0: 0 s? # (L))) 0 (g (n))

Limită inferioară asimptotic ascuțită pentru funcția de complexitate definit verbal astfel: dacă există numere pozitive cuși n 0 astfel încât pentru n> n 0 funcția f (n) nu crește mai lent decât funcția g (n) până la un factor constant cu, atunci funcția? (l) se numește o limită inferioară asimptotic ascuțită pentru funcție

O notație formală mai precisă a definiției este următoarea:

• 3 cu e 9 ^, cu > 0:
  • (3 i 0 e X, i 0> 0: (/ i e K, i > eu sunt 0: 0 s? g (n)

/(Eu sunt) = 0. ^ (N))

Rețineți următoarele:

• 1) inegalitățile indicate în definițiile formale ale asimptoticelor, în cazul general, pot satisface nu una, ci o mulțime de funcții, adesea cu un set infinit de termeni, deci construcțiile Q (g (n)), 0 ^ (n))și 0. ^ (N)) simboliza multe funcții cu care se compară funcția investigată a intensității muncii f (i); în virtutea acesteia, în notația asimptoticelor de forma f (x) = 0 (q (x)), f (f0 = 0 (q max (n)), d) = q 2 (q mn (x) ) în locul semnului „= »Ar fi mai rațional să folosim semnul „e”;
• 2) constructii (d ^ (n)), 0 ^ (n))și ? 1 ^ (n)), folosite ca desemnări pentru unele cantități trebuie citite în consecință, după cum urmează: orice funcție care coincide, nu crește mai repede și nu crește mai încet g (n).

Coincidență și diferență de asimptotice

Să fim atenți la următorul fapt: estimarea f (i) = 0 (? (I)) stabilește pentru f (i) atât limitele superioare, cât și cele inferioare, întrucât definiția ei presupune validitatea relației. c g (n)

Următoarea proprietate a asimptoticelor este destul de evidentă: dacă estimarea φ (n) = © ^ (n)) există, atunci egalitățile / ( NS) = 0 (^ (i)) și f (i) =? 2 (# (i)), adică. estimările superioare și inferioare ale intensității muncii coincid între ele; dacă f (i) = 0 (? max (i)) și φ (n) = C1 ^ mt (n)), și g max (n) фg m Ln (i), atunci nu există nicio funcție g (n), astfel încât / (i) = 0 (? (i)).

Coincidența dintre estimările superioare și inferioare ale intensității muncii este posibilă în următoarele cazuri:

• 1) funcția de complexitate pentru toate valorile lungimii de intrare este o funcție deterministă (nealeatorie), adică numărul de operațiuni efectuate nu depinde de specificul valorilor datelor inițiale; astfel, de exemplu, sunt funcții de dependențe ale numărului de operații de înmulțire și împărțire de numărul de mărimi necunoscute în algoritmul de rezolvare a sistemelor de ecuații algebrice liniare prin metoda de descompunere IZ;
• 2) funcția de intensitate a muncii este o funcție aleatorie, adică. numărul operațiunilor efectuate depinde de specificul datelor inițiale și (sau) ordinea de primire a acestora și puteți specifica funcțiile / t | n (i), / max (i), descriind numărul minim și maxim de operațiunile efectuate de executantul algoritmului pentru o anumită lungime de intrare i, cu toate acestea, ambele aceste funcții au aceleași dominante - de exemplu, sunt polinoame de același ordin.

Există trei reguli importante de reținut atunci când vine vorba de estimarea ordinii complexității operaționale:

• 1) factorii constanți nu contează pentru determinarea ordinii de complexitate, i.e. 0 (к? g (n)) = 0 (g (""));
• 2) ordinea complexității produsului a două funcții este egală cu produsul complexității lor, deoarece egalitatea este adevărată:
• 0 (gl (i) §2(i)) = 0 (? | (i)) 0 (# 2 (i));
• 3) ordinea complexității sumei funcțiilor este egală cu ordinea dominantei termenilor, de exemplu: 0 (i e + n 2 + n) = 0 (i 5).

În regulile de mai sus, simbolul unui singur asimptotic este folosit 0 (»), dar ele sunt valabile pentru toate estimările asimptotice - și pentru 0( ) , și &.{ ).

În setul de funcții elementare, puteți specifica o listă de dominanță funcțională: dacă este o variabilă, a, b - constante numerice, sunt adevărate următoarele afirmații: I „Domin!; Eu! domin un „; a” domină Zj „dacă a> b a n domină NS b dacă A> 1 pentru oricare b e 9? ; n / A domină un / dacă a> b i domină log q (i) dacă A > 1.

Estimarea intensității medii a muncii

În practică, re În unele calcule, estimarea f (n) a așteptării matematice a complexității lui M prezintă un interes semnificativ, deoarece în majoritatea covârșitoare a cazurilor f (n) este o funcție aleatorie. Cu toate acestea, în procesul de studii experimentale ale algoritmilor cu f (i) aleatoriu, apare o problemă suplimentară - alegerea numărului de teste pentru o estimare fiabilă a lui M. Soluția propusă se bazează pe utilizarea distribuției beta pentru a aproxima / (i). Aceasta este o tehnică foarte constructivă și versatilă. Cu toate acestea, în condițiile moderne, când productivitatea computerului este suficient de mare, în multe cazuri este posibil să se utilizeze o metodă mai simplă de alegere a domeniului de testare, bazată pe controlul variabilității curente a valorilor f (n) - valorile sunt evaluate până când variabilitatea estimărilor devine mai mică decât eroarea specificată.

Estimarea complexității operaționale a unui algoritm

Complexitatea algoritmului poate fi determinată pe baza analizei structurilor sale de control. Algoritmii fără bucle și apeluri recursive au o complexitate constantă. Prin urmare, determinarea complexității unui algoritm se reduce în principal la analiza buclelor și apelurilor recursive.

Luați în considerare algoritmul de ștergere La al-lea element din matricea dimensiunilor NS constând din elemente de matrice în mișcare din (k + 1) th la NS-a poziție înapoi la începutul matricei și scăderea numărului de elemente NS pe unitate. Complexitatea ciclului de procesare a matricei este Oh (p-k)întrucât se realizează corpul buclei (operaţia de mutare). PC ori, iar complexitatea corpului buclei este 0 (1), i.e. este constantă.

În exemplul luat în considerare, complexitatea este caracterizată de asimptoticele 0 ("), deoarece numărul de operații efectuate în acest algoritm nu depinde de specificul valorilor datelor. Funcția de complexitate este deterministă și toate tipurile de asimptotice coincid unele cu altele: f (n) = Q (n-k), f (n) = 0 (n-k)și f (n) = Q (n- la). Acest fapt este dovedit de indicarea lui © (). Ar trebui să utilizați 0 (*) și/sau?2 (*) numai dacă aceste asimptotice sunt diferite.

Tipul buclei (for, while, repeat) nu afectează complexitatea. Dacă un ciclu este imbricat în altul și ambele cicluri depind de mărimea aceleiași variabile, atunci întreaga construcție este caracterizată de complexitate pătratică. Cuibărirea repetitivă este un factor major în creșterea dificultății. Ca exemplu, prezentăm complexitățile unor algoritmi de căutare și sortare bine-cunoscuți pentru o serie de dimensiuni NS:

• numărul de operații de comparare în căutarea secvențială: 0 (i);
• numărul de operații de comparare în căutarea binară: 0 (log 2 NS);
• numărul de operații de comparare în metoda schimbului simplu (sortare cu bule): 0 (i 2);
• numărul de operații de permutare în sortarea cu bule: 0 (n 2);

Rețineți că numărul de operații de comparare în metoda schimbului simplu are asimptotice 0 (n 2), iar numărul de operații de permutare are două asimptotice diferite 0 (n 2)și? 2 (0), deoarece numărul de comparații nu depinde de specificul valorilor datelor sortate, în timp ce numărul de permutări este determinat tocmai de acest specific. Permutările pot să nu fie efectuate deloc - dacă matricea de date este ordonată corect inițial sau numărul de permutări poate fi maxim - aproximativ NS 2, - dacă tabloul care este sortat este ordonat inițial în direcția opusă.

Numele funcției g (n)în asimptotice f (n) = @ (t (n)) și f (a) = 0 (g (n)) funcția de complexitate / (") este utilizată pentru a caracteriza algoritmul. Astfel, se vorbește de algoritmi de complexitate polinomială, exponențială, logaritmică etc.