Divide et impera (informatika)

A számitástechikában a divide et impera (Oszd meg és uralkodj^[1]) egy rekurzión alapuló programozási stratégia, amellyel egy komplex feladatot addig bontunk le részfeladatokra, amíg a részfeladatok megoldása triviális lesz. Használják különböző rendezésekhez (pl. quicksort), nagy számok szorzásánál, vagy diszkrét Fourier transzformációk számításánál.

Részletes leírás

Próbáljuk meg egy konkrét feladattal leírni a divide et impera módszer metodikáját. Tegyük fel, hogy meg kell találnunk egy tömb legnagyobb elemét. Ehhez a legegyszerűbb megoldás az lenne, hogy összehasonlítjuk az első és a második elemet, s amelyik a kettő közül nagyobb, az lesz az ideiglenes maximumunk. Aztán ezt az ideiglenes maximumot hasonlítjuk a tömb többi eleméhez, s természetesen cseréljük, ha találunk nagyobb elemet.

Ha divide et impera módszerrel szeretnénk megoldani, akkor azzal kezdjük a feladatot, hogy felosztjuk a tömböt két egyforma részre, mindkettőnek megkeressük a maximumát, s csak ezt a két maximumot hasonlítjuk össze. Igen ám, de a két féltömböt is feloszthatjuk még két féltömbre (vagyis lesz négy negyedtömbünk) rekurzívan, s ezt egészen addig ismételhetjük, amíg egy tömbrészletben csak egy elem lesz, vagyis triviális lesz, hogy az a maximum. Az alábbi egyszerű C++ programban láthatjuk ennek az implementációját.

#include <iostream>
#include <stdlib.h>

const int n = 10000;
int v[n];

// Divide et Impera módszeren alapuló maximum kereső függvény,
// megkeresi a maximumot a tömbben az argumentumként megadott két index között
int max(int i, int j)
{
    if (i == j) {
        // ha a két index egyezik, akkor már nem lehet tovább bontani a tömböt,
        // tehát ez az érték lesz a maximum
        return v[i];
    } else {
        // ha nem, akkor keresd meg a maximumot a kapott
        // tömb jobb és bal felén s add vissza a nagyobb értéket
        int kozep = (i + j) / 2;
        int max1 = max(i, kozep);
        int max2 = max(kozep + 1, j);
        return max1 > max2 ? max1 : max2;
    }
}


int main()
{
    // feltölti véletlenszámokkal a tömböt
    srand(0);
    for (int i = 0; i < n; i++)
        v[i] = rand();

    // számítsd ki a maximumot a megadott két index között
    int maximum = max(0, n);
    
    std::cout << "max = " << maximum << std::endl;
}