Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Expresia provine din latină unde exista și ca proverb: „Divide et impera”. În română este mai cunoscut ca: „divide și cucerește”
- In domeniul informaticii,Divide et impera este o clasă de algoritmi care funcționează pe baza tacticii "divide et impera"
- Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
- Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.
- Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:
- 1.s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
- 2.nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
- O descriere a tehnicii D&I: “Divide and Conquer algorithms break the problem into several sub-problems that are similar to the original problem but smaller in size, solve the sub-problems recursively, and then combine these solutions to create a solution to the original problem.” [7]
- Deci un algoritm D&I împarte problema în mai multe subprobleme similare cu problema inițială şi de dimensiuni mai mici, rezolva sub-problemele recursiv şi apoi combina soluțiile obţinute pentru a obține soluția problemei inițiale.
- Sunt trei pași pentru aplicarea algoritmului D&I:
- Divide: împarte problema în una sau mai multe probleme similare de dimensiuni mai mici.
- Impera (stăpânește): rezolva subprobleme recursiv; dacă dimensiunea sub-problemelor este mica se rezolva iterativ.
- Combină: combină soluțiile sub-problemelor pentru a obține soluția problemei inițiale.
- Complexitatea algoritmului este dată de formula: T(n)=D(n)+S(n)+C(n), unde D(n)=O(1), S(n)=2∗T(n/2) și C(n)=O(n), rezulta T(n)=2∗T(n/2)+O(n).
- Folosind teorema Master [8] găsim complexitatea algoritmului: T(n)=O(n∗log(n)).
- /////////complexitate temporala : T=O(n∗log(n))
- Ce inseamna aceasta metrica? Masoara efectiv timpul de executie al algoritmului (nu include citiri, afisari etc).
- complexitate spatiala : S=O(n)
- Ce inseamna aceasta metrica? Masoara efectiv memoria suplimentara folosita de algoritm (in acest caz ne referim strict la buffer-ul temporar).
- Tipruri de algoritmi
- Turnurile din Hanoi
- Cautare Binara
- MergeSort
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement