Tris

Exemple d’implantation de ces algorithmes ici

Complexité quadratique ($\Theta(n^{2})$)

Tri à bulle

$f(n) = \Theta(n^{2})$ si $f\frac{n}{n^{2}}$ est bornée

Taille $n$ :
$$\sum\limits_{k=1}^{n}k=\frac{n(n+1)}{2}=(n-1)+(n-2)+\dots+1$$

Tri par insertion

Complexité $\Theta(nlog(n))$

$$1+2+\dots+(n-1)=\frac{n(n+1)}{2}$$

Tri rapide et tri fusion

$n$ base10 => binaire
_ _ _ _ _ _ $\frac{n}{2}$
_ _ _ _ _ 0 $\frac{n}{4}$ (ou 1 à la place de 0)

$n$ sur $k$ bits
$$2^{k-1} \leq n \leq 2^{k}$$
$$\begin{aligned}a^{b} =& e^{ln(a)b} \\\ &e^{(h-1)ln(2)} \leq n \leq e^{ln(2)k} \\\ &(k-1)ln(2) \leq ln(n) \leq ln(2)k \\\ &(k-1) < \frac{ln(n)}{ln(2)} \leq k \end{aligned}$$

Suite de Fibonacci

Méthode de récursivité lourde $\approx \Theta(2^{n})$

Soit $C_{n}$ $k$ nombre d’opérations pour calculer $F(n)$
$C_{n} = (1 +) C_{n-1} + C_{n-2}$, la complexité c’est grosso-modo Fibonacci + 1, donc
$C_{n} \simeq F(n)$
Donc, $F(n) = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n} + (\frac{1-\sqrt{5}}{2})^{n})$ : ça fonctionne jusqu’à une certaines valeurs et après ça ne fonctionne plus.

Calcul matricielle

$\begin{pmatrix} 1 & 1 \\\ 1 & 1 \end{pmatrix}$ avec $\begin{pmatrix} 1 & 2 \\\ 3 & 4 \end{pmatrix}$ donne : $\begin{pmatrix} 3 & 3 \\\ 7 & 7 \end{pmatrix}$

La matrice est cachée dans ce système :
$$\left[\begin{array}{ll} F(n) = F(n-1) + F(n-2) \\\ F(n-1) = F(n-1) \end{array}\right.$$

Donnant :
$$\begin{array}{ll} \quad\quad F(n) = \\\ F(n-1) = \end{array} \begin{pmatrix} 1 & 1 \\\ 1 & 0 \end{pmatrix} \text{ avec } \begin{pmatrix} F(n-1) \\\ F(n-2) \end{pmatrix} \text{ donne } \begin{pmatrix} F(n-1) & F(n-2) \\\ F(n-1) \end{pmatrix}$$

Exponentiation rapide

$a^{n}$ puissance rapide

si (n == 1)
	retourne a
sinon
	si n % 2 == 0
		x = puissance_rapide(a, n / 2)
		retourne x * x
	sinon
		x = puissance_rapide(a, n / 2)
		retourne a * x * x
 
Copier

$a^{n}$ $A^{n}$ puissance rapide

si (n == 1)
	retourne A
sinon
	si n % 2 == 0
		x = puissance_rapide(A, n / 2)
		retourne multiplication(x, x)
	sinon
		x = puissance_rapide(a, n / 2)
		retourne a * x * x
 
Copier

Triangle de Pascal (avec coefficient binomiaux) :
$$\begin{pmatrix} n \\\ k \end{pmatrix} = \begin{pmatrix} n - 1 \\\ k - 1 \end{pmatrix} + \begin{pmatrix} n - 1 \\\ k \end{pmatrix}$$