Divide and Conquer je algoritmický vzorec. V algoritmických metodách je návrh vzít spor o velký vstup, rozdělit vstup na menší části, rozhodnout problém o každém z malých částí a poté sloučit po částech řešení do globálního řešení. Tento mechanismus řešení problému se nazývá Strategie rozděl a panuj.

Algoritmus Divide and Conquer se skládá ze sporu pomocí následujících tří kroků.

Rozdělitpůvodní problém na sadu dílčích problémů.Dobýt:Řešte každý dílčí problém samostatně, rekurzivně.Kombajn:Dejte dohromady řešení dílčích problémů, abyste získali řešení celého problému.

Obecně se můžeme řídit rozděl a panuj přístup ve třech krocích.

Příklady: Specifické počítačové algoritmy jsou založeny na přístupu Divide & Conquer:

1. Problém maxima a minima
2. Binární vyhledávání
3. Řazení (sloučit řazení, rychlé řazení)
4. Hanojská věž.

Základ strategie rozděl a panuj:

Strategie Divide & Conquer má dva základní principy:

1. Relační vzorec
2. Stav zastavení

1. Relační vzorec: Je to vzorec, který vygenerujeme z dané techniky. Po vygenerování formule aplikujeme strategii D&C, tj. rekurzivně rozbijeme problém a vyřešíme rozbité dílčí problémy.

2. Stav zastavení: Když problém prolomíme pomocí strategie Divide & Conquer, pak musíme vědět, že po jakou dobu potřebujeme rozdělení a panování aplikovat. Takže stav, kdy je potřeba zastavit naše rekurzivní kroky D&C, se nazývá Stopping Condition.

Aplikace přístupu rozděl a panuj:

Následující algoritmy jsou založeny na konceptu techniky rozděl a panuj:

Binární vyhledávání:Binární vyhledávací algoritmus je vyhledávací algoritmus, který se také nazývá polointervalové vyhledávání nebo logaritmické vyhledávání. Funguje tak, že porovnává cílovou hodnotu s prostředním prvkem existujícím v seřazeném poli. Po provedení srovnání, pokud se hodnota liší, pak polovina, která nemůže obsahovat cíl, bude nakonec odstraněna, následuje pokračování hledání na druhé polovině. Opět zvážíme prostřední prvek a porovnáme jej s cílovou hodnotou. Proces se neustále opakuje, dokud není dosaženo cílové hodnoty. Pokud jsme po ukončení vyhledávání zjistili, že druhá polovina je prázdná, pak lze dojít k závěru, že cíl není v poli přítomen.Rychlé řazení:Je to nejúčinnější třídicí algoritmus, který je také známý jako třídění na základě výměny oddílů. Začíná výběrem pivotní hodnoty z pole a následným rozdělením zbývajících prvků pole do dvou dílčích polí. Rozdělení se vytvoří porovnáním každého z prvků s hodnotou pivotu. Porovnává, zda má prvek větší nebo nižší hodnotu než pivot, a pak rekurzivně třídí pole.Sloučit třídění:Je to třídicí algoritmus, který třídí pole pomocí porovnání. Začíná rozdělením pole na dílčí pole a poté rekurzivně třídí každé z nich. Po dokončení třídění je sloučí zpět.Nejbližší dvojice bodů:Je to problém výpočetní geometrie. Tento algoritmus klade důraz na zjištění nejbližší dvojice bodů v metrickém prostoru zadaných n bodů, takže vzdálenost mezi dvojicí bodů by měla být minimální.Strassenův algoritmus:Je to algoritmus pro násobení matic, který je pojmenován po Volkeru Strassenovi. Ukázalo se, že je mnohem rychlejší než tradiční algoritmus, když pracuje na velkých maticích.Algoritmus Cooley-Tukey Fast Fourier Transform (FFT):Algoritmus rychlé Fourierovy transformace je pojmenován po J. W. Cooley a John Turkey. Dodržuje přístup rozděl a panuj a ukládá složitost O(nlogn).Algoritmus Karatsuba pro rychlé násobení:Je to jeden z nejrychlejších algoritmů násobení tradiční doby, který vynalezl Anatoly Karatsuba na konci roku 1960 a byl publikován v roce 1962. Násobí dvě n-ciferná čísla takovým způsobem, že je redukuje na maximálně jednociferné.

Výhody rozděl a panuj

• Rozděl a panuj obvykle úspěšně řeší jeden z největších problémů, jako je Hanojská věž, matematický hlavolam. Je náročné řešit složité problémy, o kterých nemáte základní představu, ale s pomocí přístupu rozděl a panuj to snížilo úsilí, protože funguje na rozdělení hlavního problému na dvě poloviny a jejich následné rekurzivní řešení. Tento algoritmus je mnohem rychlejší než jiné algoritmy.
• Efektivně využívá vyrovnávací paměť, aniž by zabírala mnoho místa, protože řeší jednoduché dílčí problémy ve vyrovnávací paměti namísto přístupu k pomalejší hlavní paměti.
• Je dokonalejší než technika jeho protějšku Brute Force.
• Vzhledem k tomu, že tyto algoritmy inhibují paralelismus, nezahrnuje žádné úpravy a je řešen systémy zahrnujícími paralelní zpracování.

Nevýhody rozděl a panuj

• Protože většina jeho algoritmů je navržena se začleněním rekurze, vyžaduje to vysokou správu paměti.
• Explicitní zásobník může nadměrně využívat prostor.
• Může dokonce dojít ke zhroucení systému, pokud je rekurze prováděna přísněji než zásobník přítomný v CPU.