Après avoir compris l'utilité des algorithmes, et la manière de les utiliser, une question arrive assez vite: pour deux algorithmes réalisant le même objectif (trier des nombres par exemple), pourquoi utiliser l'un plutôt que l'autre? Il peut y avoir plusieurs critères: je n'ai pensé qu'à celui-là, j'ai trouvé que l'algorithme était plus facile à comprendre, ... Mais souvent on s'intéresse à l'efficacité de l'algorithme qui est un critère plus objectif.

La notion de complexité est introduite pour différencier l'efficacité de deux algorithmes. L'efficacité se définit sur deux plans:

• le temps: si un algorithme est largement plus lent qu'un autre, dans presque tous les cas, alors il vaut mieux utiliser l'autre.
• l'espace: si un algorithme prend beaucoup plus d'espace en mémoire qu'un autre, dans presque tous les cas, alors il vaut mieux prendre l'autre.

Qu'est-ce que la complexité algorithmique?

Après avoir compris l'utilité des algorithmes, et la manière de les utiliser, une question arrive assez vite: pour deux algorithmes réalisant le même objectif (trier des nombres par exemple), pourquoi utiliser l'un plutôt que l'autre? Il peut y avoir plusieurs critères: je n'ai pensé qu'à celui-là, j'ai trouvé que l'algorithme était plus facile à comprendre, ... Mais souvent on s'intéresse à l'efficacité de l'algorithme qui est un critère plus objectif.

La notion de complexité est introduite pour différencier l'efficacité de deux algorithmes. L'efficacité se définit sur deux plans:

• le temps: si un algorithme met largement plus lent qu'un autre, alors il vaut mieux utiliser l'autre.
• l'espace: si un algorithme prend beaucoup plus d'espace en mémoire qu'un autre, alors il vaut mieux prendre l'autre.

Exemple

Imaginons que l'on vous demande de trier tous les articles d'un magasin par prix. Si la méthode que vous utilisez prend 10 années pour trier les articles, et qu'une autre vous prend quelques minutes, vous allez utiliser cette dernière (c'est la complexité temporelle, relative au temps). Maintenant, si votre méthode nécessite de mettre TOUS les articles du magasin dans votre petit caddie, alors qu'il en existe une autre qui nécessite de ne mettre que deux articles à la fois dans le caddie, la méthode prend trop d'espace pour l'espace qui vous est disponible (votre petit caddie) (c'est la complexité spatiale, relative à l'espace). Dans le cadre des activités proposées ici, on se limite à la notion de complexité temporelle.

Il est facile de comprendre qu'il ne suffit pas de trouver une méthode pour qu'elle soit intéressante ... Il faut aussi que ce soit une "bonne" méthode. L'objectif est de donner l'intuition aux élèves, qu'il est possible d'utiliser plusieurs méthodes pour résoudre certains problèmes, mais que ces méthodes ne sont pas toutes équivalentes en termes d'efficacité.

Pour être plus précis sur la notion de complexité, il est nécessaire de parler du nombre d'opérations que l'on va effectuer, par rapport à la taille du problème, c'est-à-dire le nombre d'objets que l'on considère. Par exemple, si l'on a X bouteilles, et que pour obtenir le résultat voulu, on doit:

• soit passer chaque bouteille en revue une seule fois (algorithme 1)
• soit, pour chaque bouteille, regarder toutes les autres bouteilles par rapport à celle-ci (algorithme 2)

On voit directement que pour presque n'importe quelle valeur de X, l'algorithme 1 sera plus rapide que l'algorithme 2 (parce qu'on doit faire beaucoup plus de choses dans l'algorithme 2 que dans l'algorithme 1). On constate également que le nombre d'opérations augmente avec la taille du problème (ici le nombre de bouteilles).

Pourquoi parler de complexité?

L'activité met en lumière qu'il y a souvent plusieurs méthodes pour résoudre un même problème. On le constate fréquemment quand on compare sa méthode à celle de son voisin. Mais parfois, on est si content d'avoir trouvé une méthode/algorithme qu'on en va pas plus loin, qu'on ne poursuit pas le travail pour en trouver une nouvelle. C'est pourtant dommage car si les deux méthodes mènent au même résultat final, certaines peuvent être plus efficaces que d'autres et ce ne sera pas nécessairement celle qu'on a trouvé en premier. Dans la vie quotidienne, ce n'est généralement pas bien grave de ne pas avoir "la meilleure" méthode car on ne le fait qu'une fois. En informatique, c'est différent. Si on utilise un ordinateur, c'est le plus souvent pour l'une des deux raisons suivantes: soit on doit faire la même opération plusieurs fois (des millions de fois), soit on doit effectuer ce travail avec un problème de grande taille (par exemple, si on utilise un ordinateur pour trier, ce n'est pas parce qu'il y a 3 éléments ou 10 éléments à trier, c'est généralement parce qu'il y en a des milliers). Dans les deux cas, vu le grand nombre de répétitions ou la taille du problème, une différence d'efficacité se chiffrera vite en minutes ou en heures.

Comment faire un exercice sur la complexité?

L'idée centrale des exercices est simple. On propose deux méthodes/algorithmes qui ont exactement le MEME objectif, pour pouvoir les comparer. Et on teste quel est le plus efficace. Les opérations sont toujours faire à la main et on compte simplement le nombre d'opérations que l'on effectue. Il ne s'agit pas d'exécuter un problème sur un ordinateur et de "chronométrer" le temps d'exécution.

Pour faciliter les activités, on prend deux contraintes en compte dans le choix des algorithmes:

• on différentie l'efficacité des algorithmes sur base de la complexité temporelle qui est plus intuitive que la complexité spatiale.
• on compare une "très bonne" méthode à une "très mauvaise", pour "forcer le trait" et faciliter la compréhension du concept par les élèves sans rentrer dans des formules mathématiques.

Au delà de la comparaison de deux méthodes, l'objectif est aussi de faire comprendre aux élèves qu'il est possible de déterminer qu'une méthode est meilleure qu'une autre, et qu'il est parfois important de se poser la question.

"Rechercher le nombre" est une activité qui illustre la différence d'efficacité entre deux algorithmes de recherche.