Discussion :

[simnitch]

Bonjour,

j'aimerais comprendre pourquoi la complexité de l'algorithme de suppression d'un tableau trié (O(n)) n'est pas la même que pour l'algorithme de recherche (O(log n)) alors que pour un tableau non trié, la complexité est la même (O(n)).
Merci d'avance à qui pourra m'éclairer

[ToTo13]

Le problème n'est pas de trouver l'élément O(N), mais après l'avoir supprimé O(1) il faut décaler tout les éléments suivants O(N).

[simnitch]

merci pour ta réponse, donc si je comprends bien quand on dit supprimer un élément c'est supprimer n'importe quel élément, le premier qui vient (et ensuite replacer les autres)?

[DonQuiche]

Ce qu'il veut dire c'est que pour supprimer un élément d'un tableau il faut déplacer les éléments qui viennent après. Il y a donc entre 0 et N éléments à déplacer, soit N/2 en moyenne. Donc O(n).

Si tu veux supprimer "toto" d'une liste de chaînes, d'abord tu fais une recherche, ensuite tu déplaces les éléments après toto. La recherche est en O(n.ln(n)) mais le déplacement est en O(n). La complexité totale est donc en O(n).

[ToTo13]

Si tu veux supprimer "toto" d'une liste de chaînes, d'abord tu fais une recherche, ensuite tu déplaces les éléments après toto. La recherche est en O(n.ln(n)) mais le déplacement est en O(n). La complexité totale est donc en O(n).

Dans une liste, la recherche est en O(N) et le suppression en O(1), donc O(N) au final.

merci pour ta réponse, donc si je comprends bien quand on dit supprimer un élément c'est supprimer n'importe quel élément, le premier qui vient (et ensuite replacer les autres)?

On prend toujours le cas le plus défavorable. Dans le cas d'un tableau, c'est supprimer le premier élément, car il faut ensuite déplacer TOUS les autres éléments.

[DonQuiche]

Dans une liste, la recherche est en O(N)

Liste triée puisque c'était ce dont on parlait.

On prend toujours le cas le plus défavorable. Dans le cas d'un tableau, c'est supprimer le premier élément, car il faut ensuite déplacer TOUS les autres éléments.

Non, on ne prend pas toujours le cas le plus défavorable. En général le plus défavorable et le moyen ont le même comportement asymptotique, soit O(n) ici, donc on ne fait pas de distinction. S'ils ne sont pas identiques, la distinction doit être faîte explicitement.