Bienvenue, le sujet d'aujourd'hui portera sur l'étude de la complexité des algorithmes, ce sujet s'adresse particulièrement aux étudiants de deuxième année Informatique (branche MI - AS3), bon lecture.
Contenu du sujet
- Qu'entendons-nous par algorithme
- Qu'entendons-nous par complexité des algorithmes
- Exercices sur la complexité des algorithmes

Qu'entendons-nous par algorithme
Un algorithme est un proc´ed´e automatique pour r´esoudre un probl`eme en un nombre fini d’´etapes.
Pour accéder aux leçons des algorithmes d'ici
Qu'entendons-nous par complexité des algorithmes
Le calcul de la complexité d’un algorithme permet de mesurer sa performance. Il existe deux types de complexité :
- complexité spatiale : permet de quantifier l’utilisation de la mémoire
- complexité temporelle : permet de quantifier la vitesse d’exécution
Bientôt, un sujet détaillé sera développé sur la leçon de la complexité des algorithmes
Exercices sur la complexité des algorithmes
Maintenant devant vous quelques exercices sur l'étude de la complexité des algorithmes, des exercices merveilleux et très utiles pour comprendre les techniques de détermination du degré de complexité des algorithmes, et bien sûr ces exercices sont joints à la correction typique, afin que vous puissiez identifier vos erreurs et les étudier
- Exercice 1
- Exercice 2
On considère, pour effectuer la recherche d’un élément dans un tableau, la recherche séquentielle
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
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. Ecrire 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.
La méthode qui parcourt le tableau 26 fois consiste à parcourir le texte pour compter d’abord tous les A, recommencer pour compter tous les B, etc. On utilise un tableau d’entiers de 26 cases, qui sert à mémoriser les occurrences. La deuxième méthode demande de disposer de la conversion d’une lettre en un entier, qui correspond à sa place dans l’alphabet. (En c++, on ferait tout simplement appel à i = car – ‘A’).
char texte[TMAX]
int cpt, pos, occ[26]
pour cpt := 1 à 26 faire occ[cpt]:= 0 {initialisation à zéro}
cpt := 1
tant que (texte[cpt] ≠ CARFIN) faire
pos := conversion(texte[cpt])
occ[pos] := occ[pos] + 1
cpt := cpt + 1
ftq