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(n^2)$\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(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis timp în toate cazurile, iar sortarea rapidă se execută în $\Theta(n \lg 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(n^2)$\Theta, left parenthesis, n, squared, right parenthesis timp. Iată un tabel cu acești patru algoritmi de sortare și timpii lor de execuție:

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:

Îț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.