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 \Theta, left parenthesis, n, right parenthesis timp atunci când interclasează n elemente, cum demonstrăm că mergeSort se execută în \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis 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 \Theta, left parenthesis, 1, right parenthesis.
  2. Pasul de rezolvare, în care sortăm recursiv două subșiruri a câte aproximativ n, slash, 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 asamblare interclasează în total n elemente, în \Theta, left parenthesis, n, right parenthesis timp.
Dacă ne gândim la pasul divide și la cel de asamblare simultan, timpul de execuție \Theta, left parenthesis, 1, right parenthesis al pasului divide are gradul mic comparativ cu timpul \Theta, left parenthesis, n, right parenthesis al pasului de asamblare. Așadar, să ne gândim că cei doi pași se execută împreună în \Theta, left parenthesis, n, right parenthesis timp. Concret, să spunem că pasul divide și cel de asamblare se execută în c, n timp, pentru o constantă oarecare c.
Pentru a simplifica lucrurile, să presupunem că dacă n, is greater than, 1, atunci n este întotdeauna par, astfel încât n, slash, 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 left parenthesis, n, slash, 2, right parenthesis elemente (pentru pasul de rezolvare) plus c, n (pentru pasul divide și cel de asamblare - de fapt, pentru interclasare).
Acum trebuie să calculăm timpul de execuție a două apeluri recursive pe n, slash, 2 elemente. Fiecare dintre aceste apeluri recursive se execută în timp dublu față de algoritmul mergeSort pe un subșir de left parenthesis, n, slash, 4, right parenthesis elemente (deoarece trebuie să înjumătățim n, slash, 2) plus c, n, slash, 2 pentru interclasare. Avem două subprobleme de dimensiune n, slash, 2, iar interclasarea fiecăreia se execută în c, n, slash, 2 timp, deci timpul total pe care îl petrecem la interclasarea subproblemelor de dimensiune n, slash, 2 este 2, dot, c, n, slash, 2, equals, c, n.
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, slash, 2, dimensiunea subșirurilor pentru cele două subprobleme de dimensiune n, slash, 2.
Fiecare subproblemă de dimensiune n, slash, 2 sortează recursiv două subșiruri de dimensiune left parenthesis, n, slash, 2, right parenthesis, slash, 2, adică n, slash, 4 elemente. Deoarece există două subprobleme de dimensiune n, slash, 2, sunt patru subprobleme de dimensiune n, slash, 4. Fiecare dintre aceste patru subprobleme interclasează n, slash, 4 elemente, deci timpul de execuție al interclasării pentru fiecare subproblemă este c, n, slash, 4. Calculând suma timpilor pentru cele patru subprobleme, obținem totalul de 4, dot, c, n, slash, 4, equals, c, n:
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, slash, 8? Ar exista opt de acest tip, iar timpul de interclasare pentru fiecare dintre ele ar fi egal cu c, n, slash, 8, rezultând un timp total de interclasare egal cu 8, dot, c, n, slash, 8, equals, c, n:
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 recursiei, 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 c, n pe fiecare nivel de recursie. În final, ajungem la subprobleme de dimensiune 1: cazul de bază. Sortarea subșirurilor de dimensiune 1 se face în \Theta, left parenthesis, 1, right parenthesis timp, deoarece trebuie să verificăm dacă p, is less than, 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 de bază se execută în \Theta, left parenthesis, 1, right parenthesis timp, să spunem că adunate ocupă c, n 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, dot, c, n. 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, equals, log, start base, 2, end base, n, plus, 1. De exemplu, dacă n, equals, 8, atunci log, start base, 2, end base, n, plus, 1, equals, 4, și, cu siguranță, arborele are patru niveluri: n, equals, 8, comma, 4, comma, 2, comma, 1. Timpul total de execuție pentru mergeSort este, așadar, c, n, left parenthesis, log, start base, 2, end base, n, plus, 1, right parenthesis. Atunci când folosim notația Θ pentru a caracteriza acest timp de execuție, putem renunța la termenul de grad mic (plus, 1) și la coeficientul constant (c), obținând astfel timpul de execuție \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, 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ă a 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.