Rozděl a panuj řeší problém pomocí (1) rozdělení na menší podproblémy, (2) řešení každého rekurzivně a (3) kombinování výsledků. Mnoho efektivních algoritmů následuje tuto šablonu.
Pokud jsou podproblémy nezávislé a rychle se zmenšují, celková práce následuje relaci, kterou můžete analyzovat pomocí Master Theoremu.
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
Často T(n) = a·T(n/b) + f(n); pro merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Využijte, když se problém čistě dělí na nezávislé podproblémy. Pokud se podproblémy překrývají, raději zvolte dynamické programování (aby se zabránilo opakovanému výpočtu). Režie rekurze a krok kombinování mohou dominovat pro malé vstupy.
Rozděl a panuj je opakovaně použitelná šablona za obrovským podílem efektivních algoritmů.
Poznání tohoto vzoru vám umožní rychle odvodit a analyzovat nové algoritmy pomocí relací.
Mapuje se také přirozeně na paralelizmus, protože nezávislé podproblémy mohou běžet souběžně.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět