Podcast
Questions and Answers
Quel est le résultat de l'algorithme Tous_Differents pour la liste L={2, 3, 4, 5}?
Quel est le résultat de l'algorithme Tous_Differents pour la liste L={2, 3, 4, 5}?
Que renvoie l'algorithme Tous_Differents si la liste L a un seul élément?
Que renvoie l'algorithme Tous_Differents si la liste L a un seul élément?
Quelle est la complexité temporelle de l'algorithme Tous_Differents?
Quelle est la complexité temporelle de l'algorithme Tous_Differents?
Dans l'algorithme récursif TDR, quel paramètre est utilisé pour transmettre la sous-liste?
Dans l'algorithme récursif TDR, quel paramètre est utilisé pour transmettre la sous-liste?
Signup and view all the answers
Quel type d'approche est demandé pour l'algorithme Tous_Differents?
Quel type d'approche est demandé pour l'algorithme Tous_Differents?
Signup and view all the answers
Quel résultat retourne l'algorithme TDR pour une liste L={1, 2, 1}?
Quel résultat retourne l'algorithme TDR pour une liste L={1, 2, 1}?
Signup and view all the answers
L'algorithme Tous_Differents renvoie FAUX si:
L'algorithme Tous_Differents renvoie FAUX si:
Signup and view all the answers
Quel peut être un cas d'erreur dans l'algorithme TDR?
Quel peut être un cas d'erreur dans l'algorithme TDR?
Signup and view all the answers
Study Notes
Algorithme Tous_Differents
- L'algorithme Tous_Differents prend en entrée une liste L de N entiers, où N est supérieur à 0.
- L'algorithme renvoie VRAI si tous les éléments de L sont distincts, et FAUX dans le cas contraire.
- L'algorithme doit renvoyer FAUX dès la découverte de deux éléments égaux.
-
Version itérative :
- Initialiser une variable booléenne
tous_differentsà VRAI. - Parcourir la liste L de l'indice 0 à N-1.
- Pour chaque élément de la liste, comparer avec tous les éléments suivants de la liste.
- Si deux éléments sont égaux, attribuer FAUX à la variable
tous_differentset sortir de la boucle. - Renvoyer la valeur de la variable
tous_differents.
- Initialiser une variable booléenne
Complexité de l'algorithme Tous_Differents
- La complexité de l'algorithme itératif est de O(N^2).
- La boucle interne parcourt N-i éléments pour chaque élément i de la liste, soit N-1+N-2+...+1 opérations, ce qui est équivalent à N(N-1)/2, qui appartient à O(N^2).
Version Récursive TDR
- L'algorithme TDR prend en entrée une liste L de N entiers.
- L'algorithme renvoie VRAI si tous les éléments de L sont distincts, et FAUX dans le cas contraire.
-
Version récursive :
- Si N=1, renvoyer VRAI.
- Appeler TDR de manière récursive sur la sous-liste L(1,N) pour vérifier si les éléments de la sous-liste sont distincts.
- Si la sous-liste L(0,N-1) contient des éléments distincts, comparer l'élément L(0) avec tous les éléments suivants de la liste L(1,N).
- Si une correspondance est trouvée, renvoyer FAUX, sinon renvoyer VRAI.
Complexité de l'algorithme TDR
- La complexité de l'algorithme récursif est également de O(N^2).
- À chaque étape récursive, l'algorithme compare le premier élément avec les autres éléments de la sous-liste, ce qui conduit à N comparaisons pour le premier appel récursif, N-1 pour le deuxième, et ainsi de suite.
- Le nombre total de comparaisons est donc N+(N-1)+(N-2)+...+1, ce qui est équivalent à N(N-1)/2, appartenant à O(N^2).
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Découvrez l'algorithme Tous_Differents qui teste si tous les éléments d'une liste d'entiers sont distincts. Ce quiz explore à la fois la version itérative et la complexité de l'algorithme, vous permettant de vous familiariser avec les concepts de base et avancés. Testez vos connaissances sur les algorithmes et leur efficacité.
