Ve výpočetní technice je rozdělení a dobývání (z latiny „ Divide ut imperes “ , rozděl a panuj v angličtině) algoritmická technika, která se skládá z:
Tato technika poskytuje efektivní algoritmy pro mnoho problémů, jako je hledání položky v seřazeném poli ( binární vyhledávání ), třídění ( sloučení , rychlé řazení ), šíření velkého počtu ( algoritmus Karatsuba ) nebo transformace Diskrétní Fourier ( rychlá Fourierova transformace ) .
V následující tabulce jsou uvedeny příklady algoritmů poskytujících tři fáze (dělení, vládnutí, kombinování).
Rozdělit | Vládnout | Kombajn | |
---|---|---|---|
Dichotomické vyhledávání | Najít x v seřazeném poli T [1, .. n],
|
- | - |
Sloučit třídění | rozdělili jsme pole T [1, .. n], které se má třídit, na dvě dílčí pole T [1, .. n / 2] a T [n / 2 +1, .. n] | setřídíme dvě dílčí pole T [1, .. n / 2] a T [n / 2 +1, .. n] (rekurzivně, nebo neděláme nic, pokud mají velikost 1) | vypočítáme seřazenou permutaci počátečního pole sloučením dvou seřazených dílčích polí T [1, .. n / 2] a T [n / 2 +1, .. n]. |
Rychlé třídění | náhodně vybereme prvek pole, který bude „otočný“ a vyměníme všechny prvky tak, aby se nalevo od otočného prvku umístily prvky, které jsou pod ním, a napravo ty, které jsou nad ním | obě poloviny jsou seřazeny na obou stranách čepu. | - |
Zde jsou další příklady algoritmů rozdělení a dobývání :
Dichotomický výzkum je formován v článku Johna Mauchlyho v roce 1946, ale myšlenka použití tříděného seznamu k usnadnění výzkumu sahá až do Babylonu v roce -220. Eukleidův algoritmus spočítat největší společný dělitel dvou čísel může být viděn jako rozděl a panuj (obě čísla snížit a jeden se redukuje na menší problém). Gauss popisuje rychlou Fourierovu transformaci v roce 1805, aniž by provedl analýzu složitosti. Rychlá Fourierova transformace je znovuobjevena o století později.
John von Neumann vynalezl fúzní třídění v roce 1945. Algoritmus Karatsuba vynalezl Anatolii A. Karatsuba v roce 1960: vynásobí dva počty n číslic v operacích (viz notace Landau ). Tento algoritmus odporuje domněnce Andreje Kolmogorova z roku 1956, která uvádí, že operace jsou nezbytné. Knuth uvádí metodu používanou poštovními službami : písmena jsou tříděna a rozdělena podle geografických oblastí, poté do subgeografických oblastí atd. Toto třídění je radixové třídění , popsané pro kartové stroje IBM (IBM card sorter (en) ) z roku 1929.
Nízká složitost algoritmů rozděl a panuj je jedním z jejich hlavních zájmů. Existuje několik vět, které usnadňují výpočet složitosti algoritmů dělení a dobývání. Hlavní teorém je Masterův teorém . U složitějších případů můžeme uvést větu Akra-Bazzi . Následující tabulka porovnává složitost naivního algoritmu a algoritmu rozdělení a dobývání u některých problémů (viz Landauovy notace ):
Složitost s naivním algoritmem | Složitost s algoritmem rozděl a panuj | |
---|---|---|
Hledejte v seřazeném poli o velikosti n | My) | O (log n) |
Třídění pole n prvků | O (n²) (viz vložení řazení , výběr řazení ) | O (n log n) s druhem sloučení
O (n log n) v průměru s rychlým tříděním |
Násobení dvou čísel n číslicemi | O (n²) | s algoritmem Karatsuba |
Algoritmy rozdělení a dobývání jsou často přizpůsobeny pro provoz na strojích s více procesory.
Existují obvody pro vstupy pevné velikosti pro rychlou Fourierovu transformaci . Existují také třídicí sítě pro třídění fúzí, tzv. Bitonické třídění .
Algoritmy rozděl a panuj se přirozeně hodí k rekurzivnímu psaní . Ale někdy může běh rekurzivních algoritmů vést k přetečení zásobníku . Proto někdy dáváme přednost iteračnímu algoritmu.
Při použití funkce „rozděl a panuj“ nedojde k žádné redundanci: každý dílčí problém je během rekurzivních volání vyřešen pouze jednou. Na druhou stranu, když jsou dílčí problémy nadbytečné, může mít rekurzivní algoritmus získaný z „rozděl a panuj“ špatnou složitost. Vezměme si příklad výpočtu n -té doby na Fibonacciho posloupnosti . Následující algoritmus je v exponenciálním čase v n:
fonction fibonacci(n) si(n = 0 ou n = 1) renvoyer 1 sinon renvoyer fibonacci(n-1) + fibonacci(n-2)K překonání tohoto limitu si lze zapamatovat již vypočítané hodnoty, aby se předešlo vyřešení již zjištěných dílčích problémů. Jedná se o zapamatování (používá se také v dynamickém programování ).