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 six = L[0]
vautval
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 deL2
à 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 deL[:i]
aux valeurs différentes deval
. La restriction deL[:i+1]
aux valeurs différentes deval
est alors soit égal àL2
siL[i] = val
soitL2 + L[i]
sinon. C'est exactement ce que vautL2'
.
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.