Algorithmique et Structures de Données

Chapitre 2
Diviser pour régner

Complexité de QuickSort

Soit $N$ la taille du tableau à triller. Alors, le positionnement du pivot nécessite un parcours du tableau, donc $N - 1$ comparaisons.

Si nous notons $C_n$ la complexité et que nous nous retrouvons avec un pivot en position $i$, nous avons la relation de récurrence :
$C_n=(N-1)+C_i+C_{N-i-1}$

En moyenne, $C_n=N+2C_{N/2}$.

En utilisant la relation de récurrent pour $C_{N/2}$, nous obtenons :
$C_n=N+2(N/2+2C_{N/4})=2N+4C_{N/4}$

Puis : $C_n=3N+8C_{N/8}$
etc.. etc..

Le processus s'arrête lorsque l'indice de droite ($N/8$) devient 1. Alors :
$C_n=(log\,N)N+NC_1$

Conclusion : $C_n = O(N\,log\,N)$ !

Transformée de Fourier

Voici une onde...

En 1D, cela peut représenter un son. En 2D, une image...
Problème : Comment traiter et stocker efficacement cette onde ?

Solution naïve, traiter et stocker l'onde tels quelle

Notre onde peut-être décomposée en plusieurs ondes sinusoïdales...

Voici une onde carré...

De même, celle-ci peut-être approximée en plusieurs onde sinusoïdale...

Il faut beaucoup d'iterations pour obtenir une bonne reconstruction

Transformée de Fourier Discrète

fft.cpp

                    
std::complex<float> dft(const std::complex<float>> f[], int n, int k, float s);

$DFT(f)[k] = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}f[j]e^{-\frac{2i\pi}{N} jk}.$
pour un $k$ donné

test_fft.cpp

$DFT(f)[k] = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}f[j]e^{-\frac{2i\pi}{N} jk}.$
pour $\qquad k = 0,\dots,n-1.$

Transformée de Fourier Rapide

Divier pour régner

Pour $N\geq2$, on sépare la somme dans la DFT en indices pairs et impairs: $$\sqrt{N} DFT(f)[k] = \sum_{j=0}^{N/2-1}f[2j]e^{-\frac{2i\pi}{N} (2j)k} + \sum_{j=0}^{N/2-1}f[2j+1]e^{-\frac{2i\pi}{N} (2j+1)k},$$

Dont on déduit facilement: $\sqrt{N} DFT(f)[k] = \sum_{j=0}^{N/2-1}f[2j]e^{-\frac{2i\pi}{N/2} jk} + e^{-\frac{2i\pi}{N}k} \sum_{j=0}^{N/2-1}f[2j+1]e^{-\frac{2i\pi}{N/2} jk}.$