Complexité algorithme

[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

[fatal_error]

hi,

depile(P) est pas significatif car tu peux imaginer que ca compte pour 1 action
typiquement dépile ca sous entend que tu as une pile (c'est d'ailleurs précisé dans les entrées), et dépiler un element ca revient juste à supprimer le dernier element

Bien sûr dans la vraie vie, si tu fais n'importe quoi et que tu veux le dernier élément alors que tu es obligé d'itérer sur toute une liste, alors c'est plus 1 action qu'il te faut c'est n (parcourir tous les éléments jusqu'au dernier)
mais ici, on a bien une pile, on a accès au dernier élément, et l'enlever ca compte juste pour 1 (ce qui n'est pas significatif)

concernant le booléen il suffit de parler en francais: je boucle tant que ma pile n'est pas vide et que j'ai pas trouvé
ou réciproquement, j'arrete quand j'ai trouvé ou que ma pile est vide (plus d'éléments)

[manysokA]

ah d'accord je comprends mieux, donc je dois résonner pour le meilleur et pire cas avec x = sommet(p)