Complexitatea calculului Shell Sort

1. Introducere

Analiza matematică a complexităţii algoritmilor poate fi dificilă în cazul unor algoritmi care nu sunt simpli, mai ales dacă este vorba de analiza cazului mediu. O alternativă la analiza matematică a complexităţii algoritmilor o reprezintă analiza empirică .

În analiza empirică a eficienţei unui algoritm se parcurg următoarele etape:

1. Se stabileşte scopul analizei.

2. Se stabileşte metoda de apreciere a eficienţei: număr de execuţii ale unei/unor operaţii sau timp de execuţie a întregului algoritm sau porţiune de algoritm.

3. Se stabilesc proprietăţile datelor de intrare în raport cu care se face analiza(dimensiunea acestora sau ale proprietăţi specifice).

4. Se transcrie algoritmul într-un limbaj de programare.

5. Se generează mai multe seturi de date de intrare.

6. Se execută programul pentru fiecare set de date de intrare.

7. Se analizează rezultatele obţinute.

Alegerea măsurii de eficienţă depinde de scopul analizei. Dacă, de exemplu, se urmăreşte obţinerea unor informaţii privind clasa de complexitate sau chiar verificarea acurateţei unei estimări teoretice atunci este adecvată utilizarea numărului de operaţii efectuate (numărarea prin program a numărului de operaţii). Dacă scopul evaluării este analiza comportării unui algoritm, atunci este potrivit timpul de execuţie (măsurarea timpului de execuţie prin program).

Timpul necesar execuţiei unui program depinde de numărul operaţiilor ce

trebuiesc executate, care depinde de datele de intrare, deci se schimbă de la o

execuţie la alta.

Există însă un cel mai rău caz, pentru acele date de intrare pentru care numărul operaţiilor efectuate este maxim. În acest caz vorbim de complexitate în cel mai rău caz.

De asemenea, putem vorbi de numărul mediu de operaţii efectuate într-o execuţie. Dacă numărul execuţiilor posibile este finit atunci acest număr mediu este egal cu numărul operaţiilor efectuate în toate execuţiile, împărţit la numărul execuţiilor - complexitate medie.

Complexitatea măsoară eficienţa unui algoritm din punct de vedere al vitezei de lucru, deci a timpului necesar rezolvării unei probleme.

În general, este suficient să determinăm ordinul de mărime al complexităţii în funcţie de numărul datelor de intrare (n). Se spune că o complexitate C este de ordinul nk şi se notează aceasta cu O(nk), dacă există două constante c1, c2 pentru

care: c1 . nk < C < c2 . nk .

Sortarea datelor constă în rearanjarea colecţiei de date astfel încât un câmp al elementelor colecţiei să respecte o anumită ordine. De exemplu, în cartea de telefon, fiecare element (abonat) are un câmp de nume, unul de adresă şi unul pentru numărul de telefon. Colecţia aceasta respectă ordinea alfabetică după câmpul de nume.

Dacă datele pe care dorim să le ordonăm, adică să le sortăm, sunt în memoria internă, atunci procesul de rearanjare a colecţiei îl vom numi sortare internă, iar dacă datele se află într-un fişier (colecţie de date de acelaşi fel aflate pe suport extern), atunci procesul îl vom numi sortare externă.

Fiecare element al colecţiei de date se numeşte articol iar acesta la rândul său este compus din unul sau mai multe componente. O cheie C este asociată fiecărui articol şi este de obicei una dintre componente. Spunem că o colecţie de n articole este ordonată crescător după cheia C dacă C(i) ≤C(j) pentru 1≤i<j≤n, iar dacă C(i) ≥ C(j) atunci este ordonată descrescător.