Complexité Algorithme sur piles

Signaler
-
 manysokA -
Bonjour, voici l'énoncé de mon exercice ou je bloque concernant la complexité et les piles.
Pour l'algorithme suivant, déterminez son rôle, les opérations significatives
à considérer et la complexité dans le pire cas et dans le meilleur cas.

début
/* ENTRÉES : Une pile P, un élément x */
/* SORTIE : A DETERMINER */
trouve ← Faux
while not(est_vide(P)) et not trouve) do
si x = sommet(P) alors trouve ← Vrai
else depile(P)
retourner trouve
fin

je ne sais pas si depile(P) est compté comme une opération significatives qui opérent sur la complexité et aussi j'arrive pas à comprendre si on trouve x = sommet(p) l'algorithme s'arrête ou il continue vu qu'il y a l'opérateur booléen ET dans le while cela me semble étrange.

Merci

3 réponses

Messages postés
13093
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
15 novembre 2020
729
Messages postés
243
Date d'inscription
samedi 12 septembre 2020
Statut
Membre
Dernière intervention
13 novembre 2020
13
Salut,
Le but est de retrouver x dans la pile. Il peut ne pas exister, on sort de la boucle quand la pile est vide (le pire cas O(p)) OU on sort de la boucle quand l'élément au sommet de la pile est égal à x (meilleur cas O(1), pire cas O(p-1). Où p est la taille de la pile. p-1 car on dépile APRÈS avoir fait la comparaison.
On reste dans la boucle quand les conditions ci-dessus sont l'inverse et il faut bien utiliser l'opérateur ET parce que si une des conditions est fausse, on sort de la boucle.
Si on avait écrit :
TANT QUE NON vide OU NON trouvé:
Si c'est vide ET qu'on a pas trouvé : boucle infinie
Si on a trouvé ET que ce n'est pas vide : la boucle continue jusqu'à dépiler le tout : perte de perfs.
En ce qui concerne les opé significatives de dépile(pile), je ne pense pas qu'elles sont demandeuses de ressources du moment que le programme sait exactement où se trouve la pile en mémoire, et en faisant l'analogie avec la pile d'assiettes, enlever l'assiette au sommet est facile et rapide.
C’est vraiment beaucoup plus clair, merci grandement à vous pour votre aide !