Deli in vladaj (računalništvo)

Za druge pomene glej Deli in vladaj (razločitev).

Deli in vladaj (angleško divide and conquer) predstavlja strategijo delitve problema na manjše probleme, ki so prvotnemu problemu enaki (enakega tipa). Tak postopek ponavljamo, dokler nismo sposobni rešiti podproblemov.

Strategija temelji na rekurziji.

Algoritmi

• dvojiško iskanje
• iskanje mejnih elementov zaporedja
• urejanje z zlivanjem
• hitro urejanje (angleško Quick sort)
• iskanje k-tega elementa po velikosti
• množenje števil
• množenje matrik
• Strassenovo množenje matrik
• Hanojski stolpi
• problem najbližjega para točk

Splošna procedura

// a[dno], a[dno+1], ..., a[vrh]; dno>=1 so podatki
procedure DeliInVladaj(a, dno, vrh, rešitev) 
begin
  if problem majhen (dno, vrh) then
    resi (a, dno, vrh, rešitev)
  else
  begin  // problem ni majhen, potrebna delitev
    s := deli(dno,vrh)    // index delitve, razdeli na 2 podproblema
    DeliInVladaj(a, dno, s, rešitev)     // reši levi podproblem
    DeliInVladaj(a, s+1, vrh, rešitev)   // reši desni podproblem
    Združi(dno, s, vrh, rešitev)         // združi rešitve posameznega podproblema
  end
end