Bonjour a tous,
Pour l'exercice 5.a. dont le but est de trouver le nombre de mots dans une chaine de caracteres, j'ai ecrit l'algorithme suivant:
phrase := " hello world !!! "
counter := 0
POUR chaque lettre:
PENDANT QUE la lettre est un espace:
passer a la lettre suivante
SI la lettre est la derniere:
sortir de la boucle
PENDANT QUE la lettre n'est pas un espace:
passer a la lettre suivante
counter = counter + 1
SORTIR counter
Explication (j'utilise le caractere | pour indiquer ou on en est dans les iterations):
"| hello world !!! "
On saute tous les espaces
On n'est pas encore a la fin, donc on continue
" |hello world !!! "
On saute tous les non-espaces
" hello| world !!! "
On a trouve la fin d'un mot, donc on peut incrementer le compteur de mots
etc...
" hello world !!!| "
On saute tous les espaces
On est a la fin, donc on sort sans incrementer la valeur de counter
" hello world !!! |"
La raison pour laquelle j'ai une verification de la derniere lettre est pour les chaines suivantes:
" " et "hello "
Sans la verification, l'algorithme compte un dernier espace comme un mot.
En p.j., mon implementation en c++ pour ceux qui veulent le tester.
Ma question est: comment calculer la complexite de cet algorithme ?
Si on prend n le nombre de caracteres dans la phrase, la boucle POUR compte pour n
Les pires cas pour les PENDANT QUE sont que la phrase soit composee d'espaces ou de lettres uniquement. MAIS ils ont comme effet de diminuer la longueur de la boucle POUR.
En somme, on aura toujours n iterations, qu'elles soient faites dans la boucle POUR ou PENDANT QUE, et les instructions SI et affectation ne feront qu'augmenter le multiple de n, ce qui ne change pas la complexite.
Ais-je alors raison de dire que l'algorithme a une complexite O(n) ?
Merci
