Corrigé

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

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.

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.