1 Tehnica divide et impera
Divide
et impera este o tehnica de elaborare a
algoritmilor care consta in:
Descompunerea cazului ce trebuie
rezolvat intr-un numar de subcazuri mai mici ale aceleiasi probleme.
Rezolvarea succesiva si independenta
a fiecaruia din aceste subcazuri.
Recompunerea subsolutiilor astfel
obtinute pentru a gasi solutia cazului initial.
Sa presupunem ca avem un algoritm A cu timp patratic. Fie c o
constanta, astfel incat timpul pentru a rezolva un caz de marime n este
tA(n) cn2.
Sa presupunem ca este posibil sa rezolvam un astfel de caz prin descompunerea
in trei subcazuri, fiecare de marime n/2.
Fie d o constanta, astfel incat timpul necesar pentru descompunere si
recompunere este t(n) dn.
Folosind vechiul algoritm si ideea de descompunere-recompunere a subcazurilor,
obtinem un nou algoritm B, pentru care:
