Scribd
Importer
0 vues3 pages

TD2

Ce document est un TD sur la complexité algorithmique, comprenant plusieurs exercices sur l'analyse de la complexité de différents algorithmes. Les exercices incluent des questions sur l'égalité de complexité, le décompte d'opérations dans divers cas, et l'évaluation de la complexité asymptotique pour plusieurs algorithmes. Il aborde également des concepts tels que les notations Big O et les justifications des résultats obtenus.

Transféré par

Mersel Fares
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
0 vues3 pages

TD2

Ce document est un TD sur la complexité algorithmique, comprenant plusieurs exercices sur l'analyse de la complexité de différents algorithmes. Les exercices incluent des questions sur l'égalité de complexité, le décompte d'opérations dans divers cas, et l'évaluation de la complexité asymptotique pour plusieurs algorithmes. Il aborde également des concepts tels que les notations Big O et les justifications des résultats obtenus.

Transféré par

Mersel Fares
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

UMBB, Faculté des Sciences, Département d’informatique

Matière : Advanced Algo & Complexity

TD2 : Complexité algorithmique


Rappel : Si f, g mesurent la complexité algorithmique alors

Ex0:
1. L'égalité suivante est-elle vraie ? Justifiez votre réponse sans faire de calculs.

2. Déterminer l'expression simplifiée de chacune des sommes suivantes

Ex1:
On considère les deux algorithmes suivants :
Algorithme Exemple_1 Algorithme Exemple_2
Entrée : un entier n ≥ 1 Entrée : un entier n ≥ 1
Début Début
pour i ← 1 à n faire pour i ← 1 à n faire
pour j ← 1 à i faire pour j ← 1 à i faire
s ← i + j pour k ← 1 à j faire
afficher(s) s ← i + j + k
fin pour afficher(s)
fin pour fin pour
Fin fin pour
fin pour
Fin
Pour ces deux algorithme déterminer la complexité (nombre d’opérations élémentaires en
fonction de n).
Rem : On peut utiliser la formule suivante

1
Ex2:
Soit le pseudo code suivant :

1. Déterminer ce que fait l’algorithme.


Pour les questions 2,3 et 4 on utilisera un décompte détaillé.
2. Déterminer le nombre d’opérations dans le meilleur cas (x en première position).
3. Déterminer le nombre d’opérations dans le pire cas (x absent ou dernière position).
4. Donner la complexité asymptotique pour chaque cas.
Pour cette question on ne comptabilisera que les comparaisons.
5. En supposant que x apparaît exactement une fois avec probabilité uniforme dans la
matrice, calculer le nombre d’opérations moyen.
Ex3:
Déterminer la complexité asymptotique au pire des cas des algorithmes associés aux
problèmes suivants en complétant le tableau :
Algorithme associé au problème O( ? ) Justification
Somme de deux vecteurs de n éléments
Somme de deux matrices carrées d’ordre n
Produit de deux matrices carrée d’ordre n
Calcul itératif de la factorielle de n
Calcul itératif de la somme 1 + 2 + . . . + n
Insertion en tête d’une liste chaînée simple de taille n
Insertion en tête d’un tableau de taille n

2
Insertion à la fin d’une liste chaînée simple de taille n
Insertion à la fin d’un tableau de taille n
Tester si un nombre n est pair ou impair

Ex4:
Les formules 2n+1=O(2n) et 22n=O(2n) sont elles correctes. Justifier.

Ex5:
Pour les paires de fonctions suivantes, indiquez si f ∈ O(g) ou g ∈ O(f) ou les deux.
Prouvez vos affirmations (il n’est pas demandé de prouver un résultat négatif).

Ex6 :
On dispose des temps d’exécution (en millisecondes) de trois algorithmes A 1,A2,A3 pour
différentes tailles d’entrée n :

Pour chacun des trois algorithmes, déterminez la complexité asymptotique en notation O.


Justifiez votre choix en identifiant des valeurs témoins (witness values).

Vous aimerez peut-être aussi