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

Algoritmi Divide-et-Impera

Cei doi algoritmi de sortare pe care i-am studiat până acum, sortarea prin selecție și sortarea prin inserție, au timpul de execuție în cazul cel mai nefavorabil egal cu \Theta, left parenthesis, n, squared, right parenthesis. Atunci când dimensiunea vectorului de intrare este mare, acești algoritmi se execută mai lent. În acest tutorial și în următorul vom vedea alți doi algoritmi de sortare, sortarea prin interclasare și sortarea rapidă, ai căror timpi de execuție sunt mai buni. Concret, sortarea prin interclasare se execută în \Theta, left parenthesis, n, \lg, n, right parenthesis timp în toate cazurile, iar sortarea rapidă se execută în \Theta, left parenthesis, n, \lg, n, right parenthesis timp în cel mai bun caz și în cazul mediu, iar în cazul cel mai nefavorabil se execută în \Theta, left parenthesis, n, squared, right parenthesis timp. Iată un tabel cu acești patru algoritmi de sortare și timpii lor de execuție:
AlgoritmTimpul de execuție în cazul cel mai nefavorabilTimpul de execuție în cazul cel mai favorabilTimpul de execuție în cazul mediu
Sortare prin selecție\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis
Sotare prin inserție\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis
Sortare prin interclasare\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis
Sortare rapidă\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis

Divide et Impera

Atât sortarea prin interclasare, cât și sortarea rapidă folosesc o paradigmă de proiectare a algoritmilor bazată pe recursie. Această paradigmă, divide et impera, descompune o problemă în subprobleme asemănătoare cu problema inițială, rezolvă recursiv subproblemele, apoi asamblează soluțiile subproblemelor pentru a rezolva problema inițială. Deoarece divide et impera rezolvă subprobleme recursiv, fiecare subproblemă trebuie să aibă dimensiuni mai mici decât problema inițială și trebuie să existe un caz de bază pentru subprobleme. Te poți gândi că un algoritm divide et impera are trei etape:
  1. Divide problema într-o serie de subprobleme de dimensiune mai mică decât problema inițială.
  2. Rezolvă subproblemele recursiv. Dacă au dimensiunea suficient de mică, subproblemele sunt chiar cazurile de bază.
  3. Asamblează soluțiile subproblemelor pentru a obține soluția problemei inițiale.
Îți poți aminti cu ușurință etapele unui algoritm divide et impera ca fiind divide, rezolvă, asamblează. Iată cum arată un pas al algoritmului, presupunând că fiecare etapă care divide creează două subprobleme (deși există algoritmi divide et impera care creează mai mult de două):
Dacă facem încă două apeluri recursive, schema algoritmului arată după cum urmează:
Deoarece divide et impera creează cel puțin două subprobleme, un algorim divide et impera face numeroase apeluri recursive.

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.