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 $\mathrm{\Theta }(n^2)$‍. 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 $\mathrm{\Theta }(n\lg n)$‍ timp în toate cazurile, iar sortarea rapidă se execută în $\mathrm{\Theta }(n\lg n)$‍ timp în cel mai bun caz și în cazul mediu, iar în cazul cel mai nefavorabil se execută în $\mathrm{\Theta }(n^2)$‍ 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 recurență. Această paradigmă, divide et impera, descompune o problemă în subprobleme asemănătoare cu problema inițială, rezolvă recursiv subproblemele, apoi combină 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 elementar (de bază, direct rezolvabil) 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ă, combină. 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ă subprobleme):

Dacă facem încă două apeluri recursive, schema algoritmului arată după cum urmează:

Deoarece divide et impera creează cel puțin două subprobleme, un algoritm 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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.