Algorithmique (14/14) - Complexité des algorithmes

Bonjour à tous et bienvenue dans cette nouvelle leçon d'algorithmique. Aujourd'hui, nous allons traiter la complexité. Imaginons que pour résoudre un problème informatique, votre collègue et vous avez décidé de proposer chacun sa version d'algorithme. Cependant, seule la version la plus efficace parmi les deux sera retenue. La question qui se pose est la suivante: qu'est-ce qui fait dire qu'un algorithme est plus efficace qu'un autre? Avant de pencher sur la question, il faut se mettre en tête la chose suivante: pour comparer des algorithmes afin de décider lequel d'entre eux est le meilleur, il faut déjà que ces derniers soient fonctionnels. Autrement dit, si par hasard un algorithme vous semble plus facile à implémenter en programme par rapport aux autres, mais qu'il ne donne pas les résultats attendus, alors il doit être écarté, car le but même d'un algorithme qui consiste à décrire la solution du problème posé n'est pas satisfait dans ce cas. Maintenant, si les 2 algorithmes proposés sont fonctionnels et donnent les résultats espérés, Alors on pourrait envisager de les comparer pour en sélectionner le plus efficace et le plus performant. Pour juger des performances d'un algorithme, on s'intéresse à la quantité de ressources que celui-ci demande pour son exécution. Ces ressources sont le temps et l'espace. Le temps représente une estimation de la durée totale nécessaire à l'exécution de l'algorithme et l'espace fait allusion aux ressources matérielles qui sont mises à disposition de l'algorithme au moment de son exécution, comme la quantité de la mémoire ou les ressources allouées par le microprocesseur, etc. Cependant, le temps d'exécution de l'algorithme constitue la ressource la plus significative qu'il faut quantifier, on parle alors de complexité en temps. Par conséquent, pour évaluer les performances d'un algorithme on tente de calculer sa complexité, et plus particulièrement la complexité en temps. Moins la complexité est importante, plus l'algorithme est performant, ce qui signifie qu'il s'exécutera plus rapidement. Comme vous l'aurez probablement deviné, un ordinateur plus puissant mettra moins de temps à exécuter un algorithme. Cependant, pour évaluer la complexité d'un algorithme on fait abstraction de la puissance de calcul qui peut varier d'un ordinateur à un autre, et on essaie plutôt de la calculer de manière plus générale. On parle alors de complexité asymptotique. Autrement dit, on ne cherche pas à calculer le temps exact que mettra l'algorithme à s'exécuter, mais une approximation plus générale de ce temps-là. Mieux encore, ce n'est même pas le temps proprement dit que l'on cherche à estimer, mais une approximation du nombre d'opérations qui seront menées lors de l'exécution de l'algorithme, De cette manière, les performances de l'ordinateur qui exécute l'algorithme n'ont aucun impact sur le calcul de la complexité. Pour calculer la complexité en tant qu'approximation de la fonction du temps, on utilise la notation grand O ou O majuscule. Cette notation donne une idée plus générale sur le nombre d'opérations significatives qui doivent être menées afin d'exécuter l'algorithme au complet. Autrement dit, on ne considère pas les instructions dans un algorithme comme étant des opérations individuelles, mais peuvent constituer une seule et unique opération. Prenons cet algorithme. Dans ce cas, on demande à l'utilisateur de saisir son nom puis on récupère ce dernier. En tout, nous avons 2 instructions, mais en termes de complexité on parle d'une seule opération. Donc la complexité dans cet algorithme vaut 1, que l'on note O. On parle alors de complexité constante. Modifions un peu cet algorithme. Dans ce cas, nous avons ajouté 2 autres opérations. En effet, on demande à l'utilisateur de saisir son prénom puis son email. Peut donc en déduire que l'on a effectué 3 opérations. Cependant, le nombre 3 qui est considéré dans ce cas comme étant un facteur multiplicatif n'est pas considéré au moment du calcul de la complexité. Autrement dit, la complexité de cet algorithme vaut toujours O. Donc, si le nombre d'opérations à exécuter dans un algorithme est constant, c'est-à-dire qu'il est le même à chaque fois que l'on exécute celui-ci, alors sa complexité vaut toujours O. Maintenant prenons cet algorithme. Il s'agit là d'un algorithme qui permet de rechercher séquentiellement un élément dans un tableau. Le traitement le plus conséquent dans cet algorithme est sans doute le traitement itératif assuré par la boucle Pour. En effet, dans cette boucle on parcourt le tableau élément par élément en comparant l'élément courant avec l'élément recherché. Si l'élément recherché est trouvé, alors on met fin à la boucle prématurément à l'aide de l'instruction Break. Donc, si par hasard l'élément recherché figure dans la première case du tableau, alors une seule itération de la boucle sera exécutée. Et si cet élément-là se trouve dans la dernière case, alors on aura exécuté autant d'itérations qu'il y a de cases dans le tableau. Dans ce genre de situation, on évalue la complexité du pire des cas, autrement dit, le cas où l'élément recherché figure dans la dernière cellule. Par conséquent, la complexité de cet algorithme vaut O. n dans ce cas représente l'ordre de grandeur du nombre d'opérations à exécuter et qui est équivalent au nombre d'itérations dans la boucle. On parle alors de complexité linéaire. Maintenant, imaginez que l'on a cet algorithme. Rien de sorcier là non plus, il s'agit en fait d'un algorithme qui permet de calculer la somme des éléments de chacun des 2 tableaux d'entiers Tab1 et Tab2. Bien entendu, j'ai fixé le nombre d'éléments des 2 tableaux à 100, mais on peut envisager un nombre dynamique qui peut changer à chaque exécution et qui peut être beaucoup plus grand. En tout cas, dans cet exemple nous avons 2 instructions itératives qui se succèdent, alors on peut estimer la grandeur de la complexité comme étant égale à 2n, vu qu'on a 2 boucles. Mais comme je l'ai mentionné il y a quelques instants, les facteurs multiplicatifs sont ignorés lors du calcul de la complexité. Par conséquent, la complexité de cet algorithme vaut aussi O. Regardons maintenant cet algorithme. Ici, nous procédons à toutes les multiplications possibles entre les éléments du premier tableau et du deuxième tableau. Dans ce cas, nous avons imbriqué 2 boucles Pour l'une dans l'autre. Alors, l'ordre de grandeur du nombre d'opérations à exécuter vaut le nombre d'itérations de la grande boucle multiplié par le nombre d'itérations de la petite boucle. Donc la complexité dans ce cas vaut O ou O que l'on appelle complexité quadratique. Et si on prend l'algorithme de la recherche dichotomique dans un tableau trié et que nous avons déjà traité dans un exercice, alors vous vous rendez compte que l'intervalle de recherche rétrécit de moitié à chaque itération, donc le nombre d'opérations à exécuter dans le pire des cas vaut log, par conséquent la complexité vaut O) que l'on appelle complexité logarithmique. De la même manière, dans certains algorithmes on peut se retrouver avec la complexité cubique, factorielle ou quasi-linéaire, etc. À la fin, bien que le fait de réduire la complexité en temps d'un algorithme rend ce dernier plus rapide, il serait également bénéfique d'envisager d'optimiser l'algorithme en réduisant les ressources matérielles allouées comme la mémoire et les tâches du processeur. Merci pour votre attention et à la vidéo prochaine.