Divide and conquer husoma tatizo kwa (1) kugawanya katika tatizo ndogo, (2) kushinda kila moja kwa njia ya kurudia, na (3) kuchanganya matokeo. Algorithms nyingi zenye ufanisi zinafuata muundo huu.
Kama tatizo ndogo zina uhuru na zinakula haraka, kazi ya jumla inafuata muundo wa kurudia ambao unaweza kuchambua kwa 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
Mara nyingi T(n) = a·T(n/b) + f(n); kwa merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Tumia wakati tatizo linagawanywa vizuri katika tatizo ndogo lenye uhuru. Ikiwa tatizo ndogo linaingiliana, pendelea dynamic programming badala yake (kuepuka kuhesabu tena). Kukamatia kwa kurudia na hatua ya kuchanganya inaweza kuwa nyingi kwa ingizo ndogo.
Divide and conquer ni mpango wa kubadilika unaonacho katika sehemu kubwa ya algorithms zenye ufanisi.
Kutambua muundo hukuruhusu kuhanga na kuchambua algorithms mpya haraka kwa muundo wa kurudia.
Inakamatia kwa asili kwenye parallelism, kwa sababu tatizo ndogo lenye uhuru linaweza kukimbia kwa sambamba.
Maktaba ya maswali ya mahojiano ya IT yenye majibu ya kina — kutoka Junior hadi Senior.
Changia