Pour concevoir des logiciels bien optimisés, il est souvent nécessaire de pouvoir distinguer les algorithmes optimaux des algorithmes trop gourmands en ressources. D’où l’entrée en jeu de l’étude de la complexité d’un algorithme, qui devient primordiale pour reconnaître son optimalité dans le monde réel. En d’autres mots, ça permet de prédire le comportement d’un algorithme avec un nombre très élevé de données.
Pour avoir une compréhension de c’est quoi la complexité d’un algorithme, appelez aussi le grand-O (Big-O en anglais), on va imaginer un exemple simple, supposons qu’un algorithme nécessite une seconde pour calculer 10 données, sa complexité est monotone (O(n)) s’il lui faudrait 10 secondes pour finir 100 données. Par contre si c’est un algorithme optimal il lui faudrait moins de temps. Ou inversement si c’est un algorithme gourmand il lui faudrait plus. La complexité permet plus ou moins de prédire ce temps.
À vrai dire, l’étude de la complexité est une méthode mathématique relativement difficile à appréhender à première vue. La principale raison est que cette méthode ne ressemble à aucun domaine mathématique vu auparavant dans le cursus de l’étudiant. On peut grossièrement la qualifier comme un point d’intersection entre le calcul arithmétique et le calcul des limites dans l’analyse mathématique. D’une part, malgré que le but de la méthode soit le calcul du temps nécessaire pour l’exécution en rapport avec les données exercées sur l’algorithme, elle ne va pas faire un calcul arithmétique exacte de ce temps comme on avait vu sur l’exemple, mais elle va plutôt nous fournir une approximation. Et d’autre part la méthode tend à évaluer le temps pour un nombre très grand de données, et s’appuyer sur des procédés mathématiques qui sont similaires au calcul des limites, comme par exemple négliger les fonctions les moins rapides (comme par exemple : 2X2 + 4X +1 tend vers X2). Mais en même temps, ce n’est pas un calcul de limite. La complexité va réellement nous retourner une fonction parmi les fonctions illustrées sur le graphe en haut. Cette fonction va nous donner une estimation de la rapidité en complexité de l’algorithme en rapport avec le nombre de données. La vidéo en bas de la chaîne YouTube du site web éducatif www.freecodecamp.org illustre cette notion de complexité sous format d’un cours de courte durée pour appréhender plus ou moins cette notion du Big-O.