2. Domination de suite

Cf. TD1reponses

Le nombre d’opérations d’un algorithme pour résoudre un problème dépend des données du problème. Afin de caractériser l’efficacité d’un algorithme, on étudie la suite qui lie la taille des données du problème avec le nombre d’opérations de l’algorithme.

Définition (suite numérique)

Une suite numérique est une application de \N dans \R.

Exemple

• 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
• 3, 3, 3, 3, 3, 3, 3, 3, 3, ...
• 1, 2, 4, 8, 16, 32, 64, ...
• 2, 4, 6, 8, 10, 12, 14, ...

Vocabulaire

On peut décrire la suite avec une formule explicite ou avec une formule récursive.

Exemple

Formules explicite :
\ u : n \mapsto\ \ 3 : 3, 3, 3, 3
\ v : n \mapsto\ \ n : 0, 1, 2, 3
w : n \mapsto 2n : 0, 2, 4, 6, 8
\ r : n \mapsto 2^n\ : 1, 2, 4, 8, 16, 32

V_{n} = \begin{cases} & 0 \text{ si } n = 0 \\\\ & V_{n-1} \text{ si } n \neq 0 \end{cases}

W_n = \begin{cases} & 0 \text{ si } n = 0 \\\\ & W_{n-1}+2 \text{ si } n \neq 0 \end{cases}

R_n = \begin{cases} & \text{ si } n = 0 \\\\ & R_{n-1} \text{ si } n \neq 0 \end{cases}

Définition (Domination)

Soient U et R deux suites numérique, on dit que U domine R si :
\exists\ M > 0, M \in \R, \exists\ n \in \N, \forall_n > n_0, |R_n| \leq M.|U_n|

On note R = O(u) ou R \ll U (celle qui domine est celle qui croît le plus vite)
On note \Omega(U) l’ensemble des suites qui domine U.
U \in O(D)

Propriété

Si U, V, W sont des suites et m, w des nombres réels, alors :

• Si U \ll V et V \ll W alors U \ll W
• Si U, V \ll W alors m.U + V \ll w
• Si \forall n \in \N, w.V \leq m.|W_n| alors V \leq W
• L’ensemble O(1) est l’ensemble des suites bornées
• L’ensemble O(V) est égale à l’ensemble |V|.O(1) (=(V_n.U_n)_{n\in\N} avec U suite bornée).

Remarque

Si U, F, W sont des suites, alors :

• U \ll U (dominé par elle-même)
• O(U).O(F) = O(F.U)
• Si U\ll W, alors U\times V\ll W\times V

Notation

Si U et V sont des suites et que on a U\ll V et V\ll U on note U = \Theta(U) (ou V =\Theta(U)) -> c’est une relation d’équivalence.

Exemple

• 1 = O(n) mais n \neq O(1)
• 4n^5+3n^4+10n+20=\Theta(n^5)
• log(n) = \Theta(ln(n))
• n.ln(n)\neq\Theta(ln(n)) | ln(n) = \Theta(n.ln(n))