Taqsim u ikkunssta issolvi problema billi (1) taqsammha f'sub-problemi iżgħar, (2) tikkunsstahhom kull wieħed b'mod rikursiv, u (3) tgħaqqadha r-riżultati. Ħafna algoritmi effiċjenti jsegwu dan it-template.
If sub-problemi huma indipendenti u jaqgħu malajr, ix-xogħol totali isegwi rikorrenza li tista' tanalizza bit-Teorema ta' Master.
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
Spiss T(n) = a·T(n/b) + f(n); għal merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Uża meta problema tinqasam b'mod ċar f'sub-problemi indipendenti. Jekk sub-problemi joħxdu, prefer il-programmazzjoni dinamika minflok (biex tiġib il-kalkolu mill-ġdid). L-overhead tal-rikursjoni u l-pass tal-magħluq jistgħu jiddomoraw għal inputs żgħar.
Taqsim u ikkunssta hija blueprint li tista' tintuża mill-ġdid wara frazzjoni kbira ta' algoritmi effiċjenti.
Il-ħsieb tal-pattern iletin tiddividi u tanalizza algoritmi ġodda b'aħfef bit-rikorrenze.
Ihidden jinqasmu naturalment għall-paralleliżmu, billi sub-problemi indipendenti jistgħu jaħdmu flimkien.
Librerija ta' mistoqsijiet ta' intervisti tal-IT b'tweġibiet dettaljati — minn Junior sa Senior.
Iddona