Rozděl a panuj (algoritmus)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Metoda rozděl a panuj (anglicky divide and conquer, 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 Mergesortu - 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í).

Typickými představiteli metody rozděl a panuj jsou algoritmy třídění Quicksort, Merge sort, výpočet rychlé Fourierovy transformace (FFT) nebo binární vyhledávání.

Související články[editovat | editovat zdroj]

Master theorem