Mik a Divide and Conquer algoritmusok? (És nem, ez nem "Oszd meg és értsd")
A Divide and Conquer egy algoritmikus paradigma (amelyet néha tévesen "Divide and Concur" -nak hívnak - vicces és találó név), hasonló a Kapzsi és a Dinamikus Programozáshoz. Egy tipikus Divide and Conquer algoritmus a következő három lépés segítségével oldja meg a problémát.
- Osztás : Szüntesse meg az adott problémát azonos típusú részproblémákra. Ebben a lépésben a problémát kisebb részproblémákra kell bontani. Az alproblémáknak az eredeti probléma részét kell képezniük. Ez a lépés általában rekurzív megközelítést alkalmaz a probléma felosztására, amíg egyetlen részprobléma sem osztható tovább. Ebben a szakaszban az alproblémák atom jellegűvé válnak, de mégis a tényleges probléma bizonyos részét képviselik.
- Hódítás : Rekurzív módon oldja meg ezeket az alproblémákat. Ez a lépés rengeteg kisebb megoldandó részproblémát kap. Általában ezen a szinten a problémákat önmagukban „megoldottnak” tekintik.
- Összevonás : A válaszok megfelelő kombinálása. Amikor a kisebb részfeladatok megoldódnak, ez a szakasz rekurzívan kombinálja őket, amíg meg nem fogalmazzák az eredeti probléma megoldását. Ez az algoritmikus megközelítés rekurzívan működik, a hódító és egyesítő lépések pedig olyan közel működnek, hogy egyként jelennek meg.
Ez a módszer általában lehetővé teszi számunkra az idő bonyolultságának nagymértékű csökkentését.
Például a Bubble Sort bonyolultságot használ O(n^2), míg a quicksort (a Divide And Conquer alkalmazás) csökkenti az idő bonyolultságát O(nlog(n)). A lineáris keresés időbonyolult O(n), míg a bináris keresés (a Divide And Conquer alkalmazás) csökkenti az idő komplexitását O(log(n)).
Az alábbiakban bemutatunk néhány standard algoritmust, amelyek a Divide and Conquer algoritmusok fajtájába tartoznak.
A bináris keresés egy kereső algoritmus. Minden lépésben az algoritmus összehasonlítja a bemeneti elemet (x) a tömb középső elemének értékével. Ha az értékek egyeznek, adja vissza a középső indexet. Egyébként, ha x kisebb, mint a középső elem, akkor az algoritmus visszatér a középső elem bal oldalára, máskülönben a középső elem jobb oldalára.
A Quicksort egy rendezési algoritmus. Az algoritmus kiválaszt egy forgó elemet, átrendezi a tömb elemeket úgy, hogy az összes, a kiválasztott forgó elemnél kisebb elem a bal oldalra, az összes nagyobb elem pedig a jobb oldalra kerüljön. Végül az algoritmus rekurzívan rendezi az alsávokat a forgatóelem bal és jobb oldalán.
A Rendezés egyesítése szintén rendezési algoritmus. Az algoritmus két töredékre osztja a tömböt, rekurzívan rendezi őket, végül egyesíti a két rendezett felet. Ennek az algoritmusnak az időbeli összetettsége a O(nLogn)legjobb, átlagos vagy a legrosszabb eset. Itt az ideje, összetettsége könnyen megérthető a kiújulás nagyjából: T(n) = 2T(n/2) + n.
A legközelebbi pontpár A probléma az, hogy megtalálja a xy síkban lévő ponthalmaz legközelebbi pontpárját. A probléma O(n^2)időben megoldható úgy, hogy kiszámítja az egyes pontpárok távolságát, és összehasonlítja a távolságokat, hogy megtalálja a minimumot. A Divide and Conquer algoritmus O(nLogn)időben megoldja a problémát .
Strassen algoritmusa hatékony algoritmus két mátrix szorzására. Két mátrix szorzásának egyszerű módszeréhez 3 egymásba ágyazott hurok szükséges O(n^3). Strassen algoritmusa két mátrixot szoroz meg O(n^2.8974)időben.
A Cooley – Tukey Fast Fourier Transform (FFT) algoritmus a leggyakoribb algoritmus az FFT számára. Ez egy megosztani és meghódítani algoritmus, amely O(nlogn)időben működik .
A Karatsuba algoritmus volt az első szorzási algoritmus, amely aszimptotikusan gyorsabb, mint a másodfokú "évfolyam iskolai" algoritmus. Csökkenti a két n-jegyű szám szorzását legfeljebb n ^ 1,585-re (ami a logaritmus közelítése a 2. alapban) egyjegyű szorzatokra. Ezért gyorsabb, mint a klasszikus algoritmus, amely n ^ 2 egyjegyű terméket igényel.
Divide and Conquer (D & C) vs dinamikus programozás (DP)
Mindkét paradigma (D & C és DP) felosztja az adott problémát részproblémákra és megoldja a részproblémákat. Hogyan válasszuk ki közülük az adott problémát? A Divide and Conquer lehetőséget akkor kell használni, ha ugyanazokat a részproblémákat nem sokszor értékelik. Ellenkező esetben dinamikus programozást vagy memóriát kell használni.
Például a bináris keresés egy Divide and Conquer algoritmus, soha többé nem értékeljük ugyanazokat az alproblémákat. Másrészt az n-edik Fibonacci szám kiszámításához a dinamikus programozást kell előnyben részesíteni.