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

• Meilleur cas : La complexité dans le scénario où l’algorithme fonctionne de manière optimale.
• Pire cas : La complexité dans le scénario où l’algorithme prend le plus de temps possible pour traiter une entrée.
• Cas moyen : La complexité dans le scénario moyen, basé sur une distribution statistique des entrées possibles.

Le « cas null » n’est pas un terme standard utilisé dans la théorie de la complexité.

Explication :

• Lors de la recherche binaire, on trouve la position d’insertion en O(log n), ce qui est plus rapide que la recherche linéaire, mais une fois la position trouvée, il faut toujours déplacer les éléments à droite de cette position pour insérer l’élément au bon endroit. Cela prend O(n) dans le pire des cas.
• Donc, même avec la recherche binaire, le tri par insertion nécessite toujours O(n²) pour déplacer les éléments dans le pire des cas, ce qui reste sa complexité temporelle en O(n²).

A: for(i = 0; i < n; i++) Cette boucle s'exécute n fois, donc la complexité est O(n).

B: for(i = 0; i < n; i += 2) Cette boucle incrémente i de 2 à chaque itération. Cela signifie qu'elle s'exécutera environ n / 2 fois, donc la complexité est toujours O(n). Cependant, elle effectuera la moitié du nombre d'itérations de la boucle précédente, mais en termes de complexité, cela reste O(n).

C: for(i = 1; i < n; i *= 2) Cette boucle double i à chaque itération. Elle s'exécute jusqu'à ce que i atteigne n, donc le nombre d'itérations est de l'ordre de log₂(n). La complexité est donc O(log n), ce qui est beaucoup plus efficace que O(n) pour de grandes valeurs de n.

D: for(i = n; i < -1; i /= 2) Cette boucle divise i par 2 à chaque itération. Elle commence avec i = n et continue tant que i est supérieur ou égal à -1. Cela signifie qu'elle s'exécute aussi en O(log n), car i est divisé par 2 à chaque itération, mais la boucle ne sera probablement pas exécutée du tout si n est positif, car la condition i < -1 ne sera jamais vraie. En pratique, cette boucle ne s'exécute pas.

Conclusion: La boucle la plus efficace est C (for(i = 1; i < n; i *= 2)), avec une complexité de O(log n), car elle effectue beaucoup moins d'itérations que les autres boucles qui ont une complexité de O(n).

Ainsi, X sera généralement plus efficace que Y pour les grandes entrées, mais pour les petites entrées, cela pourrait ne pas être le cas.

Cela montre que log(n!) est asymptotiquement équivalent à Θ(n log n), car le terme -n devient négligeable par rapport à n log n à grande échelle. Par conséquent, log(n!) = Θ(n * log n) est valide.

• Ils permettent un accès rapide aux éléments par index (O(1)), ce qui est avantageux lorsque la taille des données ne change pas fréquemment.
• Les tableaux ont une taille fixe, donc ils ne sont pas idéaux pour des collections où les données changent fréquemment ou dont la taille varie de manière dynamique (ce qui est plus adapté aux structures comme les listes chaînées).

En revanche, les tableaux ne sont pas bien adaptés pour des données dont la structure change fréquemment (ajout, suppression d'éléments, etc.), car ces opérations peuvent être coûteuses (par exemple, O(n) dans le pire des cas pour l'ajout ou la suppression d'un élément dans un tableau).

Donc, les tableaux sont plus efficaces pour des données relativement permanentes, mais pas pour des collections dynamiques.