Corrigé

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

• la création d'une liste vide se fait en $\mathcal{O}(1)$ opérations,
• l'ajout d'un élément en fin de liste se fait en $\mathcal{O}(1)$ opérations,
• lire un élément d'une liste se fait en $\mathcal{O}(1)$ opérations.

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ù :

• A est le nombre de fois où l'on rentre dans la boucle tant que : $\mathcal{O}(len(L))$
• B est la complexité maximale de l'algorithme de la question 1 : $\mathcal{O}(len(L))$

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 :

• $L2 = [v_1, \dots, v_i]$.

• L vaut la restriction de L initiale aux valeurs différentes de $v_1$ jusqu'à $v_i$.

• initialisation : comme $v_1= L[0]$ notre invariant est vrai puisque l'algorithme 1 rendra la restriction de L initiale aux éléments différents de $v_1$.

• récurrence : On suppose la propriété vraie à la fin de l'itération $i$. Au début de l'itération $i+1$, on a par hypothèse de récurrence que $L2 = [v_1, \dots, v_i]$ et que L vaut la restriction de la liste L initiale aux valeurs différentes de $v_1$ jusqu'à $v_i$. Donc $L[0] = v_{i+1}$ et tout se passe comme à la 1ère 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)))$