Divide and conquer løser et problem ved å (1) dele det i mindre delproblemer, (2) erobre hver enkelt rekursivt, og (3) kombinere resultatene. Mange effektive algoritmer følger denne malen.
Hvis delproblemer er uavhengige og krymper raskt, følger det totale arbeidet en gjentakelse som du kan analysere med Master Theorem.
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
Oftest T(n) = a·T(n/b) + f(n); for merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Bruk når et problem splitter rent inn i uavhengige delproblemer. Hvis delproblemer overlapper, foretrekk dynamic programming i stedet (for å unngå omberegning). Rekursjonsoverhead og kombinasjonstrinnet kan dominere for små innganger.
Divide and conquer er en gjenbrukbar mal bak en stor del av effektive algoritmer.
Å kjenne igjen mønsteret lar deg utlede og analysere nye algoritmer raskt med gjentakelser.
Det kartlegges også naturlig til parallellisme, siden uavhengige delproblemer kan kjøre samtidig.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner