[ALGO] Complexite des algorithmes (8)

Preuve de complexite par recurrence

H1 est vraie
si H1, H2, …, Hn-1 sont vraies, alors Hn est vraie
, Hn est vraie

Prouver que T(n) = O(f(n))

  1. Poser l’hypothese Hn : " pour un (qu’on peut choisir aussi grand qu’on veut)"

  2. Montrer que est vraie (cas de base)

  3. Supposer et montrer que est vraie

  4. Conclure que Hn vraie et donc T(n) = O(f(n))

Applications

Exemple 1:


Intuition : ?


est fausse

Ou c existe par definition de

est vraie


Cas general :
Pour , on suppose


Ou si c est choisi assez grand pour dominer

Donc est vraie.

On a montre
Donc


Exercice 2:


Intuition :

On essaye de montrer par recurrence


vraie
vraie

Pour , on suppose

On applique notre hypothese


On veut supprimer le + 1
Hypothese pas suffisamment precise ? On soustrait le terme qui nous derange dans l’hypothese de depart



vraie (pour c suffisamment grand)
vraie

, on suppose

On applique notre hypothese



vraie Donc

Selection de la valeur de rang k

k-ieme plus petite valeur

rang 0 = min
rang n - 1 = max
rang = mediane

Exemple:
On veut k = 4

2 3 4 7 9 2 5 7
2 3 4 7 9 2 5 7
2 3 4 7 5 2 | 9 7
k =4
2 | 3 4 7 5 2
k =3
2 | 4 7 5 3
k =2
3 | 7 5 4
k = 1
4 | 5 7
k = 0
5 | 7
Selection(A, b, e, k)
// retourne la valeur de rang k dans A[b...e-1]
// 0 <= k < e - b
if (e - b) == 1
    return A[b]
else
    m <- Partition(A, b, e)
    l <- m - b
    if (k < l)
        return Selection(A, b, m, k)
    else
        return Selection(A, m, l, k - l)
Ligne de code Cout
if (e - b) == 1 return A[b]
m <- Partition(A, b, e)
l <- m - b
return Selection(A, b, m, k)
return Selection(A, m, l, k - l)

Meilleur cas :




Donc

Autre cas (favorable) :



Donc

Pire cas :



Donc

Cas moyen :

Moyenne sur tous les cas possibles

Intuition :


, supposons

On applique notre hypothese



Ou si c choisi assez grand


Par ailleurs, a cause de l’appel a Partition, donc

On veut une meilleure complexite pour le pire cas >> IntroSelect