Podeli-pa-vladaj (Divide & Conquer)

Metodologija podeli pa vladaj (eng. divide and conquer) predstavlja jednu od najvažnijih paradigma u savremenim algoritmima. Ideja je da se veliki problem podeli na manje podproblemske jedinice, zatim se svaki od njih reši nezavisno, a potom se rešenja kombinuju u konačno rešenje.

Ova tehnika se najviše koristi kada je moguće:

• problem jasno podeliti na manje iste ili slične podprobleme
• smanjiti veličinu problema u svakoj iteraciji (n → n/2 ili slična redukcija)
• jednostavno spojiti rezultate podproblema

Neki od najpoznatijih algoritama koji koriste ovu paradigmu su: Merge Sort, Quick Sort, Binary Search, Strassenovo množenje matrica, FFT i mnogi drugi.

Osnovna ideja paradigme

Algoritam se sastoji od tri osnovna koraka:

• Podeli: problem se deli na manje delove
• Reši: svaki podproblem se rešava (često rekurzivno)
• Spoji: rešenja podproblema se kombinuju

Ovi koraci se često prikazuju formulom:

T(n) = a · T(n/b) + f(n)

Gde:

• a = broj podproblema
• b = faktor smanjenja veličine problema u svakom koraku
• f(n) = trošak spajanja rešenja podproblema

Ovakve relacije rešavamo Master Teoremom (kasnije posebna lekcija).

Primer: Binarna pretraga (Binary Search)

Binarna pretraga je najjednostavniji primer primene D&C pristupa. Ako je niz sortiran, reklišemo polovinu niza u jednom koraku.

Pravila:

• ako je tražena vrednost manja od srednjeg elementa → pretražujemo levi deo
• ako je veća → pretražujemo desni deo
• ako je jednaka → našli smo element

int binarySearch(int a[], int l, int r, int x) {
    if (l > r) return -1;
    int mid = (l + r) / 2;

    if (a[mid] == x) return mid;
    if (x < a[mid])
        return binarySearch(a, l, mid - 1, x);
    else
        return binarySearch(a, mid + 1, r, x);
}

Vremenska složenost: O(log n) Prostorna složenost: O(log n) zbog rekurzije

Primer: Merge Sort

Merge Sort je jedan od najpoznatijih algoritama koji ilustruje moć ove paradigme. Algoritam sortira tako što:

1. podeli niz na dva jednaka dela
2. rekurzivno sortira svaki deo
3. spaja (merge) dve sortirane polovine

void mergeSort(vector &a) {
    if (a.size() <= 1) return;

    int mid = a.size() / 2;
    vector left(a.begin(), a.begin() + mid);
    vector right(a.begin() + mid, a.end());

    mergeSort(left);
    mergeSort(right);

    int i = 0, j = 0, k = 0;
    while (i < (int)left.size() && j < (int)right.size()) {
        if (left[i] < right[j]) a[k++] = left[i++];
        else a[k++] = right[j++];
    }
    while (i < (int)left.size()) a[k++] = left[i++];
    while (j < (int)right.size()) a[k++] = right[j++];
}

Vremenska složenost: O(n log n)
Prostorna složenost: O(n)

Kompleksnost i Master Teorem (kratko)

Ako je algoritam opisan relacijom:

T(n) = aT(n/b) + f(n)

onda koristimo sledeća pravila:

• Ako je f(n) manja od n^(log_b(a)) → vreme je O(n^(log_b(a)))
• Ako je f(n) jednaka → O(n^(log_b(a)) · log n)
• Ako je f(n) veća → O(f(n))

→ Detaljna lekcija o Master Teoremu će biti dostupna posebno.

Zadaci za vežbu

Probaj da rešiš sledeće zadatke koristeći D&C pristup:

Zadatak 1:

Napiši funkciju koja nalazi maksimalni element u nizu koristeći rekurziju i pristup podeli pa vladaj.

Zadatak 2:

Implementirati algoritam za pronalaženje najveće sume podniza (Maximum Subarray) koristeći D&C pristup.

Zadatak 3:

Pronađi koliko puta se element x pojavljuje u sortiranom nizu koristeći binarnu pretragu (varijanta: nađi krajnje indekse).

Zaključak

Paradigma Podeli pa vladaj je temelj mnogih naprednih algoritama. Korišćenjem jasne strukture podeli → reši → spoji postiže se efikasnost, posebno u slučajevima kada je moguća logaritamska redukcija problema.

Preporučena naredna lekcija: □ Gramzivi algoritmi (Greedy)