If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

Biblioteca de informatică

Curs: Biblioteca de informatică > Unitatea 1

Lecția 7: Sortarea prin interclasare
Calculatoare
Biblioteca de informatică
Bazele informaticii
Sortarea prin interclasare
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie

Analiza sortării prin îmbinare

Clasa Google
Având în vedere faptul că funcția merge se execută în Θ(n) timp atunci când interclasează n elemente, cum demonstrăm că mergeSort se execută în Θ(nlog2⁡n) 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 n elemente din șir.
  1. Pasul divide se execută în timp constant, indiferent de dimensiunea subșirului. La urma urmei, acesta calculează doar valoarea lui q, aflat la mijlocul șirului delimitat de p și r. Amintește-ți că în cazul notației Θ, scriem timpul constant sub forma Θ(1).
  2. Pasul de rezolvare, în care sortăm recursiv două subșiruri a câte aproximativ n/2 elemente fiecare, se execută și el într-un anumit timp, dar vom justifica acest timp atunci când analizăm subproblemele.
  3. Pasul de combinare interclasează în total n elemente, în Θ(n) timp.
Dacă ne gândim la pasul divide și la cel de combinare simultan, timpul de execuție Θ(1) al pasului divide are gradul mic comparativ cu timpul Θ(n) al pasului de combinare. Așadar, să ne gândim că cei doi pași se execută împreună în Θ(n) timp. Concret, să spunem că pasul divide și cel de combinare se execută în cn timp, pentru o constantă oarecare c.
Pentru a simplifica lucrurile, să presupunem că dacă n>1, atunci n este întotdeauna par, astfel încât n/2 să fie întotdeauna un număr întreg. (Dacă am lua în considerare cazul în care n este impar, nu ar schimba cu nimic rezultatul din punctul de vedere al notației Θ). Așadar, putem privi timpul de execuție pentru mergeSort pe un vector cu n elemente ca fiind suma dublului timpului de execuție pentru mergeSort pe un vector cu (n/2) elemente (pentru pasul de rezolvare) plus cn (pentru pasul divide și cel de combinare - de fapt, pentru interclasare).
Acum trebuie să calculăm timpul de execuție a două apeluri recursive pe n/2 elemente. Fiecare dintre aceste apeluri recursive se execută în timp dublu față de algoritmul mergeSort pe un subșir de (n/4) elemente (deoarece trebuie să înjumătățim n/2) plus cn/2 pentru interclasare. Avem două subprobleme de dimensiune n/2, iar interclasarea fiecăreia se execută în cn/2 timp, deci timpul total pe care îl petrecem la interclasarea subproblemelor de dimensiune n/2 este 2⋅cn/2=cn.
Să desenăm timpii de interclasare sub formă de arbore:
O diagramă cu un arbore în stânga și cu timpii de execuție pentru interclasare în dreapta. Arborele este etichetat cu „Dimensiunea subproblemei”, iar partea dreaptă este etichetată cu „Timpul total de interclasare a tuturor subproblemelor de această dimensiune”. Primul nivel al arborelui conține un singur nod n, cu timpul de interclasare corespunzător egal cu c ori n. Al doilea nivel al arborelui conține două noduri 1/2 n, cu timpii de interclasare corespunzători egali cu 2 ori c ori 1/2 n, adică c ori n.
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 n, reprezentând dimensiunea vectorului inițial. Rădăcina are doi copii, iar fiecare este etichetat cu n/2, dimensiunea subșirurilor pentru cele două subprobleme de dimensiune n/2.
Fiecare subproblemă de dimensiune n/2 sortează recursiv două subșiruri de dimensiune (n/2)/2, adică n/4 elemente. Deoarece există două subprobleme de dimensiune n/2, sunt patru subprobleme de dimensiune n/4. Fiecare dintre aceste patru subprobleme interclasează n/4 elemente, deci timpul de execuție al interclasării pentru fiecare subproblemă este cn/4. Calculând suma timpilor pentru cele patru subprobleme, obținem totalul de 4⋅cn/4=cn:
O diagramă cu un arbore în stânga și cu timpii de execuție pentru interclasare în dreapta. Arborele este etichetat cu „Dimensiunea subproblemei”, iar partea dreaptă este etichetată cu „Timpul total de interclasare a tuturor subproblemelor de această dimensiune”. Primul nivel al arborelui conține un singur nod n, cu timpul de interclasare corespunzător egal cu c ori n. Al doilea nivel al arborelui conține două noduri 1/2 n, cu timpii de interclasare corespunzători egali cu 2 ori c ori 1/2 n, adică c ori n. Al treilea nivel al arboreui conține patru noduri 1/4 n, cu timpii de interclasare egali cu 4 ori c ori 1/4 n, adică c ori n.
Ce crezi că s-ar întâmpla în cazul subproblemelor de dimensiune n/8? Ar exista opt de acest tip, iar timpul de interclasare pentru fiecare dintre ele ar fi egal cu cn/8, rezultând un timp total de interclasare egal cu 8⋅cn/8=cn:
O diagramă cu un arbore în stânga și cu timpii de execuție pentru interclasare în dreapta. Arborele este etichetat cu „Dimensiunea subproblemei”, iar partea dreaptă este etichetată cu „Timpul total de interclasare a tuturor subproblemelor de această dimensiune”. Primul nivel al arborelui conține un singur nod n, cu timpul de interclasare corespunzător egal cu c ori n. Al doilea nivel al arborelui conține două noduri 1/2 n, cu timpii de interclasare corespunzători egali cu 2 ori c ori 1/2 n, adică c ori n. Al treilea nivel al arboreui conține patru noduri 1/4 n, cu timpii de interclasare egali cu 4 ori c ori 1/4 n, adică c ori n. Al patrulea nivel al arborelui conține opt noduri 1/8 n, cu timpii de interclasare egali cu 8 ori c ori 1/8 n, adică c ori n.
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 cn 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 Θ(1) timp, deoarece trebuie să verificăm dacă p<r, iar acest test consumă timp. Câte subșiruri de dimensiune 1 există? Din moment ce am început cu n elemente, trebuie să fie n subșiruri. Din moment ce fiecare caz elementar (de bază) se execută în Θ(1) timp, să spunem că adunate ocupă cn timp:
O diagramă cu un arbore în stânga și cu timpii de execuție pentru interclasare în dreapta. Arborele este etichetat cu „Dimensiunea subproblemei”, iar partea dreaptă este etichetată cu „Timpul total de interclasare a tuturor subproblemelor de această dimensiune”. Primul nivel al arborelui conține un singur nod n, cu timpul de interclasare corespunzător egal cu c ori n. Al doilea nivel al arborelui conține două noduri 1/2 n, cu timpii de interclasare corespunzători egali cu 2 ori c ori 1/2 n, adică c ori n. Al treilea nivel al arboreui conține patru noduri 1/4 n, cu timpii de interclasare egali cu 4 ori c ori 1/4 n, adică c ori n. Al patrulea nivel al arborelui conține opt noduri 1/8 n, cu timpii de interclasare egali cu 8 ori c ori 1/8 n, adică c ori n. Sub acel nivel, punctele de suspensie indică pașii intermediari care se execută exact la fel. Nivelul final conține n nodur etichetate cu 1, cu timpii de interclasare corespunzători egali cu n ori c, adică c ori n.
Acum știm în cât timp se execută interclasarea pentru fiecare dimensiune de subproblemă. Timpul total de execuție pentru mergeSort este suma timpilor de pe toate nivelurile. Dacă arborele are l niveluri, atunci timpul total de interclasare este l⋅cn. Așadar, care este valoarea lui l? Începem cu subprobleme de dimensiune n ș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 l=log2⁡n+1. De exemplu, dacă n=8, atunci log2⁡n+1=4, și, cu siguranță, arborele are patru niveluri: n=8,4,2,1. Timpul total de execuție pentru mergeSort este, așadar, cn(log2⁡n+1). Atunci când folosim notația Θ pentru a caracteriza acest timp de execuție, putem renunța la termenul de grad mic (+1) și la coeficientul constant (c), obținând astfel timpul de execuție Θ(nlog2⁡n), așa cum am promis.
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?

Conectare
Nici o postare încă.
Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.