Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 7: Sortarea prin interclasare- Algoritmi Divide-et-Impera
- Prezentare generală a sortării prin interclasare (îmbinare)
- Provocare: Implementează sortarea prin îmbinare
- Îmbinarea în timp liniar
- Provocare: Implementează îmbinarea
- Analiza sortării prin îmbinare
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
Analiza sortării prin îmbinare
Având în vedere faptul că funcția timp atunci când interclasează elemente, cum demonstrăm că timp? Începem prin a ne aminti cele trei părți ale paradigmei divide et impera și justificarea timpilor lor de execuție. Presupunem că sortăm elemente din șir.
merge
se execută în mergeSort
se execută în - Pasul divide se execută în timp constant, indiferent de dimensiunea subșirului. La urma urmei, acesta calculează doar valoarea lui
, aflat la mijlocul șirului delimitat de și . Amintește-ți că în cazul notației Θ, scriem timpul constant sub forma . - Pasul de rezolvare, în care sortăm recursiv două subșiruri a câte aproximativ
elemente fiecare, se execută și el într-un anumit timp, dar vom justifica acest timp atunci când analizăm subproblemele. - Pasul de combinare interclasează în total
elemente, în timp.
Dacă ne gândim la pasul divide și la cel de combinare simultan, timpul de execuție al pasului divide are gradul mic comparativ cu timpul al pasului de combinare. Așadar, să ne gândim că cei doi pași se execută împreună în timp. Concret, să spunem că pasul divide și cel de combinare se execută în timp, pentru o constantă oarecare .
Pentru a simplifica lucrurile, să presupunem că dacă , atunci este întotdeauna par, astfel încât să fie întotdeauna un număr întreg. (Dacă am lua în considerare cazul în care este impar, nu ar schimba cu nimic rezultatul din punctul de vedere al notației Θ). Așadar, putem privi timpul de execuție pentru elemente ca fiind suma dublului timpului de execuție pentru elemente (pentru pasul de rezolvare) plus (pentru pasul divide și cel de combinare - de fapt, pentru interclasare).
mergeSort
pe un vector cu mergeSort
pe un vector cu Acum trebuie să calculăm timpul de execuție a două apeluri recursive pe elemente. Fiecare dintre aceste apeluri recursive se execută în timp dublu față de algoritmul elemente (deoarece trebuie să înjumătățim ) plus pentru interclasare. Avem două subprobleme de dimensiune , iar interclasarea fiecăreia se execută în timp, deci timpul total pe care îl petrecem la interclasarea subproblemelor de dimensiune este .
mergeSort
pe un subșir de Să desenăm timpii de interclasare sub formă de arbore:
Informaticienii desenează arborii invers față de cum cresc copacii în natură. Un arbore este un graf aciclic (un ciclu este un drum care începe și se termină în același loc). Convenția este să numim vârfurile arborelui noduri. Rădăcina este nodul din vârf; aici, aceasta este etichetată cu , reprezentând dimensiunea vectorului inițial. Rădăcina are doi copii, iar fiecare este etichetat cu , dimensiunea subșirurilor pentru cele două subprobleme de dimensiune .
Fiecare subproblemă de dimensiune sortează recursiv două subșiruri de dimensiune , adică elemente. Deoarece există două subprobleme de dimensiune , sunt patru subprobleme de dimensiune . Fiecare dintre aceste patru subprobleme interclasează elemente, deci timpul de execuție al interclasării pentru fiecare subproblemă este . Calculând suma timpilor pentru cele patru subprobleme, obținem totalul de :
Ce crezi că s-ar întâmpla în cazul subproblemelor de dimensiune ? Ar exista opt de acest tip, iar timpul de interclasare pentru fiecare dintre ele ar fi egal cu , rezultând un timp total de interclasare egal cu :
Pe măsură ce subproblemele devin mai mici, numărul acestora se dublează pe fiecare „nivel” al procesului recursiv, dar timpul de interclasare se înjumătățește. Dublarea și înjumătățirea se anulează reciproc, așadar timpul total de interclasare este egal cu pe fiecare nivel recursiv. În final, ajungem la subprobleme de dimensiune 1: cazul elementar (de bază). Sortarea subșirurilor de dimensiune 1 se face în timp, deoarece trebuie să verificăm dacă , iar acest test consumă timp. Câte subșiruri de dimensiune 1 există? Din moment ce am început cu elemente, trebuie să fie subșiruri. Din moment ce fiecare caz elementar (de bază) se execută în timp, să spunem că adunate ocupă timp:
Acum știm în cât timp se execută interclasarea pentru fiecare dimensiune de subproblemă. Timpul total de execuție pentru niveluri, atunci timpul total de interclasare este . Așadar, care este valoarea lui ? Începem cu subprobleme de dimensiune și înjumătățim treptat până când obținem subprobleme de dimensiune 1. Am analizat acest fenomen când am discutat despre căutarea binară, iar răspunsul este . De exemplu, dacă , atunci , și, cu siguranță, arborele are patru niveluri: . Timpul total de execuție pentru . Atunci când folosim notația Θ pentru a caracteriza acest timp de execuție, putem renunța la termenul de grad mic ( ) și la coeficientul constant ( ), obținând astfel timpul de execuție , așa cum am promis.
mergeSort
este suma timpilor de pe toate nivelurile. Dacă arborele are mergeSort
este, așadar, Un alt lucru despre sortarea prin interclasare merită menționat. În timpul interclasării, algoritmul face o copie a vectorului ce urmează să fie sortat, punând jumătate în
lowHalf
și jumătate în highHalf
. Deoarece copiază mai mult de un număr constant de elemente la un moment dat, spunem că sortarea prin interclasare nu lucrează pe loc. Prin comparație, atât sortarea prin selecție, cât și sortarea prin inserție lucrează pe loc, deoarece nu fac niciodată o copie a unui număr semnifictiv de elemente la un moment dat. Informaticienii verifică dacă un algoritm lucrează pe loc, deoarece există unele sisteme în care spațiul este limitat, iar acest tip de algoritmi este preferat.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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.
Vrei să te alături conversației?
Nici o postare încă.