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 tri par insertion sur un tel tableau ? Justifier votre réponse.
Je suis débutante en algorithme et notion de complexité. Quelqu'un peut-il me proposer une solution ou me mettre sur le bon chemin pour comprendre la notion de complexité de tri des tableaux ? Merci d'avance !
Partager