Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 4: Sortarea prin selecție- Sortare
- Provocare: implementare swap
- Pseudocodul sortării prin selecție
- Provocare: Determinarea minimului într-un subvector
- Provocare: implementează sortarea prin selecție
- Analiza sortării prin selecție
- Proiect: vizualizare sortare prin selecție
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
Analiza sortării prin selecție
Sortarea prin selecție parcurge în mod repetat indicii vectorului, iar pentru fiecare indice apelează
indexOfMinimum
și swap
. Dacă lungimea vectorului este n, atunci sunt n indici în vector.Deoarece la fiecare execuție a structurii repetitive sunt rulate două instrucțiuni, ai putea crede că sortarea prin selecție rulează în total 2, n instrucțiuni. Acest lucru nu este adevărat, pentru că
indexOfMinimum
și swap
sunt de fapt funcții care au, la rândul lor, alte instrucțiuni care se execută la apel.Câte instrucțiuni sunt executate la un singur apel al funcției
swap
? În general trei, deci fiecare apel swap
are timp de execuție constant.Câte instrucțiuni sunt executate la un singur apel al funcției
indexOfMinimum
? Trebuie să luăm în considerare și repetiția din indexOfMinimum
. De câte ori se execută aceasta la un apel indexOfMinimum
? Depinde de dimensiunea subșirului peste care iterează. Dacă subșirul este chiar vectorul (așa cum se întâmplă la primul pas), repetiția are loc de n ori, iar dacă subșirul este de lungime 6, repetiția are loc de 6 ori.De exemplu, să spunem că vectorul este de lungime 8 și să ne gândim la modul în care operează sortarea prin selecție.
- La primul apel
indexOfMinimum
, algoritmul verifică toate valorile din vector, deci repetiția dinindexOfMinimum
se execută de 8 ori. - La al doilea apel
indexOfMinimum
, verifică valorile din subșirul cu indici de la 1 la 7, deci repetiția dinindexOfMinimum
se execută de 7 ori. - La al treilea apel, verifică subșirul cu indici de la 2 la 7; repetiția se execută de 6 ori.
- La al patrulea apel, verifică subșirul cu indici de la 3 la 7; repetiția se execută de 5 ori.
- ...
- La al optulea apel și cel final al funcției
indexOfMinimum
, repetiția se execută o singură dată.
Dacă însumăm numărul de execuții ale structurii repetitive din
indexOfMinimum
, obținem 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 execuții.Paranteză: Calcularea sumelor de la 1 la n
Cum calculezi rapid suma 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1? Iată un truc. Haide să schimbăm ordinea în care adunăm numerele. Întâi adunăm 8 + 1, cea mai mare și cea mai mică valoare, și obținem 9. Apoi adunăm 7 + 2, a doua cea mai mare și a doua cea mai mică valoare, și obținem tot 9. Dar dacă adunăm 6 + 3? Tot 9. În final adunăm 5 + 4, tot 9. Deci ce obținem?
Sunt patru perechi de numere, fiecare având suma 9. Iată deci metoda generală pentru a aduna orice șir de numere întregi consecutive:
- Adună cel mai mic și cel mai mare număr.
- Înmulțește suma respectivă cu numărul de perechi.
Dar dacă șirul are lungime impară și nu poți asocia toate numerele două câte două? Pur și simplu privește numărul din mijloc, cel fără pereche, ca fiind jumătate de pereche. De exemplu, haide să adunăm 1 + 2 + 3 + 4 + 5. Avem două perechi întregi (1 + 5 și 2 + 4, fiecare având suma 6) și o jumătate de pereche (3, care este jumătatea lui 6), reprezentând în total 2.5 perechi. Înmulțim 2, point, 5, dot, 6, equals, 15 și obținem răspunsul corect.
Dar dacă numerele pe care le adunăm sunt de la 1 la n? Numim acest șir o progresie aritmetică. Suma celui mai mic și celui mai mare număr este n, plus, 1. Deoarece sunt în total n numere, există n, slash, 2 perechi (indiferent de paritatea lui n). Așadar, suma numerelor de la 1 la n este left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, adică n, squared, slash, 2, plus, n, slash, 2. Încearcă să aplici această formulă pentru n, equals, 5 și n, equals, 8.
Analiza asimptotică a timpului de execuție pentru sortarea prin selecție
Timpul total de execuție pentru sortarea prin selecție are trei componente:
- Timpul de execuție pentru toate apelurile către
indexOfMinimum
. - Timpul de execuție pentru toate apelurile către
swap
. - Timpul de execuție pentru restul repetiției din funcția
selectionSort
.
A doua și a treia componentă sunt ușor de calculat. Știm că se fac n apeluri către
swap
și fiecare apel are timp de execuție constant. Folosindu-ne de notația asimptotică, constatăm că timpul de execuție al tuturor apelurilor swap
este \Theta, left parenthesis, n, right parenthesis. Celelalte instrucțiuni din structura repetitivă din selectionSort
verifică și incrementează variabila repetiței și apelează indexOfMinimum
și swap
. Aceste operații au tot timp de execuție constant și se repetă de n ori, rezultând din nou timpul de execuție \Theta, left parenthesis, n, right parenthesis.Pentru prima componentă (timpul de execuție pentru toate apelurile către
indexOfMinimum
) am calculat deja partea dificilă. Fiecare parcurgere a repetiției din indexOfMinimum
are timp constant de execuție. Numărul de iterații ale repetiției este n la primul apel, apoi n, minus, 1, apoi n, minus, 2 și așa mai departe. Am văzut că această sumă, 1, plus, 2, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, plus, n este o progresie aritmetică al cărei rezultat este left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, sau n, squared, slash, 2, plus, n, slash, 2. Așadar, timpul total pentru toate apelurile către indexOfMinimum
este n, squared, slash, 2, plus, n, slash, 2, de un număr constant de ori. Atunci când folosim notația Θ, nu luăm în considerare nici constantele, nici factorul 1/2 al termenului de ordin mai mic, deci timpul de execuție pentru toate apelurile către indexOfMinimum
este \Theta, left parenthesis, n, squared, right parenthesis.Adunând timpii de execuție pentru cele trei componente, obținem \Theta, left parenthesis, n, squared, right parenthesis pentru apelurile către
indexOfMinimum
, \Theta, left parenthesis, n, right parenthesis pentru apelurile către swap
și \Theta, left parenthesis, n, right parenthesis pentru restul repetiției din selectionSort
. \Theta, left parenthesis, n, squared, right parenthesis este termenul dominant, deci putem afirma că timpul de execuție al sortării prin selecție este \Theta, left parenthesis, n, squared, right parenthesis.De asemenea, trebuie să observi că niciun caz nu este favorabil sau nefavorabil pentru sortarea prin selecție. Repetiția din
indexOfMinimum
va face mereu n, squared, slash, 2, plus, n, slash, 2 iterații, indiferent de datele de intrare. Prin urmare, putem spune că sortarea prin selecție are timpul de execuție \Theta, left parenthesis, n, squared, right parenthesis în toate cazurile.Haide să vedem cum \Theta, left parenthesis, n, squared, right parenthesis influențează în realitate timpul de execuție. Să presupunem că sortarea prin selecție sortează n valori în aproximativ n, squared, slash, 10, start superscript, 6, end superscript secunde. Inițial vom alege o valoare mai mică pentru n, de exemplu n, equals, 100. Asta înseamnă că timpul de execuție al sortării prin selecție este de aproximativ 100, squared, slash, 10, start superscript, 6, end superscript, equals, 1, slash, 100 secunde, ceea ce pare destul de puțin. Dar dacă n, equals, 1000? Atunci sortarea prin selecție ar dura aproximativ 1000, squared, slash, 10, start superscript, 6, end superscript, equals, 1 secundă. Dimensiunea vectorului a crescut de 10 ori, dar timpul de execuție a crescut de 100 de ori. Dacă n, equals, 1, comma, 000, comma, 000? Atunci sortarea prin selecție ar dura 1, comma, 000, comma, 000, squared, slash, 10, start superscript, 6, end superscript, equals, 1, comma, 000, comma, 000 secunde, adică puțin mai mult 11.5 zile. Creșterea dimensiunii vectorului de 1000 de ori ar crește timpul de execuție de un milion de ori!
Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.
Vrei să te alături conversației?
Nici o postare încă.