S'il existe un choix d'algorithmes de complexités temporelles différentes, quand serait-il plus intéressant de choisir un Big-O "pire" , tel que choisir O (n) au lieu de O (log n) .
3 Réponses :
Big O signifie limiter , infiniment de nombreuses opérations lorsque notre code fonctionne avec un nombre fini d’opérations (donc Big O est une approximation). Comparez deux complexités temporelles:
t ~ 1e100 * N t ~ N * N
Le deuxième algorithme (ayant une complexité temporelle plus faible - N au carré) est préférable et plus rapide pour l'entrée du monde réel.
Toute notation asymptotique, décrit comment un certain algorithme se comporte après qu'une certaine taille de l'entrée ( n> n_0 ) est atteinte.
Ce qui n'est généralement pas décrit, c'est tout terme multiplicatif constant supplémentaire qui pourrait être présent (ainsi que d'autres termes négligeables, par exemple n ^ 2 + n est de classe O (n ^ 2) ).
Par exemple, deux algorithmes de complexité de calcul 2 * n et 3 * n seraient sur la même classe O (n) , tandis qu'un algorithme 2 * n ^ 2 serait dans le O (n ^ 2) . Maintenant, pour des entrées suffisamment petites ( n = 1 dans cet exemple), le 2 * n ^ 2 s’exécuterait plus efficacement que le 3 * n algorithme.
Cela pourrait également être vrai pour O (n) par rapport à O (log (n)) (ou toute autre) complexité de calcul.
La complexité ne vous dit rien sur les performances, il ne suffit donc pas de connaître la complexité pour décider si une approche vaut plus qu'une autre. Pour savoir si une approche est meilleure qu'une autre dans une situation donnée (c'est-à-dire pour une taille de problème donnée), le benchmarking est la voie à suivre. Une fois que vous avez comparé les différentes approches, la complexité peut vous aider à prévoir comment les choses évolueront lorsque le problème s'agrandit.
Connaître la complexité de vos algorithmes peut être très utile - par exemple - en traitement d'image:
Imaginez que vous ayez deux filtres différents donnant des résultats très similaires sur une image 2D, l'un étant plus rapide que l'autre pour les images "normales" (certains mégapixels par exemple). Comment vont-ils se comporter si vous les appliquez à des images 3D (c'est-à-dire que se passe-t-il si la taille du problème est de gigapixels à la place)? Connaître la complexité ET avoir un benchmark de référence peut vous aider à prévoir le filtre qui vaudra la peine d'être utilisé, mais à la fin ... vous pourrez toujours comparer les deux solutions pour vous en assurer.