A számítástechnika , oszd meg és uralkodj (a latin „ Divide ut imperes ” , oszd meg és uralkodj angolul) egy algoritmikus módszer a következőkből áll:
Ez a technika hatékony algoritmusokat kínál számos problémára, például egy elem megkeresésére egy rendezett tömbben ( bináris keresés ), válogatásra ( egyesítés rendezése , gyors rendezés ), nagy számok elterjedésére ( Karatsuba algoritmus ) vagy transzformációra Diszkrét Fourier ( gyors Fourier transzformáció ) .
Az alábbi táblázat példákat mutat be a három lépés (osztás, szabály, kombinálás) algoritmusokra.
Elosztani, megosztani | Uralkodni | Kombájn | |
---|---|---|---|
Dichotóm keresés | Az x keresése a T [1, .. n] rendezett tömbben,
|
- | - |
Egyesítés rendezése | a rendezni kívánt T [1, .. n] tömböt két T [1, .. n / 2] és T [n / 2 +1, .. n] tömbre osztjuk | válogatjuk a két T [1, .. n / 2] és T [n / 2 +1, .. n] tömböt (rekurzívan, vagy nem csinálunk semmit, ha 1-es méretűek) | kiszámítjuk a kezdeti tömb rendezett permutációját a két rendezett T [1, .. n / 2] és T [n / 2 +1, .. n] tömb összevonásával. |
Gyors rendezés | a tömbből véletlenszerűen választunk egy elemet, amely „pivot” lesz, és az összes elemet átitatjuk úgy, hogy a forgás bal oldalán elhelyezzük azokat az elemeket, amelyek alacsonyabbak, és jobb oldalon azokat, amelyek felette vannak. | a két fél a forgás mindkét oldalán rendezve van. | - |
Itt vannak más példák a megosztani és meghódítani algoritmusokra :
A dichotóm kutatásokat John Mauchly 1946-ban megjelent cikke formalizálja , de a kutatás megkönnyítésére egy válogatott lista felhasználásának ötlete Babilonba nyúlik vissza -220-ban. A két szám legnagyobb közös osztójának kiszámítására szolgáló euklideszi algoritmus osztás és meghódítás algoritmusnak tekinthető (mindkét szám csökken, az egyik pedig kisebb problémára redukálódik). Gauss leírja a gyors Fourier-transzformációt 1805-ben anélkül, hogy elvégezné a bonyolultsági elemzést. A gyors Fourier-átalakulást egy évszázaddal később fedezik fel újra.
John von Neumann 1945- ben találta fel a fúziós válogatást . A Karatsuba algoritmust Anatolii A. Karatsuba találta ki 1960-ban: ez két számjegyű n számjegyet szoroz meg a műveletek során (lásd Landau jelölések ). Ez az algoritmus ellentmond Andrei Kolmogorov 1956-os sejtésének, amely szerint a műveletekre szükség van. Knuth megadja a postai szolgáltatások által használt módszert : a leveleket földrajzi területek szerint rendezik és szétválasztják, majd földrajzi területekre stb. Ez a rendezés a radix-rendezés , amelyet az IBM kártyagépek ( IBM card sortter (en) ) írtak le 1929-től.
A divide and conquer algoritmusok alacsony bonyolultsága az egyik fő érdeklődésük. Számos tétel létezik, amelyek megkönnyítik az osztódás és meghódítás algoritmusok bonyolultságának kiszámítását . A fő tétel a Mester tétel . Összetettebb esetekre hivatkozhatunk az Akra-Bazzi tételre . Az alábbi táblázat összehasonlítja a naiv algoritmus bonyolultságát és az osztás és meghódítás algoritmust egyes problémákkal (lásd: Landau-jelölések ):
Komplexitás a naiv algoritmussal | Komplexitás a divide and conquer algoritmussal | |
---|---|---|
Keresés n méret szerinti rendezett tömbben | Mi) | O (log n) |
N elem tömbjének rendezése | O (n²) (lásd válogatás beillesztése , válogatás kiválasztása ) | O (n log n) az egyesítés rendezésével
O (n log n) átlagosan gyors rendezéssel |
Két szám szorzata n számjeggyel | O (n²) | a Karatsuba algoritmussal |
A Divide and Conquer algoritmusokat gyakran úgy alkalmazzák, hogy több processzorral rendelkező gépeken fussanak.
Vannak áramkörök fix méretű bemenetekhez a gyors Fourier-transzformációhoz . Rendelkeznek fúziós válogatáshoz rendezési hálózatokkal is , az úgynevezett bitonikus rendezéssel .
Oszd és hódítsd meg az algoritmusokat természetesen rekurzív írásnak vetik alá . De néha a rekurzív algoritmusok futtatása halom túlcsorduláshoz vezethet . Ezért néha inkább egy iteratív algoritmust preferálunk.
Az „oszd meg és hódítsd” alkalmazásakor nincs redundancia: a rekurzív hívások során minden egyes problémát csak egyszer oldanak meg. Másrészt, ha az alproblémák feleslegesek, az „oszd meg és hódítsd” módszerrel kapott rekurzív algoritmusnak rossz összetettsége lehet. Vegyünk példát a Fibonacci-szekvencia n- edik számának kiszámítására . A következő algoritmus exponenciális időben van n-ben:
fonction fibonacci(n) si(n = 0 ou n = 1) renvoyer 1 sinon renvoyer fibonacci(n-1) + fibonacci(n-2)Ennek a határnak a túllépése érdekében megjegyezheti a már kiszámított értékeket, hogy elkerülje a már felmerült részproblémák megoldását. Ez a memorizálás ( dinamikus programozásnál is használják ).