Si vous savez que les éléments d'une liste sont presque triés, quel type de tri parmi les tris suivants allez-vous utiliser?

Trouver l'ordre asymptotique de l'équation de récurrence suivante:

Un programmeur décide de modifier le tri rapide de la manière suivante. Au lieu de prendre un seul pivot à chaque niveau de récursivité qui divise le tableau en deux parties, une partie dont les valeurs des éléments sont plus petites que le pivot et une autre plus grandes que le pivot, il prend deux pivots p₁ et p₂ où p₁ < p₂. 

Ainsi le tableau sera divisé en trois parties: une partie dont les valeurs des éléments sont plus petites que p_1, une autre partie où les valeurs des éléments sont entre p₁ et p₂ et, finalement une partie où les valeurs des éléments sont plus grandes que p₂.

Quel serait l'ordre de ce nouvel algorithme dans le meilleur des cas?

Trouver l'ordre asymptotique de l'équation de récurrence suivante:

Trouver l'ordre asymptotique de l'équation de récurrence suivante:

Considérez les tris suivants:

• tri par insertion
• tri par fusion
• tri rapide

Algorithmes de tri

Étant donné une séquence d'étapes intermédiaires, vous devez indiquez quel algorithme de tri a été utilisé pour trier la séquence 10,25,20,24,28,18,27,17,19,12,16,13.

Les étapes intermédiaires sont présentés dans l'ordre mais ne sont pas nécessairement consécutives.  

Notez que chaque algorithme de tri apparaît qu'une seule fois.   

Donnez l'ordre de l'algorithme suivant:

Un algorithme en O(n!) est plus rapide qu'un algorithme en O(2ⁿ).

Un algorithme met 1 seconde pour traiter une entrée de taille n=1000 et 4 secondes pour une entrée de taille 2000. Quelle est la complexité probable de l'algorithme?