Rozděl a panuj (algoritmus)

Metoda rozděl a panuj označuje ty algoritmy pro práci s daty, které řeší problém rozdělením řešené úlohy na dílčí části (podproblémy), nad kterými se provádí algoritmická operace. Často se tato metoda implementuje rekurzivně nebo iterativně a původní úloha se dělí na stále menší části, až v některé úrovni dosáhne problému konstantní velikosti, který lze triviálně vyřešit (např. u algoritmu řazení slučováním - posloupnost délky jedna je vždy seřazená). Důležitým předpokladem této metody je, aby dílčí podproblémy byly v rámci jedné úrovně jeden na druhém nezávislé (pokud jsou závislé, je většinou možné použít metodu zvanou dynamické programování).

Také se hodí a používá pro cache-oblivious algoritmus. Po postupném dělení se úloha na základní úrovni vejde do keše a následně vyřeší rychle.

Typickými představiteli metody rozděl a panuj jsou algoritmy třídění rychlé řazení, řazení slučováním, výpočet rychlé Fourierovy transformace nebo binární vyhledávání.

Související články

Master theorem

Externí odkazy

Kategorie:Algoritmy