---
# System prepended metadata

title: Cour 4 -- Algorithme
tags: [M1 S1, Algorithme, cour]

---

# 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)
![Imgur](https://i.imgur.com/2E0SLyq.png)
### analyse de compléxité
```graphviz
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:
![](https://i.imgur.com/2eT79L3.png)

### Aproche diviser pour regner
![](https://i.imgur.com/nCPDDtd.png)

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

![](https://i.imgur.com/m3oovrY.png)

$$
\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)