Complexitatea Calculului Shell Sort

Proiect
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: docx
Pagini : 14 în total
Cuvinte : 3276
Mărime: 76.76KB (arhivat)
Cost: 4 puncte

Cuprins

1. Introducere

2. Descrierea algoritmului

3. Algoritm

4. Analiza algoritmului

5. Efectul incrementului

6. Analiza cazului cel mai defavorabil

7. Aplicatie

8. Bibliografie

Extras din document

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.

Preview document

Complexitatea Calculului Shell Sort - Pagina 1
Complexitatea Calculului Shell Sort - Pagina 2
Complexitatea Calculului Shell Sort - Pagina 3
Complexitatea Calculului Shell Sort - Pagina 4
Complexitatea Calculului Shell Sort - Pagina 5
Complexitatea Calculului Shell Sort - Pagina 6
Complexitatea Calculului Shell Sort - Pagina 7
Complexitatea Calculului Shell Sort - Pagina 8
Complexitatea Calculului Shell Sort - Pagina 9
Complexitatea Calculului Shell Sort - Pagina 10
Complexitatea Calculului Shell Sort - Pagina 11
Complexitatea Calculului Shell Sort - Pagina 12
Complexitatea Calculului Shell Sort - Pagina 13
Complexitatea Calculului Shell Sort - Pagina 14

Conținut arhivă zip

  • Complexitatea Calculului Shell Sort.docx

Alții au mai descărcat și

Arhitectura Calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

Structuri de Date și Algoritmi

1 Tema:Implimentarea tipului abstract de date.Tabloul de structuri. 2 Sarcina:De implimentat tipul abstract de date,tablou de structuri si de...

Structuri de Date și Algoritmi

1.Sarcina Sa se creeze o baza de date care contine datele despre sortimentul unei sectii dintr-un MARKETING .Aceasta baza de date va contine...

Te-ar putea interesa și

Complexitatea Calculului

Teoria complexităţii constituie un domeniu foarte important al teoriei algoritmilor care investighează rezolvabilitatea individuală a problemelor...

Ai nevoie de altceva?