Discussion :

[emna1987]

bonjour
j'ai un exercice qui est le suivant:
on cherche à trier un tableau de n entiers dont seulement p éléments ne sont pas à leur place(si on retire ces p éléments, les n-p restants sont bien dans l'ordre).Quelle est la complexité au pire des cas d'un trie par insertion sur un tel tableau?justifier votre réponse
je suis débutante en algorithme et notion de complexité quelq'un peut me proposer une solution ou me mettre sur le bon chemin pour comprendre la nottion de complexité de trie des tableaux et merci d'avance!!

[DonQuiche]

Bonjour.

Voici les deux questions que tu dois te poser :
* Quel est le coût pour détecter les éléments qui ne sont pas à leur place ?
* Quel est le coût par élément qui n'est pas à sa place ?