Algoritmi → Napredne tehnike → Podeli pa vladaj

Podeli pa vladaj

Tri koraka

Složenost zavisi od broja delova, njihove veličine i cene spajanja:

Dobitak dolazi od toga što se problem deli na jednake delove: tada je nivoa rekurzije samo log₂ n.

Primer: brzo stepenovanje

aⁿ = (an/2)² za parno n i a · an−1 za neparno. Svaki korak prepolovi izložilac – O(log n) množenja umesto n.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long stepen(long long a, long long n) {
    if (n == 0) return 1;                     // a^0 = 1
    long long p = stepen(a, n / 2);           // reši problem pola veličine (jednom!)
    p = p * p % MOD;                          // spoji
    if (n % 2 == 1) p = p * a % MOD;          // neparan izložilac
    return p;
}

int main() {
    long long a, n;
    cin >> a >> n;
    cout << stepen(a % MOD, n) << endl;
    return 0;
}

Važno je da se stepen(a, n / 2) pozove jednom i sačuva; dva poziva bi vratila složenost na O(n). Detaljnije u lekciji Algoritam brzog stepenovanja.

Primer: najveći zbir uzastopnog dela

Najbolji deo niza je ili ceo u levoj polovini, ili ceo u desnoj, ili prelazi preko sredine. Prva dva slučaja rešava rekurzija, a treći – najbolji sufiks leve i najbolji prefiks desne polovine – u O(n). Ukupno O(n log n).

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

vector<long long> a;

long long najbolji(int l, int d) {
    if (l == d) return a[l];                         // jedan element
    int m = (l + d) / 2;
    long long levo = najbolji(l, m), desno = najbolji(m + 1, d);
    // deo koji prelazi sredinu: najbolji sufiks levo + najbolji prefiks desno
    long long s = 0, bestL = LLONG_MIN;
    for (int i = m; i >= l; i--) { s += a[i]; bestL = max(bestL, s); }
    s = 0;
    long long bestD = LLONG_MIN;
    for (int i = m + 1; i <= d; i++) { s += a[i]; bestD = max(bestD, s); }
    return max({levo, desno, bestL + bestD});
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    for (auto &x : a) cin >> x;
    cout << najbolji(0, n - 1) << endl;
    return 0;
}

Za ovaj problem postoji i rešenje O(n) – Kadaneov algoritam, ali „podeli pa vladaj“ verzija pokazuje opšti obrazac: šta prelazi preko granice delova, to se računa pri spajanju.

Gde se još koristi

• Sortiranje objedinjavanjem i brojanje inverzija;
• brzo sortiranje i k-ti najmanji element;
• binarna pretraga i binarna pretraga po rešenju;
• segmentno stablo – svaki čvor čuva rezultat za svoj interval i spaja rezultate dece;
• Hanojske kule.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje