Time and Space Complexity

Complexité temporelle :

• Meilleur cas : O(n)
  • Lorsque le tableau est déjà trié, le tri par insertion n'effectue qu'une seule passe pour confirmer l'ordre trié.
• Cas moyen et pire cas : O(n²)
  • Dans les cas moyens et les pires cas, cela prend un temps quadratique car, pour chaque élément, nous pouvons avoir besoin de comparer et de décaler à travers toute la partie triée.

Complexité spatiale :

• O(1)
  • Le tri par insertion est un algorithme « en place », ce qui signifie qu'il ne nécessite pas de mémoire supplémentaire proportionnelle à la taille de l'entrée.
  • L'espace utilisé pour le tri reste constant, quelle que soit la taille de l'entrée.

Résumé :

• Le tri par insertion est efficace pour les petits ensembles de données ou les tableaux presque triés.
• Il est moins adapté aux grands ensembles de données en raison de sa complexité temporelle quadratique.
• La complexité spatiale est constante, ce qui le rend efficace en mémoire pour n'importe quelle taille d'entrée.