skupinu algoritmů From Wikipedia, the free encyclopedia
Metoda rozděl a panuj (latinsky Divide et Impera) 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í.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.