Ebben az oktatóanyagban megtudhatja, hogyan működik az osztás és meghódítás algoritmus. Összehasonlítjuk a megosztási és a hódítási megközelítést a rekurzív probléma megoldásának más megközelítéseivel is.
A Divide and Conquer algoritmus egy nagy probléma megoldásának stratégiája
- a problémát kisebb részproblémákra bontva
- az alproblémák megoldása, és
- kombinálva őket a kívánt eredmény eléréséhez.
Az osztás és meghódítás algoritmus használatához rekurziót használunk. Tudjon meg többet a rekurzióról a különböző programozási nyelveken:
- Rekurzió Java-ban
- Rekurzió Pythonban
- Rekurzió C ++ nyelven
Hogyan működnek az algoritmusok megosztása és meghódítása?
Itt vannak az érintett lépések:
- Osztás : Az adott problémát rekurzióval részproblémákra oszthatja.
- Hódítás : Rekurzív módon oldja meg a kisebb részfeladatokat. Ha az alprobléma elég kicsi, akkor oldja meg közvetlenül.
- Kombinálás: Kombinálja a rekurzív folyamat részét képező részproblémák megoldásait a tényleges probléma megoldásához.
Értsük meg ezt a koncepciót egy példa segítségével.
Itt rendezni fogunk egy tömböt a divide and conquer megközelítés (azaz egyesítés rendezés) segítségével.
- Legyen az adott tömb:
Tömb az egyesítés rendezéséhez - Osszuk a tömböt két félre.
Osszuk el a tömböt két részre
Ismét, osszuk meg az egyes részeket rekurzívan két félre, amíg meg nem kapjuk az egyes elemeket.
Osszuk a tömböt kisebb részekre - Most egyesítse az egyes elemeket rendezve. Itt a hódítás és a kombinálás lépései egymás mellett haladnak.
Kombinálja az alrészeket
Az idő komplexitása
Az osztás és meghódítás algoritmus bonyolultságát a főtétel segítségével számítják ki.
T (n) = aT (n / b) + f (n), ahol, n = a bemenet mérete a = a rekurziós részproblémák száma n / b = az egyes részproblémák mérete. Feltételezzük, hogy az összes részprobléma azonos méretű. f (n) = a rekurzív híváson kívül végzett munka költsége, amely magában foglalja a probléma felosztásának költségét és a megoldások összevonásának költségeit
Vegyünk egy példát a rekurzív probléma időbeli összetettségének megállapítására.
Egyesítési fajta esetén az egyenlet a következőképpen írható fel:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) ahol a = 2 (minden alkalommal egy probléma 2 részproblémára oszlik) n / b = n / 2 (az egyes részfeladatok mérete a bemenet fele) f (n) = a probléma felosztásához és az alproblémák összevonásához szükséges idő T (n / 2) = O (n log n) (Ennek megértéséhez kérjük, olvassa el a törzstétel.) Most T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs Dynamic megközelítés
Az „oszd meg és hódítsd” megközelítés egy problémát kisebb részproblémákra oszt; ezek az alproblémák rekurzív módon tovább oldódnak. Az egyes részproblémák eredményét nem tároljuk későbbi felhasználás céljából, míg egy dinamikus megközelítésben az egyes részproblémák eredményét a későbbi hivatkozások céljából tároljuk.
Használja a divide and conquer megközelítést, ha ugyanaz a részprobléma nem oldódik meg többször. Használja a dinamikus megközelítést, ha egy részprobléma eredményét a jövőben többször kell használni.
Értsük meg ezt egy példával. Tegyük fel, hogy megpróbáljuk megtalálni a Fibonacci sorozatot. Azután,
Divide and Conquer megközelítés:
fib (n) Ha n <2, adjon vissza 1-et, adjon vissza f (n - 1) + f (n -2)
Dinamikus megközelítés:
mem = () fib (n) Ha n a mem-ben: adja vissza a mem (n) else-t, Ha n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f visszatérés f
Dinamikus megközelítésben a mem tárolja az egyes részproblémák eredményét.
A Divide and Conquer Algorithm előnyei
- Két mátrix naiv módszerrel történő szorzásának bonyolultsága O (n 3 ), míg az osztás és meghódítás megközelítést (azaz Strassen mátrix szorzását) O (n 2,8074 ). Ez a megközelítés más problémákat is leegyszerűsít, például a Hanoi-tornyot.
- Ez a megközelítés alkalmas többprocesszoros rendszereknél.
- Hatékonyan használja a memória gyorsítótárakat.
Divide and Conquer Applications
- Bináris keresés
- Egyesítés rendezés
- Gyors rendezés
- Strassen Matrix szorzata
- Karatsuba algoritmus
