QCM Algorithmes, structures de données et complexité – Partie 7

Explication :

• Tri par fusion a une complexité de O(n log n) dans le pire des cas, ce qui en fait un des algorithmes de tri les plus efficaces en termes de complexité temporelle, même dans le pire des cas.
• Tri à bulles et tri par sélection ont une complexité de O(n²) dans le pire des cas, ce qui les rend moins efficaces pour de grandes entrées.
• Tri rapide a une complexité de O(n log n) dans le cas moyen, mais dans le pire des cas (lorsque la partition choisie est toujours la plus mauvaise), sa complexité peut atteindre O(n²), ce qui le rend moins performant que le tri par fusion dans le pire des cas.

• Recherche binaire est utilisée sur des tableaux triés, et elle consiste à comparer l’élément cible à l’élément du milieu du tableau, puis à éliminer la moitié du tableau à chaque itération, en réduisant ainsi la taille du problème à chaque étape.
• Cette approche donne une complexité logarithmique, c’est-à-dire O(log n), car à chaque itération, la taille du tableau à chercher est divisée par deux.

Par conséquent, la complexité temporelle de l’algorithme de recherche binaire est O(log n).

Lorsque vous effectuez un parcours en ordre (ou in-order traversal) d’un arbre de recherche binaire, vous visitez les nœuds dans l’ordre croissant, c’est-à-dire que vous traversez d’abord le sous-arbre gauche, puis le nœud lui-même, puis le sous-arbre droit. Ce parcours produit donc une liste triée des éléments de l’arbre. Exemple:

Si l’arbre contient les éléments [5, 3, 7, 2, 4, 6, 8], un parcours en ordre produira la liste triée : [2, 3, 4, 5, 6, 7, 8].

Ainsi, le résultat d’un parcours d’un arbre de recherche binaire est toujours une liste triée.

Lors de chaque appel récursif, la taille de n diminue de manière significative : le reste n % m est toujours plus petit que m, ce qui réduit la taille de l’un des deux nombres de manière rapide. En conséquence, le nombre d’appels récursifs est proportionnel à la logarithme du plus petit nombre, ce qui donne une complexité en Θ(log n) dans le pire des cas.

Pourquoi pas les autres réponses ?

• Ω(n) : Ce serait le cas si l’algorithme devait effectuer un grand nombre d’opérations dans le pire des cas, mais ici l’algorithme réduit le problème de façon logarithmique à chaque itération, pas linéairement.
• Θ(log log n) : La réduction est logarithmique, mais pas doublement logarithmique. La complexité est donc Θ(log n), pas Θ(log log n).
• Θ(sqrt(n)) : Cela serait pertinent si l’algorithme effectuait des recherches en divisant la taille de l’entrée par une racine carrée à chaque étape, mais ici ce n’est pas le cas.

Conclusion: Le nombre d’appels récursifs effectués par la fonction est Θ(log n), car l’algorithme d’Euclide divise la taille du problème de manière logarithmique.

L’avantage des listes chaînées par rapport aux tableaux est leur capacité à s’adapter dynamiquement en fonction de l’ajout ou de la suppression d’éléments, car les éléments ne sont pas stockés dans des zones de mémoire contiguës.