Algorithme Tous_Differents

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_differents et sortir de la boucle.
  • Renvoyer la valeur de la variable tous_differents.

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).