Scribd
Importer
30 vues2 pages

TD 4 Complexité Algo

Le document présente un TD sur la complexité des algorithmes, comprenant plusieurs exercices sur la détermination et la comparaison de complexités temporelles d'algorithmes en Python. Les exercices incluent l'analyse de la recherche séquentielle et dichotomique, le comptage de fréquences de lettres, et la multiplication d'entiers à l'aide d'additions. Chaque exercice demande une évaluation de la complexité temporelle des algorithmes proposés.

Transféré par

anasloyr
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
30 vues2 pages

TD 4 Complexité Algo

Le document présente un TD sur la complexité des algorithmes, comprenant plusieurs exercices sur la détermination et la comparaison de complexités temporelles d'algorithmes en Python. Les exercices incluent l'analyse de la recherche séquentielle et dichotomique, le comptage de fréquences de lettres, et la multiplication d'entiers à l'aide d'additions. Chaque exercice demande une évaluation de la complexité temporelle des algorithmes proposés.

Transféré par

anasloyr
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

Université Mohammed Premier

Pr: DAHMANI Soufiane


Faculté des Sciences OUJDA
Email: [email protected]
Département d’Informatique
Filière: MIP-S2
Informatique 2: Algorithmique 2 / Python

TD N° 4 : Complexité des algorithmes

1 Exercice 1 :Détermination de la complexité temporelle

1.) Considérez l’algorithme suivant :


d e f find max ( l s t ) :
max num = l s t [ 0 ]
f o r num i n l s t :
i f num > max num :
max num = num
r e t urn max num

2.) Quelle est la complexité temporelle de cet algorithme en fonction de la taille de la liste lst ?

2 Exercice 2 :Comparaison de deux algorithmes

• Comparez la complexité temporelle des deux algorithmes suivants pour trouver le minimum
dans une liste non triée :
• Algorithme 1 :
def find min ( l s t ) :
min num = l s t [ 0 ]
f o r num i n l s t :
i f num < min num :
min num = num
r e turn min num

• Algorithme 2 :
def find min ( l s t ) :
r e turn min ( l s t )

3 Exercice 3 :Calcul de la complexité

1.) Donnez une complexité de la fonction f1

1
4 Exercice 4 :Analyse du pire cas

• On considère, pour effectuer la recherche d’un élément dans un tableau, la recherche séquen-
tielle et la recherche dichotomique. On s’intéresse à leur complexité temporelle.
• Pour cela, considérer un tableau ayant mille éléments (version trié, et version non trié).
Pour chaque algorithme, et pour chaque version du tableau, combien de comparaisons sont
à effectuer pour :
– trouver un élément qui y figure ?
– trouver un élément qui n’y figure pas ?
• Quels sont les cas où le tableau est parcouru complètement et les cas où un parcours partiel
est suffisant ?
• Conclure en donnant la complexité temporelle pour chaque algorithme

5 Exercice 5 :

• On considère un tableau à une dimension contenant des lettres majuscules. On désire compter
la fréquence de chacune des 26 lettres de l’alphabet.
1.) Écrire deux procédures qui donnent en sortie un tableau de fréquence: l’une où le tableau
est parcouru 26 fois, et l’autre (plus performante !) où le calcul est fait en un seul parcours.
On pourra supposer que l’on dispose d’une fonction auxiliaire position(lettre) qui pour
chaque lettre donne sa position dans l’alphabet : position(‘A’) = 1, . . . , position(‘Z) =
26.

2.) Donnez la complexité temporelle pour chaque algorithme

6 Exercice 6 :**

• On voudrait écrire une fonction multiplier permettant de multiplier deux entiers positifs ou
nuls a et b (ce n’est pas la peine de vérifier la validité des données) en utilisant uniquement
des opérations d’addition.
• Le prototype de la fonction doit être def multiplier (a, b).
1.) Proposer une version récursive de la fonction multiplier. Estimer sa complexité en nombre
d’additions après avoir déterminé une formule récurrente de la complexité.

2.) Proposer une autre version récursive de la fonction multiplier basée sur le paradigme divi-
ser pour régner. Donner une formule récurrente de sa complexité en nombre d’additions
et estimer la.

3.) Donnez la complexité temporelle pour chaque algorithme

Vous aimerez peut-être aussi