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 d'une valeur

Nom : Algorithme-1
Entrées :
    val : une valeur
    L : une liste de n valeurs
Programme :
    création d’une liste L2 vide
    pour chaque élément x de L :
        si x ≠ val :
            ajoute x à la fin de L2
    Retour L2

complexité de l'algorithme 1

On considère que la création d'une liste et l'ajout d'un élément en fin de liste sont des opérations en $\mathcal{O}(1)$ opérations. De là, notre algorithme est en $\mathcal{O}(n)$ opérations où $n$ st la taille de la liste L.

preuve de l'algorithme 1

L'algorithme va parcourir la liste et ajouter un à un à L2 tous les éléments de L différents de val. Notre invariant de boucle pourrait donc être : à la fin de l'itération $i$ L2 est la restriction de L[:i] aux valeurs différentes de val.

• initialisation : à la fin de la première itération ($i=1$), L2 est vide si x = L[0] vaut val et vaut [x] sinon. Ok.
• récurrence : On suppose la propriété vraie à la fin de l'itération $i$. L'itération $i+1$ a considéré $x = L[i]$. Notons L2' la valeur de L2 à la fin de l'itération $i+1$. Au début de l'itération $i+1$, par hypothèse de récurrence, L2 est la restriction de L[:i] aux valeurs différentes de val. La restriction de L[:i+1] aux valeurs différentes de val est alors soit égal à L2 si L[i] = val soit L2 + L[i] sinon. C'est exactement ce que vaut L2'.

A la fin de la dernière itération, L2 vaut donc la restriction de L[:n] (avec n = len(L)) aux valeurs différentes de val.

Suppression d'une valeur in-place

On échange l'élément à supprimer avec le dernier de la liste puis on pop.

Nom : Algorithme-1'
Entrées :
    val : une valeur
    L : une liste de n valeurs
Programme :
    i = 0
    k = n - 1
    tant que i <= k:
    si L[i] == val
        échange L[i] et L[k]
        supprime le dernier élément de L
        k = k - 1
    sinon:
        i = i + 1

La preuve et la complexité de l'algorithme 1' est identique à celle de l'algorithme 1.