În acest tutorial, veți afla cum funcționează algoritmul de divizare și cucerire. De asemenea, vom compara abordarea divizării și cuceririi versus alte abordări pentru a rezolva o problemă recursivă.
Un algoritm de divizare și cucerire este o strategie de rezolvare a unei mari probleme prin
- descompunerea problemei în subprobleme mai mici
- rezolvarea subproblemelor și
- combinându-le pentru a obține rezultatul dorit.
Pentru a utiliza algoritmul de divizare și cucerire, se folosește recursivitatea . Aflați despre recursivitate în diferite limbaje de programare:
- Recursivitate în Java
- Recursivitate în Python
- Recursivitate în C ++
Cum funcționează algoritmii de împărțire și cucerire?
Iată pașii implicați:
- Împărțiți : împărțiți problema dată în subprobleme folosind recursivitatea.
- Cuceriți : rezolvați recursiv problemele secundare mai mici. Dacă subproblema este suficient de mică, atunci rezolvați-o direct.
- Combinați: combinați soluțiile subproblemelor care fac parte din procesul recursiv pentru a rezolva problema reală.
Să înțelegem acest concept cu ajutorul unui exemplu.
Aici, vom sorta o matrice folosind abordarea divide and conquer (de exemplu, merge sort).
- Fie matricea dată:
Array pentru sortare de îmbinare - Împărțiți matricea în două jumătăți.
Împărțiți matricea în două subparti
Din nou, împărțiți fiecare subpartea recursiv în două jumătăți până când obțineți elemente individuale.
Împărțiți matricea în sub-părți mai mici - Acum, combinați elementele individuale într-un mod sortat. Aici, cuceriți și combinați pașii merg unul lângă altul.
Combinați părțile secundare
Complexitatea timpului
Complexitatea algoritmului de divizare și cucerire este calculată folosind teorema master.
T (n) = aT (n / b) + f (n), unde, n = dimensiunea intrării a = numărul de subprobleme din recursivitate n / b = dimensiunea fiecărei subprobleme. Se presupune că toate subproblemele au aceeași dimensiune. f (n) = costul muncii efectuate în afara apelului recursiv, care include costul împărțirii problemei și costul fuzionării soluțiilor
Să luăm un exemplu pentru a găsi complexitatea în timp a unei probleme recursive.
Pentru un sortare de fuziune, ecuația poate fi scrisă ca:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Unde, a = 2 (de fiecare dată, o problemă este împărțită în 2 subprobleme) n / b = n / 2 (dimensiunea fiecărei subprobleme este jumătate din intrare) f (n) = timpul necesar divizării problemei și fuzionării subproblemelor T (n / 2) = O (n log n) (Pentru a înțelege acest lucru, vă rugăm să consultați teorema maestrului.) Acum, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Împărțiți și cuceriți abordarea dinamică
Abordarea divizează și cucerește împarte o problemă în subprobleme mai mici; aceste subprobleme sunt rezolvate în continuare recursiv. Rezultatul fiecărei subprobleme nu este stocat pentru referință viitoare, în timp ce, într-o abordare dinamică, rezultatul fiecărei subprobleme este stocat pentru referință viitoare.
Utilizați abordarea divizare și cucerire atunci când aceeași subproblemă nu este rezolvată de mai multe ori. Utilizați abordarea dinamică atunci când rezultatul unei subprobleme va fi utilizat de mai multe ori în viitor.
Să înțelegem acest lucru cu un exemplu. Să presupunem că încercăm să găsim seria Fibonacci. Apoi,
Abordarea divizează și cucerește:
fib (n) Dacă n <2, returnează 1 Altfel, returnează f (n - 1) + f (n -2)
Abordare dinamică:
mem = () fib (n) Dacă n în mem: returnează mem (n) altfel, Dacă n <2, f = 1 altul, f = f (n - 1) + f (n -2) mem (n) = f întoarcere f
Într-o abordare dinamică, mem stochează rezultatul fiecărei subprobleme.
Avantajele algoritmului Divide and Conquer
- Complexitatea pentru înmulțirea a două matrice folosind metoda naivă este O (n 3 ), în timp ce utilizarea abordării de divizare și cucerire (adică înmulțirea matricei lui Strassen) este O (n 2.8074 ). Această abordare simplifică și alte probleme, precum Turnul din Hanoi.
- Această abordare este potrivită pentru sistemele multiprocesare.
- Utilizează în mod eficient cache-urile de memorie.
Împărțiți și cuceriți aplicațiile
- Căutare binară
- Merge Sort
- Sortare rapida
- Înmulțirea matricei lui Strassen
- Algoritmul Karatsuba
