Jakokonkerointi ratkaisee ongelman (1) jakamalla sen pienempiin aliongelmiin, (2) ratkaisemalla jokaisen rekursiivisesti ja (3) yhdistämällä tulokset. Monet tehokkaat algoritmit noudattavat tätä mallia.
Jos aliongelmat ovat riippumattomia ja kutistuvat nopeasti, kokonaistyö noudattaa palautuskaavaa, jonka voit analysoida Master Theoremilla.
def max_dc(arr, lo, hi):
if lo == hi: # base case: one element
return arr[lo]
mid = (lo + hi) // 2
left = max_dc(arr, lo, mid) # conquer left
right = max_dc(arr, mid + 1, hi) # conquer right
return max(left, right) # combine
max_dc([3, 9, 2, 7], 0, 3) # -> 9
Usein T(n) = a·T(n/b) + f(n); merge sortin tapauksessa T(n) = 2T(n/2) + O(n) = O(n log n).
Käytä, kun ongelma jakaantuu selkeästi itsenäisiin aliongelmiin. Jos aliongelmat päällekkäin, suosi sen sijaan dynaamista ohjelmointia (uudelleenlaskennan välttämiseksi). Rekursion yleiskustannukset ja yhdistymisvaihe voivat hallita pienillä syötteillä.
Jakokonkerointi on uudelleenkäytettävä mallipohja useiden tehokkaiksi algoritmien taakse.
Kuvion tunnistaminen antaa sinulle mahdollisuuden johtaa ja analysoida uusia algoritmeja nopeasti palautuskaavoja käyttäen.
Se myös kuvautuu luonnollisesti rinnakkaisuuteen, koska itsenäiset aliongelmat voivat toimia samanaikaisesti.