Complexité Algorithme sur piles
manysoKa
-
manysokA -
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
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
A voir également:
- Complexité Algorithme sur piles
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Algorithme euromillion excel gratuit ✓ - Forum VB / VBA
- Faut il mettre des piles rechargeables dans un téléphone fixe - Forum telephonie fixe
- A quoi sert la pile sur la carte mère - Guide
- Algorithme ajout rapide snapchat ✓ - Forum Snapchat
3 réponses
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
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.
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.