Scribd
Importer
24 vues2 pages

Complexité des Algorithmes Récursifs

Ce document présente quatre exercices sur l'analyse de complexité d'algorithmes récursifs. Les exercices portent sur la résolution d'équations de récurrence, la recherche dichotomique, le calcul du maximum d'une liste de manière récursive et la recherche d'un élément majoritaire dans une liste.

Transféré par

salma ben hssin
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
24 vues2 pages

Complexité des Algorithmes Récursifs

Ce document présente quatre exercices sur l'analyse de complexité d'algorithmes récursifs. Les exercices portent sur la résolution d'équations de récurrence, la recherche dichotomique, le calcul du maximum d'une liste de manière récursive et la recherche d'un élément majoritaire dans une liste.

Transféré par

salma ben hssin
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithmique Avancée & Complexité

TD5 – Analyse des Algorithmes Récursifs

Exercice 1
Déterminer de deux façons différentes les complexités respectives aux équations de récurrence
suivantes :
a. T(n) = 4T(n/2) + n ; T(1) = 1
b. T(n) = 2T(n/2) + n ; T(1) = 1
c. T(n) = 3T(n/4) + n ; T(1) = 1
d. T(n) = 3T(n/2) + n2 ; T(1) = 1

Exercice 2
1. Quelle est la complexité de l’algorithme de recherche séquentielle d’un élément dans un
tableau à n éléments ? justifier.

2. La recherche dichotomique d’un élément x dans un tableau trié T (à n éléments) se


présente sous la fonction récursive suivante :

Fonction Dichotomie(T :Tab, x; d; f : entier) : booléen


var Milieu : entier
début
si (d>f)alors Dichotomie Faux
sinon
si (x = T[Milieu]) alors Dichotomie  Vrai
sinon
si (x < T[milieu]) alors Dichotomie Dichotomie(T; x; d;
milieu)
sinon Dichotomie  Dichotomie(T; x; milieu; f)
fsi
fsi
fsi
Fin
a. Sachant que la complexité de l’algorithme de recherche dichotomique dans un tableau à n
éléments est T(n), montrer que T(n) = T(n/2) + O(1).

b. Déduire une estimation asymptotique de T(n) en appliquant le théorème de résolution des


récurrences.

c. Calculer cette même estimation d’une autre manière.

Exercice 3
Concevoir un algorithme récursif m-aire (m>= 2) calculant le maximum d’une liste de taille n.
Déterminer sa complexité. Comparer avec l’algorithme itératif classique. Conclure.

Exercice 4

Soit E une liste de n éléments rangés dans un tableau numéroté de 1 à n. On suppose que la
seule opération qu’on sait effectuer sur les éléments est de vérifier si deux éléments sont égaux
ou non. On dit qu’un élément x ∈ E est majoritaire si l’ensemble Ex = {y ∈ E | y = x} a
strictement plus de n/2 éléments. On supposera que n est une puissance de 2.

1. Écrire une fonction itérative permettant de retourner l’élément majoritaire s’il existe. Quelle
est la complexité́ de cet algorithme ?
2. Donner une fonction récursive MajoritaireRec(i; j) selon la stratégie « Diviser pour Régner »
basé sur un découpage de E en deux listes de même taille. Il est recommandé de passer par la
fonction Occurrence(E,x, i, j) qui calcule le nombre d'occurrences de x dans le sous-tableau
E[i..j]. Calculez sa complexité.

Soit T(n) le nombre d’opérations effectuées par l’algorithme MajoritaireRec(i; j) sur une
donnée de taille n.
Complétez la formule suivante ::: si :::::
T(n) =
::::: sinon

– Utilisez le théorème maître pour calculer la complexité de l’algorithme MajoritaireRec(i; j)


– Utilisez la méthode par substitution pour prouver cette complexité.

Vous aimerez peut-être aussi