Oszd meg és hódítsd meg az algoritmust

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 ³ ), 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.