Corrigé

La structure de donnée utilisée ici est la liste. On considérera que :

Suppression de doublon en conservant l'ordre

Nom : Algorithme-2
Entrées :
    L : une liste de n valeurs
Programme :
    création d’une liste L2 vide
    tant que L est non vide:
        x = L[0]
        ajoute x à la fin de L2
        L = algorithme-1(L, x)
    Retour L2

complexité de l'algorithme 2

Commençons par compter le nombre de fois où la boucle tant que sera exécutée. L est modifiée à chaque fin de boucle L = algorithme-1(L, x) avec x = L[0]. Comme l'algorithme de la question 1 rend la restriction de de L aux valeurs différentes de x, elle va forcément être strictement plus petite (puisque x=L[0] il est forcément dans la liste) : la longueur de la liste diminue strictement à chaque itération, on ne peut y rentrer que la longueur de L initiale fois.

La seule ligne de l'algorithme qui n'est pas de complexité $\mathcal{O}(1)$ est : L = algorithme-1(L, x). Sa complexité est égale à une affectation ($\mathcal{O}(1)$) plus la complexité de l'algorithme de la question 1, qui vaut de l'ordre de la taille de la liste passée en entrée.

Cette taille diminue strictement à chaque itération : on peut utiliser l'astuce du cours pour ne garder que la complexité la plus importante, c'est à dire $\mathcal{O}(len(L))$ avec L la liste initiale.

Notre complexité est donc de l'ordre : $\mathcal{O}(1) + A * (\mathcal{O}(1) + B)$ où :

Notre algorithme est de complexité : $\mathcal{O}(len(L)^2)$

preuve algorithme 2

La liste L contient $k$ valeurs différentes que l'on note $v_1, \dots v_k$ dans l'ordre de la liste (le 1er indice où l'on rencontre $v_i$ est strictement plus petit que le 1er indice où l'on rencontre $v_j$ si $i < j$).

Notre invariant de boucle sera : au bout de la $i$ème itération :

A la fin de l'algorithme, notre invariant est toujours juste : $L2 = [v_1, \dots, v_k]$

Suppression de doublon d'une liste ordonnée

Il suffit de parcourir tous les éléments de L dans l'ordre :

Nom : Algorithme-2'
Entrées :
    L : une liste de n valeurs
Programme :
    création d’une liste L2 contenant le premier élément de L
    pour i allant de 1 à n-1:
        si L[i] != L[i-1]:
            ajoute L[i] à la fin de L2
    Retour L2

complexité de l'algorithme 2'

Clairement en $\mathcal{O}(n)$

preuve de l'algorithme 2'

L'invariant de boucle et sa preuve est identique à celle de la preuve de l'algorithme 2 en tenant compte du fait que L est trié.

Suppression de doublon d'une liste sans ordre

On commence par trier la liste on utilise l'algorithme de la question précédente. Ceci fait passer la complexité de $\mathcal{O}(len(L)^2)$ à $\mathcal{O}(len(L)\log(len(L)))$