# Cour 4 -- Algorithme

###### tags `cour` `M1 S1` `Algorithme`
[Somaire](/ueYXUIJIQ6C6hcYzKYeojA#)\
[precedent](/IdYcb7YBTBSveQ_t0efkLw)
> [time= 28 sept 2020]

[TOC]

## le k^ième^ plus petit élément (suite)
### analyse de compléxité

Digraph G{
    p0 -> {p11, p12}
    p11 -> {p21, p22}
    p12 -> {p23, p24}
    {
    rank=same
    p0 [label="N"]
    }
    
    {
    rank=same
    p11 [label="N/5"]
    p12 [label="<=7N/10"]
    }
    {
    rank =same
    p21 [label="(N/5)/5"]
    p22 [label="7(N/5)/10"]
    p23 [label="(7N/10)/5"]
    p24 [label="7(7N/10)/10"]
    }
}

Compléxité de *T(N)* de BFPRT:
$$
\begin{align}
T(N) \leq T\left(
\frac{N}{5}
\right) +
T\left(
\frac{7N}{10}
\right) +
f(N)
\end{align}
$$
- $T\left( \frac{N}{5} \right)$ pour la médiane de M
- $T\left( \frac{7N}{10} \right)$ apelle récursif (dans le pire cas)
- $f(N)$ temp en dehors de l'appels récursifs
- linéaire pour la calculer la médianne
- linéaire pour la partition

A l'étage 1 on a:
$$
O\left(
\frac{N}{5}
\right) +
O\left(
\frac{7N}{10}
\right)
\simeq O\left(
\frac{9N}{10}
\right)
$$
A l'étage 2:
$$
\begin{align}
&= \frac{N}{5} \left(\frac{1}{5} + \frac{7}{10} \right) +
\frac{7 N}{10} \left(\frac{1}{5} +\frac{7}{10} \right)\\
&= \frac{N}{5} \left(\frac{9}{10} \right) +
\frac{7 N}{10} \left(\frac{9}{10} \right)\\
&= \frac{9}{10} \left(\frac{N}{5} +\frac{7 N}{10} \right)\\
&= N \left(\frac{9}{10} \right)^2
\end{align}
$$

On prouve par récurrence qu'au i^ieme^ niveau, la compléxité est de $(\frac{9}{10})^i \times N$.\
Au total:
$$
\begin{align}
T(N)& = \sum_{i=0}^{[]}\left(
\frac{9}{10}\right)^i \times N\\
& = N \underbrace{\sum_{i=0}^{[]} \left(
\frac{9}{10}\right)^i}_{\text{la série converge}\\
\text{donc est constante}}\\
& = O(N)
\end{align}
$$

## multiplication de Karatsuba
### algo conventionel:

### Aproche diviser pour regner

compléxité:
$$
T(N) = 4 \times T\left(\frac{N}{2}\right) + O(N)
$$
- $4 \times T\left(\frac{N}{2}\right)$ les 4 multiplication\
*(A x B; B x D; A x C; C x B)*
- $O(N)$ pour les additions


$$
\begin{align}
T(N)&= \sum_{i=0}^{log(N)} 4^i \times \frac{N}{2^i} \\
&= \sum_{i=0}^{log(N)} 2^i\times N \\
&= N \sum_{i=0}^{log(N)} 2^i\\
&= N (2^{log(N) + 1} - 1)\\
&\backsimeq N \times 2N\\
&\backsimeq 2N^2
\end{align}
$$
**Conclusion** on a fait un algo plus compliqué mais de compléxité N^2^!

### Karatsuba
Observation:
si on multiplie:\

  u = [   a   ] [   b   ]
x v = [   c   ] [   d   ]
-------------------------
                [  b.d  ]
        [  a.d  ]
        [  c.b  ]
[  a.c  ]

avec:
- |a|=|b|=|c|=|d|=m
- |u| = 2m
- |v| = 2m

$u \times v = 2^{2m}ac + 2^{m}(ad + bc) + bd$
- $2^{2m}$ est le décalage

**Ruse**
$$
\begin{align}
(a-b) (d-c)
&= ad + bc - bd - ac\\
&= z
\end {align}
$$

On va faire 3 appels récurifs à la multiplication
1. $(a - b)(d - c)$
2. $a \times c$
3. $b \times d$

Puis retourner:
$$
2^{2m} ac + 2^m (z + bd + ac) + bd = u \times v
$$

Relation de récurrence de compléxité:
$$
T(N) = 3T\left(\frac{N}{2}\right) + O(N)
$$

$$
\begin{align}
T(N) &= \sum_{i=0}^{log_2(N)} 3^i \times \frac{N}{2^i}\\
&= N \sum_{i=0}^{log_2(N)} \left(
\frac{3}{2}\right)^i
\end{align}
$$
Rappel série géométrique:
$$
\begin{align}
\sum_{k = 1}^{k}\left(
\frac{a}{b}\right)^k
& = \frac{1 - \left(
\frac{a}{b}\right)^k }
{1 - \left(\frac{a}{b}\right)}\\
\text{si } \frac{a}{b} > 1 \text{ la série diverge} \quad & \backsimeq \big(\frac{a}{b}\big)^k
\end{align}
$$

Donc:
$$
\begin{align}
T(N) &\leq N \left( \frac{3}{2} \right)^{log_2(N)}\\
&= N \frac{3^{log_2(N)}}{2^{\log_{2}(N)}}\\
&= N \frac{3^{log_2(N)}}{N}\\
&= 3^{log_2(N)}\\
&= \left(2^{log_2(3)}\right)^{log_2(N)}\\
&= \left(2^{\times log_2(N)}\right)^{log_2(3)}\\
&= N^{log_2(3)} \backsimeq 1,58
\end{align}
$$

- $\leq$ car on prend le plus grand therme de la série

karatsuba $\backsimeq N{1,58} < N^{2}$

## Master théorem (version Erickson)
$$
\begin{align}
\text{Si } T(N) &= a T\left(\frac{N}{b}\right) + f(N) \text{ et:}\\
(1) \quad & a f(\frac{N}{b}) = c f(N), \: c < 1\\
&\Rightarrow T(N) = \theta(f(N))\\
\\
(2) \quad & a f(\frac{N}{b}) = c f(N), \: c = 1\\
&\Rightarrow T(N) = \theta(f(N) \times \log_b(N))\\
\\
(3) \quad & a f(\frac{N}{b}) = c f(N), \: c > 1\\
&\Rightarrow T(N) = \theta(N^{\log_b(a)})\\
\end{align}
$$

[suivant](/iv7_YjPzRnKPIGlFmtuPOA)