O analiză a comparației costurilor de timp ale algoritmilor efectuate prin rezolvarea unei instanțe a unei probleme, cu cantități mari de date de intrare, se numește asimptotic. Algoritmul cu cea mai mică complexitate asimptotică este cel mai eficient.

În analiza asimptotică, complexitatea algoritmului este o funcție care vă permite să determinați cât de repede crește timpul de rulare al algoritmului odată cu creșterea cantității de date.

Principalele estimări de creștere întâlnite în analiza asimptotică sunt:

• Ο (L-big) este estimarea asimptotică superioară pentru creșterea funcției timp;
• Ω (Omega) este estimarea asimptotică inferioară pentru creșterea funcției timp;
• Θ (Theta) sunt estimările asimptotice inferioare și superioare pentru creșterea funcției timp.

Lăsa n– cantitatea de date. Apoi creșterea funcției algoritm f(n) poate limita funcții g(n) asimptotic:

De exemplu, timpul de curățare a unei camere depinde liniar de suprafața aceleiași încăperi (Θ( S)), adică cu o creștere a suprafeței în n ori, timpul de curățare va crește și în n o singura data. Căutarea unui nume în agenda telefonică va dura timp liniar Ο (n), dacă utilizați algoritmul de căutare liniară sau timpul care depinde logaritmic de numărul de înregistrări ( Ο ( jurnalul 2 ( n))), în cazul căutării binare.

Pentru noi, cel mai mare interes este Ο -funcţie. De asemenea, în capitolele ulterioare, complexitatea algoritmilor va fi dată doar pentru limita superioară asimptotică.

Sub sintagma „complexitatea algoritmului este Ο (f(n))" implică faptul că odată cu creșterea cantității de date de intrare n, timpul de rulare al algoritmului nu va crește mai repede decât o constantă înmulțită cu f(n).

Reguli importante ale analizei asimptotice:

1. O(k*f) = O(f) este un factor constant k(constant) este aruncat, deoarece odată cu creșterea cantității de date, sensul acesteia se pierde, de exemplu:

O(9,1n) = O(n)

1. O(f*g) = O(f)*O(g) – estimarea complexității produsului a două funcții este egală cu produsul complexităților acestora, de exemplu:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2)

1. O(f/g)=O(f)/O(g) – estimarea complexității câtului a două funcții este egală cu câtul complexităților acestora, de exemplu:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

1. O(f+g) este egală cu dominanta O(f) Și O(g) – estimarea complexității sumei de funcții este definită ca estimarea complexității dominantei primului și celui de-al doilea termen, de exemplu:

O(n 5 +n 10) = O(n 10)

Numărarea numărului de operațiuni este plictisitoare și, important, deloc obligatorie. Pe baza regulilor de mai sus, pentru a determina complexitatea unui algoritm, nu este necesar, așa cum am făcut mai înainte, să numărăm toate operațiile, este suficient să știm ce complexitate este cutare sau cutare construcție a algoritmului (operator sau grup de operatori) are. Deci, un algoritm care nu conține cicluri și recursiuni are o complexitate constantă O(1). Complexitatea buclei care se execută n iterații este egală cu O(n). Construcția a două bucle imbricate în funcție de aceeași variabilă n, are complexitate pătratică O(n 2).

Diferite abordări pot fi utilizate pentru a evalua performanța algoritmilor. Cel mai simplu este să rulați pur și simplu fiecare algoritm pe mai multe sarcini și să comparați timpul de execuție. O altă modalitate este de a estima matematic timpul de execuție prin operații de numărare.

Luați în considerare un algoritm pentru calcularea valorii unui polinom de grad n V punct dat X.
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0

Algoritmul 1- pentru fiecare termen, cu excepția unui 0, majorare X la o putere dată prin înmulțire succesivă și apoi înmulțiți cu un factor. Apoi adunați termenii.

calcul i- al-lea termen( i=1..n) cere iînmulțiri. Deci, în total 1 + 2 + 3 + ... + n = n(n+1)/2înmulțiri. În plus, este necesar n+1 plus. Total n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1 operațiuni.

Algoritmul 2- scoate X-s în afara parantezei și rescrieți polinomul în formă
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x))).

De exemplu,
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))

Vom evalua expresia din interior. Cea mai interioară paranteză necesită 1 înmulțire și 1 adunare. Valoarea sa este folosită pentru următoarea paranteză... Și astfel, 1 înmulțire și 1 adunare pentru fiecare paranteză, care.. n-1 lucru. Și după ce ați calculat paranteza cea mai exterioară, înmulțiți cu x și adăugați un 0. Total nînmulțiri + n adaosuri = 2n operațiuni.

Adesea, o astfel de evaluare detaliată nu este necesară. În schimb, este dată doar rata asimptotică de creștere a numărului de operații cu creșterea n.

Funcția f(n) = n 2 /2 + 3n/2 + 1 crește cu aproximativ cât n 2/2(renunțăm la termenul cu creștere relativ lentă 3n/2+1). multiplicator constant 1/2 de asemenea, eliminăm și obținem o estimare asimptotică pentru algoritmul 1, care este notat cu un simbol special O(n2)[citește ca „O mare din pătrat”].

Aceasta este o limită superioară, adică numărul de operații (și, prin urmare, timpul de rulare) nu crește mai repede decât pătratul numărului de elemente. Pentru a vă da o idee despre ce este aceasta, priviți tabelul, care prezintă numere care ilustrează rata de creștere pentru mai multe funcții diferite.

		n*log n
1	0	0	1
16	4	64	256
256	8	2,048	65,536
4,096	12	49,152	16,777,216
65,536	16	1,048,565	4,294,967,296
1,048,576	20	20,969,520	1,099,301,922,576
16,775,616	24	402,614,784	281,421,292,179,456

Dacă presupunem că numerele din tabel corespund microsecundelor, atunci pentru o sarcină cu n=1048576 elemente ale algoritmului cu timpul de rulare O(log n) va dura 20 de microsecunde, algoritmul în timp Pe)- 17 minute, iar algoritmul cu timpul de rulare O(n2)- mai mult de 12 zile... Acum avantajul algoritmului 2 cu o estimare Pe)înainte de algoritmul 1 este destul de evident.

Cea mai bună estimare este O(1)... În acest caz, timpul nu depinde de n, adică în mod constant pentru orice număr de elemente.

Prin urmare, O()- estimare „trunchiată” a timpului de rulare a algoritmului, care este adesea mult mai ușor de obținut decât formula exactă pentru numărul de operații.

Deci, să formulăm două reguli pentru formarea estimării O().

La evaluarea funcției, numărul de operații care crește cel mai rapid este luat ca funcție.
Adică, dacă programul are o singură funcție, de exemplu, înmulțirea, este executată Pe) ori și adaos - O(n2) ori, apoi complexitatea totală a programului - O(n2), deoarece în final cu o creștere n mai rapid (într-un anumit constant de ori) adunările vor fi efectuate atât de des încât vor afecta performanța mult mai mult decât înmulțirile lente, dar rare. Simbol O() spectacole exclusiv asimptotice!

La evaluarea O() , constantele nu sunt luate în considerare.
Lăsați un algoritm să facă 2500n + 1000 de operații, iar celălalt - 2n+1. Ambele sunt evaluate Pe), deoarece timpul lor de execuție crește liniar.

În special, dacă ambii algoritmi, de exemplu, O(n*log n) Cu toate acestea, acest lucru nu înseamnă că sunt la fel de eficiente. Primul poate fi, să zicem, de 1000 de ori mai eficient. O() înseamnă doar că timpul lor crește aproximativ în funcție de n*log n.

O altă consecință a omiterii constantei este algoritmul în timp O(n2) poate rula mult mai repede decât algoritmul Pe) pentru mic n... Datorită faptului că numărul real de operații al primului algoritm poate fi n2 + 10n + 6, iar al doilea - 1000000n+5. Totuși, al doilea algoritm îl va depăși pe primul mai devreme sau mai târziu... n 2 crescand mult mai repede 1000000n.

Baza unui logaritm în cadrul unui simbol O() nu este scris.
Motivul pentru aceasta este destul de simplu. Să avem O(log2n). Dar log 2 n=log 3 n/log 3 2, A log 3 2, ca orice constantă, asimptotica este simbolul DESPRE() nu ia in calcul. Prin urmare, O(log2n) = O(log 3 n).

Putem merge la orice bază într-un mod similar, ceea ce înseamnă că nu are sens să o scriem.

Interpretarea matematică a simbolului O().

Definiție
O(g)- multe funcții f, pentru care există astfel de constante CȘi N, Ce |f(x)|<= C|g(x)| pentru toți x>N.
Înregistrare f = O(g)înseamnă literal că f aparține setului O(g). În acest caz, expresia inversă O(g) = f nu are sens.

În special, se poate spune că f(n) = 50n aparține O(n2). Aici avem de-a face cu o estimare inexactă. Desigur f(n)<= 50n 2 la n>1, dar o afirmație mai puternică ar fi f(n) = O(n), deoarece pentru C=50Și N=1 dreapta f(n)<= Cn, n>N.

Alte tipuri de evaluări.

Odata cu evaluarea Pe) scor folosit Ω(n)[citește ca „Omega mare de la ro”]. Indică o estimare mai mică pentru creșterea funcției. De exemplu, lăsați funcția să descrie numărul de operații ale algoritmului f(n) = Ω(n 2). Aceasta înseamnă că, chiar și în cel mai de succes caz, se va produce nu mai puțin de un ordin de mărime. n 2 actiuni.
...În timpul evaluării f(n) = O(n 3) garantează că în cel mai rău caz acțiunile vor fi de ordine n 3, nu mai mult.

Se folosește și estimarea Θ(n)[„Theta din en”], care este un hibrid O()Și Ω() .
Θ(n2) este atât o estimare asimptotică superioară cât și una inferioară în același timp - ordinul n 2 operațiuni. Nota Θ() există doar atunci când O()Și Ω() potriviți și egali.

Pentru algoritmii de calcul al polinomului considerat mai sus, estimările găsite sunt simultan O(), Ω() Și Θ() .
Dacă adăugăm la primul algoritm de verificare pentru x=0în exponențiere, apoi pe cele mai reușite date inițiale (când x=0) avem ordine n verificări, 0 înmulțiri și 1 adunare, care dă o nouă estimare Ω(n)împreună cu vechiul O(n2).

De regulă, atenția principală este încă acordată limitei superioare O(), deci în ciuda „îmbunătățirii”, algoritmul 2 rămâne de preferat.

Asa de, O()- estimarea asimptotică a algoritmului pe cele mai proaste date de intrare, Ω() - pe cele mai bune date de intrare, Θ() - notaţie prescurtată a acestuia O()Și Ω() .

Pentru analiza teoretică, nu este o funcție specifică care descrie dependența timpului de execuție de numărul de date de intrare, ci ordinea creșterii sale pentru N mare care este fundamentală, ceea ce este o măsurătoare mai potrivită. Problemele cheie sunt, în primul rând, în determinarea posibilității unei soluții computerizate într-un timp finit acceptabil, în principiu, și în al doilea rând, în compararea alternativelor și eliminarea algoritmilor nepotriviți din luare în considerare chiar înainte de a fi depus eforturi pentru a obține o calitate înaltă cu drepturi depline. implementare.

Cu alte cuvinte, rolul decisiv îl joacă estimare asimptotică complexitatea de calcul a algoritmului. Să luăm limita din relația de mai sus pentru algoritmul de sortare cu bule, cu numărul de date de intrare N tinzând spre infinit:

În estimarea marginală, puterile inferioare sunt eliminate deoarece domină puterile superioare. Astfel, timpul de execuție al algoritmului de sortare cu bule are o dependență pătratică de cantitatea de date de intrare.

ÎN vedere generala, timpul de execuție al oricărui algoritm poate fi reprezentat astfel:

Când studiem proprietățile și comparăm algoritmi, putem renunța la factorul constant, deoarece pentru N suficient de mare, factorul determinant este ordinea de creștere a funcției. Acest lucru este ușor de explicat cu un exemplu. Să presupunem că există 2 algoritmi alternativi, primul are un ordin pătratic de creștere, iar al doilea este descris de o funcție liniară. De asemenea, presupunem că implementarea primului algoritm este aproape de optim, iar programul rulează pe un computer modern. În același timp, implementarea celui de-al doilea algoritm este departe de a fi genială și rulează pe un computer învechit. Un asemenea dezechilibru conditii externe poate fi modelat folosind diferența de factori constanți (lit, a, a). Pentru N mic, de exemplu, cu 5 date, timpul de execuție al primului algoritm va fi mai mic decât al celui de-al doilea:

Cu toate acestea, pe măsură ce numărul de intrări crește, al doilea algoritm, care are o complexitate de calcul mai bună, îl va depăși pe primul, în ciuda tuturor factorilor nefericiți:

Oricare ar fi valorile factorilor constanți, atunci când complexitatea de calcul a unui algoritm este mai bună decât complexitatea de calcul a altuia, există întotdeauna o cantitate critică de date de intrare, începând de la care este ordinea de creștere a timpului de execuție a algoritmului. care devine factorul dominant.

Pentru raționamentul analitic despre estimările asimptotice ale complexității computaționale a algoritmilor, în literatură sunt utilizate simultan mai multe notații matematice - O-estimate, -estimate și -estimate.

Estimarea este o comparație cu un set infinit de funcții cu același ordin de creștere, care diferă printr-un factor constant. O funcție aparține mulțimii dacă există constante u care, pentru N suficient de mare, limitează funcția de sus și de jos, care descrie viteza algoritmului analizat. Astfel, este valabilă următoarea relație:

O-estimatorul este un subset al -estimatorului care restricționează funcția algoritmului analizat doar de sus. Cu alte cuvinte, estimatorul O descrie asimptotic cel mai rău caz pentru algoritmul analizat. Această estimare este utilizată cel mai des în analiză. Mult mai puțin folosită este o estimare care limitează funcția algoritmului analizat de jos (cel mai bun caz).

Printre estimările asimptotice tipice ale complexității de calcul a algoritmilor, următoarele funcții sunt comune:

liniar O(N) (timp proporțional cu creșterea datelor);

O(N2) pătratică;

complexitatea polinomială O(N M), în special, complexitatea cubică O(N 3);

complexitate exponenţială O(2 N);

complexitate factorială O(N!);

complexitate logaritmică O(log(N)) (implica logaritmul de bază 2);

complexitate liniar-logaritmică O(N * log(N)) ;

complexitate de calcul constantă O(1) (timpul nu depinde de cantitatea de date).

Această listă nu exclude apariția altor funcții, dar marea majoritate a cazurilor întâlnite în practică sunt enumerate aici. Aceste funcții pot fi ordonate de la cel mai eficient la cel mai puțin eficient după cum urmează:

Complexitatea de calcul a algoritmilor dezvoltați ar trebui să fie cât mai limitată posibil. Relația dintre aceste estimări poate fi simțită prin reprezentarea numărului de instrucțiuni executate pe exemple specifice, să zicem la N=5, 10, 25, 100 și 500 (presupunem că coeficienții constanți sunt aceiași pentru ușurință de înțelegere). Cu această cantitate de date, obținem următorii indicatori:

				asa de mult	asa de mult
			asa de mult	asa de mult	asa de mult

Complexitatea computațională constantă este un caz ideal, adesea algoritmi cu o asemenea complexitate pur și simplu nu există pentru rezolvarea problemelor. Funcția logaritmică crește, de asemenea, relativ lent. Funcțiile liniare și liniar-logaritmice cresc într-un ritm acceptabil. Alte funcții cresc considerabil mai repede.

Dacă programul aparține cercetării, complexitatea maximă admisă este polinomială, în special, cubică. Algoritmii cu complexitate de calcul mai mare sunt aplicabili doar pentru valori mici ale lui N, altfel problemele nu au o soluție computerizată cu costuri de calcul realizabile.

În același timp, în sectorul software comercial, unde nu doar realizabilitatea rezultatului în general este importantă, ci și timpul de așteptare acceptabil pentru utilizator, sunt rar utilizați algoritmi a căror complexitate depășește liniar-logaritmică.

O estimare superficială a complexității computaționale

În literatura clasică privind construcția și analiza algoritmilor, se acordă multă atenție calculelor matematice riguroase care derivă și demonstrează analitic ipoteze despre complexitatea computațională a unor algoritmi specifici. Programatorii practicanți acordă mult mai puțină atenție acestui proces, evitând raționamentul în stilul strict formal al matematicienilor. Cu toate acestea, dacă codul programului care implementează un anumit algoritm nu este prea complicat, se pare că se poate exprima o ipoteză despre complexitatea de calcul apropiată de cea corectă doar pe baza structurii generale a codului programului.

Mai jos sunt câteva indicii pentru o estimare superficială a complexității computaționale „pe ochi”, fără o abordare analitică riguroasă.

Toate instrucțiunile elementare - evaluarea expresiilor, alocarea variabilelor, intrare-ieșire, returnare a valorii - ar trebui considerate ca fiind cele mai simple blocuri cu complexitate de calcul constantă O(1).

Complexitatea de calcul a unei secvențe de instrucțiuni este egală cu complexitatea maximă a instrucțiunilor incluse în ea.

Dacă nu există informații speciale despre probabilitatea de a se declanșa săriturile condiționate, atunci toate săriturile condiționate posibile, inclusiv cele implicite (omise altfel, ramuri implicite), ar trebui considerate echiprobabile. Complexitatea fiecărui bloc de instrucțiuni este evaluată separat, iar apoi este selectat maximul dintre ele, care devine rezultatul evaluării pentru constructul condiționat în ansamblu.

Dacă instrucțiunea se află în corpul buclei, al cărei număr de iterații depinde de N, atunci complexitatea de calcul a instrucțiunii este înmulțită cu o funcție liniară.

Complexitatea de calcul a două bucle N-dependente imbricate una în cealaltă este cel mai probabil descrisă de o funcție pătratică. În consecință, cuibărirea pe 3 niveluri corespunde complexității cubice.

Dacă un algoritm împarte un set de intrări în bucăți și apoi le procesează separat de același algoritm recursiv - complexitatea de calcul este logaritmică.

Mulți algoritmi sunt recursivi, de exemplu. se numesc cu argumente diferite. În același timp, pentru a ieși din recursivitate, trebuie să existe întotdeauna o „condiție de ieșire” - valorile argumentelor la care recursiunea este întreruptă și se efectuează o acțiune elementară. Cel mai simplu exemplu este funcția factorială:

int factorial( int _X)

dacă(_X< 1)

întoarcere 0;

altfel dacă(_x==1)

întoarcere 1;

întoarcere _x * factorial(_x - 1);

Primele două ramuri ale condiției principale sunt instrucțiuni elementare, complexitatea lor de calcul este estimată ca O(1). În ceea ce privește ultima ramură, complexitatea este descrisă de așa-numitul relație recurentă:

Pentru a obține o estimare a complexității computaționale, relațiile de recurență trebuie extinse analitic. Înlocuind răspunsurile în formula de complexitate indicată pentru factorul pas cu pas, obținem o relație liniară.

Analiza algoritmului -

Tipuri de analiză

Cel mai rău caz: T(n)

Caz mediu: T(n)

Estimare asimptotică

O

f (n) = O(g(n))

($c > 0, n 0 >

O(g(n)) = (f (n) : $ c > 0, n 0 >

Exemplu: 2n2 = O(n3)

Sortare îmbinare

dacă (pag< r) //1

Arborele recursiv: T(n) = 2*T(n/2) +cn, с –const, c>0

Tehnica de evaluare a algoritmilor recursivi.

Metoda iterației

Pe baza formulei T(n), scriem formula pentru elementul mai mic situat în partea dreaptă a formulei pentru T(n).

Înlocuim partea dreaptă a formulei rezultate în formula originală

Efectuăm primii doi pași până când extindem formula într-o serie fără funcția T(n)

Estimați seria rezultată pe baza unei progresii aritmetice sau geometrice

T(n)=T(n-1)+n, T(1)=1

T(n)=θ(g(n)), g(n)=?

T(n-1)=T(n-2)+(n-1)

T(n-2)=T(n-3)+(n-2)

T(n-3)+(n-2)+(n-1)+n=…

1+…(n-2)+(n-1)+n=

Arborele recursiv - o metodă grafică pentru afișarea unei substituții de relație de sine cu sine

T(n)=2T(n/2)+n2

T(n/4) T(n/4) T(n/4) T(n/4)

(n/2) 2 (n/2) 2 log n (1/2)*n 2

(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2

Metoda de înlocuire

1. Ghici (propune) o soluție
2. Verificați soluția folosind inducție
3. Găsiți și înlocuiți constante

T(n) = 2T(n/2) + n

T(n) = (n log n)

Premisa inducției: T(n) ≤ с * n* log n, c>0

Fie ca această estimare să fie adevărată pentru n/2

T(n/2) ≤ c*(n/2)*log(n/2)

Înlocuiți-l în formula originală pentru T(n)

T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤

c*n*log(n/2)+n =

c*n*log n - c*n*log 2 +n =

c*n*log n - c*n +n ≤

c*n*log n

c≥1, n≥2

Teorema principală a estimatorilor recursivi

T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)

Algoritmi pentru sortarea tablourilor în timp polinomial

Sortare - procesul de rearanjare a obiectelor unui dat

agregate într-o anumită ordine (în creștere

sau în scădere).

Scopul sortării este de obicei de a facilita ulterioare

căutarea elementelor dintr-un set sortat.

Sortare după inserții simple

void sort_by_insertion(key a , int N)

pentru (i=1; i< N; i++)

pentru (j=i-1; (j>=0)&& (x< a[j]); j--)

a = a[j];

Analiza sortării prin inserții simple

Număr de comparații:

C (N) \u003d 1 + 2 + 3 + ... + N - 1 \u003d (N * (N -1)) / 2 \u003d O (N 2)

Timpul total: T(N) = θ(N 2)

Sortați după schimb simplu. metoda bulelor.

void bubble_sort(key a , int N)

pentru (i=0; i

pentru (j=N-l; j>i; j--)

dacă (a > a[j]) (

x = a[j] ; a [ j ] = a [ j -1] ; a[j-1]=x;

Analiză simplă a sortării schimbului

Cel mai rău caz: comandat în ordine inversă matrice

Număr de comparații:

C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2)

Timpul total: T(N) = θ(N 2)

Addendum

Nod* _Add(Nod *r, T s)

r = Nod(e) nou;

altfel dacă (s< r->inf)

r->stânga = _Add(r->stânga, s);

r->dreapta = _Add(r->dreapta, s);

Eliminarea unui element din arbore

Arborele T cu rădăcina n și cheia K.

scoateți din arborele T nodul cu cheia K (dacă există).

Algoritm:

Dacă arborele T este gol, opriți;

În caz contrar, comparați K cu cheia X a nodului rădăcină n.

Dacă K>X, îndepărtați recursiv K din subarborele din dreapta al lui T;

Dacă K

Dacă K=X, atunci este necesar să luăm în considerare trei cazuri.

Dacă nu există ambii copii, atunci ștergem nodul curent și resetam legătura către el de la nodul părinte;

Dacă unul dintre copii nu există, atunci punem valorile câmpurilor copilului m în locul valorilor corespunzătoare ale nodului rădăcină, suprascriind vechile valori ale acestuia și eliberând memoria ocupată de nodul m;

Dacă ambii copii sunt prezenți, atunci găsim nodul m, care este următorul după cel dat;

copiați datele (cu excepția referințelor la elemente copil) de la m la n;

îndepărtați recursiv nodul m.

Elementul care urmează datei

Dat: arborele T și cheia x

Returnăm un pointer la următorul element după x, sau NULL dacă x este ultimul element din arbore.

Algoritm:

Luăm în considerare două cazuri separat.

Dacă subarborele din dreapta al lui x nu este gol, atunci următorul element după x este elementul minim din acest subarboresc.

În caz contrar, dacă subarborele din dreapta al lui x este gol. Mergem de la x în sus până găsim un vârf care este copilul stâng al părintelui său. Acest părinte (dacă există) va fi elementul pe care îl căutați.

Inserarea nodurilor

Inserarea unei noi chei într-un arbore AVL se face în același mod ca și în arborii de căutare simpli: coborâm arborele, alegând direcția de mișcare la dreapta sau la stânga, în funcție de rezultatul comparării cheii în nodul curent. iar cheia fiind introdusă.

Singura diferență este că atunci când recursiunea revine (adică după ce cheia este inserată în subarborele din dreapta sau din stânga), nodul curent este echilibrat. Dezechilibrul care rezultă dintr-o astfel de inserție în orice nod de-a lungul căii de mișcare nu depășește doi, ceea ce înseamnă că aplicarea funcției de echilibrare descrisă mai sus este corectă.

Eliminarea nodurilor

Pentru a elimina un vârf dintr-un arbore AVL, se ia ca bază un algoritm, care este de obicei folosit când se elimină noduri dintr-un arbore binar standard de căutare. Găsim nodul p cu cheia k dată, în subarborele din dreapta găsim nodul min cu cea mai mică cheie și înlocuim nodul p eliminat cu nodul găsit min.

Există mai multe opțiuni de implementare. În primul rând, dacă nodul găsit p nu are un subarboresc drept, atunci, prin proprietatea arborelui AVL, acest nod poate avea un singur nod copil (un arbore de înălțime 1) în stânga, sau nodul p în general este o frunză. În ambele cazuri, trebuie doar să ștergeți nodul p și, ca rezultat, să returnați un pointer către nodul copil din stânga al nodului p.

Acum să fie p un subarboresc drept. Găsiți cheia minimă în acest subarboresc. Prin proprietatea unui arbore binar de căutare, această cheie se află la capătul ramurii din stânga, începând de la rădăcina arborelui. Folosim funcția recursivă findmin.

funcția removemin - prin eliminarea elementului minim din arborele dat. Prin proprietatea unui arbore AVL, elementul minim din dreapta fie are un singur nod, fie este gol. În ambele cazuri, trebuie doar să returnați un pointer la nodul din dreapta și să efectuați echilibrarea la întoarcere (când vă întoarceți de la recursivitate).

Tabele de hash, metoda de înlănțuire

Adresarea directă este utilizată pentru seturi mici de taste. Este necesar să se specifice o mulțime dinamică, fiecare element având o cheie din mulțimea U = (0,1,..., m - 1), unde m nu este prea mare, nu există două elemente care au aceleași chei.

Pentru a reprezenta o mulțime dinamică, se folosește un tablou (un tabel cu adresare directă), T , fiecare poziție sau celulă, din care corespunde unei chei din spațiul cheie U.

Celula k indică un element al mulțimii cu cheia k. Dacă setul nu conține un element cu cheia k, atunci Т[k] = NULL.

Operația de căutare a cheilor necesită timp O(1)

Dezavantajele adresei directe:

Dacă spațiul cheie U este mare, stocarea tabelului T cu dimensiunea |U| imposibil, dacă nu imposibil, în funcție de cantitatea de memorie disponibilă și de dimensiunea spațiului de taste

Setul K de chei stocate efectiv poate fi mic în comparație cu spațiul de chei U, caz în care memoria alocată tabelului T este în mare parte irosită.

O funcție hash este o funcție h care localizează elementele mulțimii U în tabelul T.

În hashing, elementul cu cheia k este stocat în locația h(k), funcția hash h este folosită pentru a calcula locația pentru cheia k dată. Funcția h mapează spațiul cheie U la celulele tabelului hash T [0..m - 1]:

h: U → (0,1,...,m-1).

valoarea h(k) se numește valoarea hash a cheii k.

Când setul K de chei stocat într-un dicționar este mult mai mic decât spațiul posibilelor chei U, tabelul hash necesită mult mai puțin spațiu decât un tabel direct adresabil.

Scopul funcției hash este de a reduce intervalul de lucru al indicilor de matrice și în loc de |U| valori, vă puteți descurca cu doar m valori.

Cerințele de memorie pot fi reduse la θ(|K|), în timp ce timpul de căutare a unui element într-un tabel hash rămâne O(1) - aceasta este limita timpului mediu de căutare, în timp ce în cazul unui tabel cu adresare directă, această limită este valabilă în cel mai rău caz.

O coliziune este o situație în care două chei se mapează la aceeași celulă.

De exemplu, h(43) = h(89) = h(112) = k

Metoda lanțului:

Idee: stocați elemente ale unui set cu aceeași valoare hash ca o listă.

h(51) = h(49) = h(63) = i

Analiză

Cel mai rău caz: dacă funcția hash pentru toate elementele setului produce aceeași valoare. Timpul de acces este Θ(n), pentru |U | = n.

Caz mediu: Pentru cazul în care valorile hash sunt distribuite uniform.

Fiecare cheie cu probabilitate egală poate intra în orice celulă a tabelului, indiferent de unde au ajuns alte chei.

Fie dat tabelul T și n chei sunt stocate în el.

Apoi, a = n/m este numărul mediu de chei din celulele tabelului.

Timpul de căutare pentru elementul lipsă este Θ(1 + α).

Timpul constant pentru a calcula valoarea hash plus timpul pentru a parcurge lista până la sfârșit, deoarece lungimea medie a listei este α, atunci rezultatul este Θ(1) + Θ(α) = Θ(1 + α)

Dacă numărul de celule din tabel este proporțional cu numărul de elemente stocate în acesta, atunci n = O(m) și, prin urmare, α = n/m = O(m)/m = O(1), ceea ce înseamnă că căutarea unui element în tabelul hash durează în medie timp Θ(1).

Operațiuni

Inserarea unui element într-un tabel

Îndepărtarea

necesită, de asemenea, timp O(1).

Selectarea unei funcții hash

Cheile ar trebui să fie distribuite uniform în toate celulele

Modelul de distribuție a cheilor hash nu ar trebui să se coreleze cu modelele de date. (De exemplu, datele sunt numere pare.)

Metode:

metoda diviziunii

metoda înmulțirii

metoda diviziunii

h(k) = k mod m

Problema divizorului mic m

Exemplul #1. m = 2 iar toate cheile sunt pare Þ celulele impare nu sunt

umplut.

Exemplul #2. m = 2rÞ hash este independent de biții de mai sus r.

metoda înmulțirii

Lăsa m= 2 r , cheile sunt cuvinte pe w biți.

h(k) = (A k mod 2 w) >> (w - r), Unde

A mod 2 = 1 ∩ 2 w-1< A< 2 w

El nu ar trebui să aleagă A aproape de 2 w-1Și 2w

Aceasta metoda metoda mai rapida Divizia

Metoda înmulțirii: exemplu

m = 8 = 2 3 , w = 7

Adresare deschisă: căutare

Căutarea este, de asemenea, cercetare secvențială

Succes când a găsit sensul

Eșec când a găsit o celulă goală sau a trecut întregul tabel.

Strategii de cercetare

Linear -

h(k, i) = (h′(k) + i) mod m

Această strategie este ușor de implementat, dar este supusă problemei

gruparea primară asociată cu crearea unei secvențe lungi

numărul de celule ocupate, ceea ce mărește timpul mediu de căutare.

pătratică

h(k, i) = (h′(k) + с 1 i+ с 2 i 2) mod m

unde h′(k) este funcția hash obișnuită

Hashing dublu -

h(k,i) = (h 1 (k) + i h 2 (k)) mod m.

hashing dublu

Această metodă dă rezultate excelente, dar h 2 (k) trebuie să fie relativ prim față de m.

Acest lucru poate fi realizat:

folosind puteri de 2 ca m și făcând h 2 (k) produc doar numere impare

m = 2 r și h 2 (k)- ciudat.

m- număr prim, valori h 2 sunt numere întregi pozitive mai mici decât m

Pentru simplu m poate fi instalat

h1(k)=k mod m

h2(k)=1+(k mod m')

m' este mai mic decât m (m' =m-1 sau m-2)

Deschideți Adresare: Exemplu de lipire

Fie dat tabelul A:

hashing dublu

h2(k)=1+(k mod 11)

Unde va fi încorporat elementul?

Analiza adresei deschise

O ipoteză suplimentară pentru hashing uniform este că fiecare cheie are la fel de probabil să primească oricare dintre m! permutări ale secvenţelor de studiu de tabel

indiferent de alte chei.

Găsirea unui element lipsă

Numărul de sonde pentru o căutare reușită

adresare deschisă

A< 1 - const Þ O(1)

Cum se comportă A:

Tabelul a finalizat 50% Þ2 studiu

Tabelul 90% complet Þ 10 studii

Tabelul 100% studii complete Þ m

Principiul alegerii lacome

Se spune că pentru o problemă de optimizare aplicăm principiul alegerii lacome, dacă secvența este locală alegeri optime oferă o soluție optimă la nivel global.

Într-un caz tipic, dovada optimității urmează următoarea schemă:

Este dovedit că alegerea lacomă la primul pas nu închide calea către soluția optimă: pentru fiecare soluție există o altă soluție care este în concordanță cu alegerea lacomă și nu este mai rea decât prima.

Se arată că subproblema care apare după alegerea lacomă la primul pas este similară cu cea inițială.

Argumentul se termină prin inducție.

Optimitate pentru subsarcini

Se spune că sarcina are proprietatea optimitatea pentru subprobleme, dacă soluția optimă a problemei conține soluțiile optime pentru toate subproblemele ei.

Construirea Codului Huffman

Orice mesaj constă dintr-o secvență de caractere dintr-un anumit alfabet. Adesea, pentru a economisi memorie, pentru a crește viteza de transfer de informații, apare sarcina de a comprima informațiile. În acest caz, sunt utilizate metode speciale de codificare a caracterelor. Acestea includ coduri Huffman, care oferă compresie de la 20% la 90%, în funcție de tipul de informații.

Algoritmul Huffman găsește codurile optime de caractere pe baza frecvenței caracterelor din textul comprimat.

Algoritmul lui Huffman este un exemplu de algoritm lacom.

Să fie cunoscute frecvențele de caractere într-un fișier cu lungimea de 100000 de caractere:

Trebuie să construim un cod binar în care fiecare caracter este reprezentat ca o secvență finită de biți, numită cuvânt de cod. Când se utilizează un cod uniform, în care toate cuvintele de cod au aceeași lungime, se cheltuiesc minim trei biți pentru fiecare caracter și se vor cheltui 300.000 de biți pentru întreg fișierul.

Un cod neuniform va fi mai economic dacă caracterele care apar frecvent sunt codificate cu secvențe scurte de biți și caracterele care apar rar cu caractere lungi. La codificarea întregului fișier, va dura (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. Adică, un cod neuniform oferă aproximativ 25% economii .

Coduri de prefix

Luați în considerare codurile în care, pentru fiecare dintre cele două secvențe de biți care reprezintă caractere diferite, niciunul nu este un prefix al celuilalt. Astfel de coduri se numesc coduri de prefix.

La codificare, fiecare caracter este înlocuit cu propriul său cod. De exemplu, șirul abc arată ca 0101100. Pentru un cod prefix, decodarea este unică și se face de la stânga la dreapta.

Primul caracter al unui text codificat cu un cod prefix este determinat în mod unic, deoarece cuvântul său cod nu poate fi începutul niciunui alt caracter. După ce am determinat acest caracter și i-am eliminat cuvântul de cod, repetăm ​​procesul pentru biții rămași și așa mai departe.

Pentru a implementa eficient decodarea, trebuie să stocați informații despre cod într-o formă convenabilă. O posibilitate este reprezentarea codului în formă arbore binar cod, ale căror frunze corespund caracterelor codificate. În acest caz, calea de la rădăcină la caracterul codificat determină secvența de codare a biților: deplasarea de-a lungul arborelui la stânga dă 0, iar deplasarea la dreapta dă 1.

Nodurile interne indică suma frecvențelor pentru frunzele subarborelui corespunzător.

Codul optim pentru un fișier dat corespunde întotdeauna unui arbore binar în care fiecare vârf care nu este o frunză are doi fii. Codul uniform nu este optim deoarece arborele corespunzător conține un nod cu un singur copil.

Un arbore de cod de prefix optim pentru un fișier care utilizează toate caracterele dintr-un set C și numai ele conțin exact | C | frunze, câte una pentru fiecare caracter și exact | C | - 1 noduri care nu sunt frunze.

Cunoscând arborele T corespunzător codului de prefix, este ușor de găsit numărul de biți necesari pentru codificarea fișierului. Pentru fiecare caracter c din alfabetul C, fie f[c] de câte ori apare în fișier și dT(c) adâncimea foii sale corespunzătoare și, prin urmare, lungimea secvenței de biți care codifică c. Apoi, pentru a codifica fișierul, veți avea nevoie de:

Această valoare se numește costul arborelui T. Este necesar să se minimizeze această valoare.

Huffman a propus un algoritm lacom care construiește un cod de prefix optim. Algoritmul construiește un arbore T corespunzător codului optim de jos în sus, începând cu un set de | C | frunze si facerea | C | - 1 îmbinare.

Pentru fiecare simbol este dată frecvența sa f [c]. Pentru a găsi două obiecte de îmbinat, se folosește o coadă de prioritate Q, folosind frecvențele f drept priorități - cele două obiecte cu cele mai joase frecvențe sunt îmbinate.

În urma îmbinării, se obține un nou obiect (vârf intern), a cărui frecvență este considerată egală cu suma frecvențelor celor două obiecte îmbinate. Acest vârf este adăugat la coadă.

Huffman C)

1.n ←│C│ │ C │- putere С

2.Q ← C Q - coada de prioritate

3. pentru i ← 1 la n-1

4. do z ← Create_Node() z este un nod format din câmpuri f, stânga, dreapta

5. x ← stânga [z] ← Scoateți la coadă(Q)

6. y ← dreapta [z] ← Scoateți la coadă(Q)

7. f[z] ← f[x] + f[y]

8. Pune în coadă(Q, z)

9. întoarcere Scoateți la coadă(Q) returnează rădăcina arborelui

Nota

Coada este implementată ca un heap binar.

Puteți crea o coadă în O(n).

Algoritmul constă dintr-o buclă care este executată de n-1 ori.

Fiecare operație în coadă ia O(log n).

Timp total de funcționare O(n log n).

Problema construirii unei rețele

Zone de origine: comunicații și rețele rutiere.

Dat: set de noduri de rețea (gazde, orașe).

Necesar: construirea unei rețele cu cea mai mică greutate totală a marginilor (lungimea cablurilor de rețea, lungimea drumurilor).

Model grafic: nodurile de rețea sunt noduri grafice, E = V2, știm greutățile tuturor marginilor.

Rezultat: copac liber.

Abordarea căutării MOD

Construim arborele A adăugând câte o margine la un moment dat, iar înainte de fiecare iterație, arborele curent este un subset al unor MOD.

La fiecare pas al algoritmului, definim o muchie (u, v) care poate fi adăugată la A fără a încălca această proprietate. Vom numi un astfel de seif de margine.

GenericMST(G, w)

2 în timp ce A nu este un mod

3 Găsiți o muchie (u, v) care este sigură pentru A

4 A ← A U ((u, v))

____________________________________________________________________________

Clasificarea coastelor

1. coaste de copac(muchiile arborelui) sunt muchiile graficului G. O muchie (u, v) este o muchie a arborelui dacă v este descoperit la explorarea acestei muchii.

2. Coaste inversate(muchiile din spate) sunt muchii (u,v) care leagă vârful u de strămoșul său v în arborele de căutare de adâncime. Ciclurile de margine care pot apărea în graficele direcționate sunt tratate ca margini din spate.

3. coaste drepte(muchiile înainte) sunt muchii care nu sunt arbore (u,v) care conectează vârful u la descendentul său v în arborele de căutare de adâncime.

4. Coaste încrucișate(muchii încrucișate) - toate celelalte muchii ale graficului. Ele pot uni vârfuri în același arbore DFS când niciunul dintre vârfuri nu este un strămoș al celuilalt, sau pot uni vârfuri în arbori diferiți.

Algoritmul DFS poate fi modificat în așa fel încât să clasifice marginile întâlnite în timpul funcționării. Ideea cheie este că fiecare muchie (u, v) poate fi clasificată după culoarea vârfului v prima dată când este examinată (cu toate acestea, muchiile drepte și încrucișate nu se disting).

1. culoare alba spune că aceasta este o margine a unui copac.
2. Culoarea gri definește marginea din spate.
3. Negrul indică o margine dreaptă sau încrucișată.

Primul caz rezultă direct din definiția algoritmului.

Având în vedere al doilea caz, rețineți că vârfurile gri formează întotdeauna un lanț liniar de copii corespunzător stivei de apeluri active la procedura DFS_Visit; numărul de vârfuri gri este cu unul mai mult decât adâncimea ultimului vârf deschis în arborele de căutare depth-first. Explorarea începe întotdeauna de la cel mai adânc vârf gri, astfel încât o muchie care ajunge la un alt vârf gri ajunge la părintele vârfului original.

În al treilea caz, avem de-a face cu marginile rămase care nu se încadrează în primul sau al doilea caz. O muchie (u, v) poate fi arătată drept dacă d [u]< d [v], и перекрестным, если d [u] >d[v]

___________________________________________________________________________

Sortare topologică

ÎN coloana de prioritate fiecare muchie (u, v) înseamnă că u precede v

Sortare topologică graficul este construcția unei secvențe a, unde pentru toate a i și a j $(а i ,а j) Þ i< j.

Tipul topologic al unui graf aciclic direcționat G = (V, E) este o ordonare liniară a tuturor vârfurilor sale, astfel încât, dacă graficul G conține o muchie (u, v), atunci u este situat înaintea v sub această ordonare (dacă graficul nu este aciclică, o astfel de sortare nu este posibilă). Sortarea topologică a unui grafic poate fi considerată ca ordonarea vârfurilor de-a lungul unei linii orizontale, astfel încât toate muchiile să fie îndreptate de la stânga la dreapta.

Secvență sortată: C2, C6, C7, C1, C3, C4, C5, C8

pentru fiecare(u în V) culoare[u] = alb; // inițializați

L = new linked_list; // L este o listă conexă goală

pentru fiecare (u în V)

if (culoare[u] == alb) TopVisit(u);

întoarce L; // L dă ordinea finală

TopVisit(u) ( // începe o căutare la u

culoare[u] = gri; // marchează că ai vizitat

pentru fiecare (v în Adj(u))

if (culoare[v] == alb) TopVisit(v);

Adăugați u în fața lui L; // la terminare, adăugați la listă

T (n) = Θ(V + E)

Proceduri

Creați - Setați (u)- creați o mulțime dintr-un vârf u.

Găsiți - Setați (u)- găsiți mulțimea căreia îi aparține vârful urevine în ce set se află elementul specificat. De fapt, aceasta returnează unul dintre elementele setului (numit reprezentant sau lider). Acest reprezentant este ales în fiecare set de structura de date în sine (și se poate modifica în timp, și anume, după apeluri Uniune).

Dacă apelul Find - Set pentru oricare două elemente a returnat aceeași valoare, atunci aceasta înseamnă că aceste elemente sunt în același set, altfel sunt în seturi diferite.

Unire (u,v)- îmbinare seturi care conțin vârfuri uȘi v

Seturile de elemente vor fi stocate în formular copaci: un arbore corespunde unui set. Rădăcina arborelui este reprezentantul (conducătorul) mulțimii.

Când este implementat, aceasta înseamnă că obținem o matrice mamă, în care pentru fiecare element stocăm o referință la strămoșul său în arbore. Pentru rădăcinile copacilor, vom presupune că strămoșul lor este ei înșiși (adică, buclele de legătură în acest loc).

Pentru a crea un nou element (operațiune Creare-Set), pur și simplu creăm un arbore înrădăcinat la nodul v , observând că strămoșul său este el însuși.

Pentru a îmbina două seturi (operația uniune(a,b)), găsim mai întâi liderii mulțimii care conține a și mulțimii care conține b. Dacă liderii coincid, atunci nu facem nimic - asta înseamnă că seturile au fost deja unite. În caz contrar, puteți specifica pur și simplu că strămoșul nodului b este egal cu f (sau invers) - unind astfel un arbore cu altul.

În sfârșit, implementarea operațiunii de căutare a liderului ( Găsiți - Setați(v)) este simplu: urcăm strămoșii din v-ul de sus până ajungem la rădăcină, adică. până când referinţa strămoşilor se comportă. Această operație este mai convenabilă de implementat recursiv.

Euristică de compresie a căii

Această euristică este concepută pentru a accelera lucrurile Găsiți - Setați() .

Constă în faptul că atunci când, după apel Găsiți - Setați(v) vom găsi liderul pe care-l căutăm p set, apoi amintiți-vă că vârful vși toate vârfurile au trecut pe parcurs – este acest conducător p. Cel mai simplu mod de a face acest lucru este redirecționarea acestora mamă la acest vârf p .

Astfel, șirul de strămoși mamă sensul se schimbă oarecum: acum este matrice comprimată de strămoși, adică pentru fiecare vârf, poate stoca nu strămoșul imediat, ci strămoșul strămoșului, strămoșul strămoșului strămoșului și așa mai departe.

Pe de altă parte, este clar că este imposibil să faci aceste indicații mamă arătat mereu către lider: în caz contrar, la efectuarea operației Uniune ar trebui să actualizeze liderii Pe) elemente.

Deci la o matrice mamă ar trebui tratată exact ca o matrice strămoșească, eventual comprimată parțial.

Aplicarea euristicii de compresie a căilor permite realizarea asimptoticelor logaritmice: în medie pe cerere

Analiză

Inițializare - O(V)

Bucla rulează de V ori și fiecare operație extractMin durează - O(logV) ori, total O(V logV) ori

Bucla for rulează O(E) ori, reduceKey are timp O(logV).

Timp total de funcționare - O(V log V +E logV)= O (E logV)

Proprietatea cea mai scurtă cale

Lăsa p = (v 1 , v 2 ..... v k)- calea cea mai scurtă de la vârful v 1 la vârf v kîntr-un grafic direcționat ponderat dat G=(U.E) cu functie de greutate w: E → R A p ij = (v i , v i+1 .....v j)- calea parțială a căii p care merge de la vârf v iîn partea de sus vj pentru arbitrar i și j (1 ≤ i< j ≤ k). Apoi p ij este calea cea mai scurtă de la vârf v i La v i

Dijkstra(G, w, s) (

pentru fiecare (u în V) ( // inițializare

d [u] = +infinit

culoare[u] = alb

d[s] =0 // distanța la sursă este 0

Q = nou PriQueue(V) // pune toate vârfurile în Q

în timp ce (Q.nonEmpty()) ( // până când toate nodurile sunt procesate

u = Q. extractMin() // selectează u cel mai apropiat de s

pentru fiecare (v în Adj[u]) (

dacă (d[u] + w(u,v)< d[v]) { // Relax(u,v)

d[v] = d[u] + w(u,v)

Q.decreaseKey(v, d[v])

culoare[u] = negru

Evaluare de dificultate

Algoritmul Bellman-Ford își finalizează activitatea în timp O(V*E), deoarece inițializarea în linia 1 durează timp O(V), pentru fiecare |V| - 1 margine merge în liniile 2-4 durează timp O(E), iar bucla for din liniile 5-7 durează timp O(E). .

Estimarea asimptotică a algoritmului

Analiza algoritmului - studiul teoretic al performanţelor programelor de calculator şi al resurselor pe care acestea le consumă.

Viteză - timpul algoritmului, în funcție de cantitatea de date de intrare.

Este determinată de funcția T(n), unde n este cantitatea de date de intrare

Tipuri de analiză

Cel mai rău caz: T(n) este timpul maxim pentru orice date de intrare de dimensiunea n.

Caz mediu: T(n) este timpul așteptat pentru orice intrare de dimensiune n.

Cel mai bun caz este timpul minim de funcționare.

Estimare asimptotică

O- notatie: limita superioara asimptotica

f (n) = O(g(n))

($c > 0, n 0 > 0 z 0 ≤ f (n) ≤ c g(n), n ≥ n 0)

O(g(n)) = (f (n) : $ c > 0, n 0 > 0 z 0 ≤ f (n) ≤ c g(n), n ≥ n 0 )

Exemplu: 2n2 = O(n3)

Algoritmi recursivi, construirea unei estimări asimptotice. Exemplu

Sortare îmbinare

sort(А,p,r) //p - începutul matricei, r - sfârșitul matricei T(n)

dacă (pag< r) //1

q=(p + r)/2; // Calculați mijlocul matricei 1

sortare(A, p, q); //sortează partea stângă a lui T(n/2)

sortare(A,q+1,r); //sortează partea dreaptă a lui T(n/2)

merge(p,q,r); //unește două matrice într-un singur n