Metoda rozděl a panuj

Při používání metody rozděl a panuj se snažíme o dělení problému na menší pod problémy, z jejich výsledků pak skládat výsledek a s menšími problémy naložíme stejně, dokud se nedostaneme k triviálním vstupům.

MergeSort

$$\begin{array}{rl}& \text{MergeSort}\\ & \text{Vstup: }{a}_1,\dots ,a_n\text{ k setrˇıˊzenıˊ}\\ & \text{Vyˊstup: }{b}_1,\dots ,b_n\text{ setrˇıˊzenaˊ}\\ & \text{1. Pokud }n=1,\text{ pak vraˊtıˊme }{a}_1=b_1\text{ a skoncˇıˊme}\\ & \text{2. }{x}_1,...,x_{\lfloor n/2\rfloor }\leftarrow \text{MergeSort}(a_1,...,a_{\lfloor n/2\rfloor })\\ & \text{3. }{y}_1,...,y_{\lceil n/2\rceil }\leftarrow \text{MergeSort}(a_{\lfloor n/2\rfloor +1},...,a_n)\\ & \text{4. }{b}_1,...,b_n\leftarrow \text{Merge}(x_1,...,x_{\lfloor n/2\rfloor };y_1,...,y_{\lceil n/2\rceil })\end{array}$$

Kde Merge je metoda slévající v lineárním čase dvě seřazené posloupnosti.

Analýza

$T(n)$ bude značit počet kroků algoritmu MergeSort na $n$ velkém vstupu.

$$\begin{array}{rl}T(1)& =1\\ T(n)& =2\cdot T(n/2)+n\end{array}$$

Rovnici vyřešíme dosazením rekurentní rovnice do rekurentní rovnice a pozorujeme přírůstky.

---

Master theorem

Věta: Rekurence, $a\in \mathbb{N}$, $b>1,c\ge 0$

$$\begin{array}{rl}T(n)& =aT(n/b)+\Theta (n^c)\\ T(1)& =T(0)=1\end{array}$$

tak rekurence má řešení

1. $T(n)\in \Theta (n^c)$ pro $\frac{a}{b^c}<1$,
2. $T(n)\in \Theta (n^c\log n)$ pro $\frac{a}{b^c}=1$,
3. $T(n)\in \Theta (n^{{\log }_{b}a})$ pro $\frac{a}{b^c}>1$.

---

Karatsuba

Rozdělíme každé číslo na dvě poloviny (po $\frac{n}{2}$ cifrách):

$$\begin{gathered} x=x_1\cdot 10^{n/2}+x_0 \\ y=y_1\cdot 10^{n/2}+y_0 \end{gathered}$$

Pak:

$$x\cdot y=x_1{y}_1\cdot 10^n+((x_1+x_0)(y_1+y_0)-x_1{y}_1-x_0{y}_0)\cdot 10^{n/2}+x_0{y}_0$$

Tedy:

• místo 4 rekurzivních volání pro součiny: $x_1{y}_1$, $x_1{y}_0$, $x_0{y}_1$, $x_0{y}_0$
• použijeme jen 3: $x_1{y}_1$, $x_0{y}_0$, a $(x_1+x_0)(y_1+y_0)$

Rekurentní rovnice

$$T(n)=3T(n/2)+\Theta (n)$$

Výsledek:

$$T(n)=\Theta (n^{{\log }_{2}3})\approx \Theta (n^{1.585})$$