Algorithme
Grâce aux différentes instructions de contrôle qu'on vient de voir, on est maintenant capable d'écrire des programmes beaucoup plus intéressants. Cette dernière section va introduire la notion d'algorithme. Il s'agit d'un processus, d'une séquence finie d'instructions à faire exécuter par un humain, une machine... pour résoudre un problème. Le mot vient de l'astronome et mathématicien Perse Al-Khwārizmī qui écrivit au IXe siècle un ouvrage sur la résolution systématique des équations linéaires et quadratiques.
L'algorithme définit donc les opérations à effectuer. Ensuite, il faut le mettre en œuvre en écrivant ces opérations dans un langage de programmation. Cette mise en œuvre est appelée implémentation.
Algorithme et implémentation
Il y a plusieurs manières de décrire un algorithme. La façon la plus courante est d'utiliser du pseudo-code, qui est une description informelle et compacte d'algorithmes, destinée aux êtres humains. Il s'agit de code ressemblant à un programme informatique pour des opérations élémentaires, mais qui peut être agrémenté avec du texte en langue naturelle ou des symboles mathématiques pour décrire les opérations moins élémentaires.
Voyons comment décrire un algorithme en partant d'un exemple qui permet de trouver le plus grand entier entre deux entiers (algorithme 1). Il n'y a pas de notation unique pour le pseudo-code, mais certaines notions de base sont toujours présentes : variables, affectation, condition if-else, boucle while et for.
La première chose à définir sont les entrées et sorties. Les entrées sont les valeurs qu'il faut fournir à l'algorithme, à savoir les données dont il a besoin pour résoudre le problème. Les sorties sont les valeurs que l'algorithme va produire, à savoir les résultats qui sont les solutions du problème qu'il résout. Dans notre cas, il y a deux entrées qui sont les entiers $a$ et $b$ et une sortie qui est le plus grand parmi eux. Vient ensuite l'algorithme à proprement parler. On utilise une instruction if-else pour vérifier si la valeur de $a$ est plus grande que celle de $b$. Si c'est le cas, le résultat de l'algorithme est $a$, ce qu'on note par return $a$ qui signale que l'algorithme est terminé et que le résultat est $a$.
Une fois un algorithme trouvé, il faut l'implémenter pour pouvoir l'utiliser. Pour traduire un algorithme en un programme Java, il faut écrire un programme et donc tout d'abord définir une classe et une méthode main. Ensuite, on va déclarer et initialiser autant de variables qu'il y a d'entrées à l'algorithme. Vient ensuite le cœur de l'algorithme et enfin, les sorties sont affichées à l'écran avec System.out.println. Voici une implémentation de l'algorithme 1 :
Dans ce cas-ci, l'implémentation choisie ressemble très fort à l'algorithme, mais ce n'est pas toujours le cas. Voyons tout de suite un autre exemple. Le problème que l'on veut résoudre consiste à calculer la somme des $n$ premiers entiers positifs. Par exemple, pour $n = 6$, on veut calculer la valeur de la somme $1 + 2 + 3 + 4 + 5 + 6$, c'est-à-dire $21$. L'algorithme 2 présente une possibilité pour résoudre ce problème. La flèche $\gets$ représente l'affectation d'une valeur à une variable.
On peut implémenter cet algorithme de manière assez directe en utilisant la boucle while. Une autre manière de faire, plus élégante étant donné qu'on connait le nombre total d'itérations à faire, est d'utiliser une boucle for :
Complexité temporelle
Pour résoudre un problème, il existe la plupart du temps plusieurs algorithmes possibles. Lorsqu'on a plusieurs choix, lequel faire ? Il faut établir un critère qui permette de classer les algorithmes. Un critère souvent utilisé en pratique est la complexité temporelle. Celle-ci mesure le temps que va prendre l'algorithme pour s'exécuter et résoudre le problème. Le temps n'est pas mesuré en terme de secondes ou minutes mais plutôt par le nombre d'opérations élémentaires (affectation, comparaison...) nécessaires en fonction de la taille du problème. La taille d'un problème est une mesure de la taille des données fournies à l'algorithme.
Pour comprendre, prenons un nouvel exemple. L'algorithme 3 permet de tester si un nombre entier positif $n > 1$ est premier ou non. Pour rappel, un nombre est premier s'il possède exactement deux diviseurs, à savoir $1$ et par lui-même. Le principe de l'algorithme est de tenter de diviser $n$ par tous les entiers compris entre $2$ et $n - 1$. Si $n$ est divisible par un des ces entiers, c'est qu'il n'est pas premier. Sinon, on sait qu'il s'agit d'un nombre premier.
Deux choses sont à remarquer à propos de cet algorithme. Tout d'abord, cette fois-ci, on a utilisé une boucle for pour les entiers $i$ de $2$ à $n - 1$. Ensuite, en ligne 3, on a une condition exprimée en français. Ceci est tout à fait autorisé puisqu'on est au niveau de l'algorithme. L'important est que la condition soit exprimée de manière claire et non-ambigüe, de sorte qu'on puisse l'implémenter (pour rappel, on peut implémenter un tel test en Java avec l'opérateur modulo).
La complexité de cet algorithme est d'ordre $n$. C'est-à-dire que pour tester si un nombre entier positif $n$ est premier ou non, il faudra dans le pire des cas faire $n$ opérations élémentaires. On dit que c'est un algorithme de complexité $\mathcal{O}(n)$. La notation big-O ($\mathcal{O}$) donne la complexité temporelle d'un algorithme comme une fonction mathématique dépendant de la taille du problème. Un algorithme en $\mathcal{O}(n)$ est dit linéaire. Voici une implémentation possible pour cet algorithme :
Notez que la complexité temporelle donne le nombre d'opérations élémentaires dans le pire des cas; dans notre exemple, il s'agit du cas où le nombre $n$ est effectivement premier. Pour comprendre ça, prenons par exemple le nombre 98 762 534. Il n'est pas premier et on s'en rend compte dès le début puisqu'il est divisible par 2, mais notre implémentation va encore tester tous les $i$ jusque 98 762 534. Une solution est d'utiliser l'instruction break dans le bloc if. Pourriez-vous proposer une solution sans instruction de branchement ? Un petit indice : regardez du côté de la condition du if. Même avec ce changement, le programme reste en $\mathcal{O}(n)$ puisque dans le pire des cas, il faudra toujours $n$ opérations élémentaires.
On peut obtenir un algorithme qui a une complexité temporelle moindre. On se rend compte qu'il ne faut pas tester tous les entiers compris entre 2 et $n$. En effet, il suffit de tester ceux compris entre 2 et $\frac{n}{2}$. Dans le pire des cas, il faudra donc $\frac{n}{2}$ opérations élémentaires pour vérifier si un nombre est premier. Avec cette modification, on obtient donc un algorithme en $\mathcal{O}(1/2n)$, ce qui est équivalent (à une constante près) à $\mathcal{O}(n)$. L'algorithme est un peu plus efficace, mais seulement à une constante près. L'ordre de grandeur ne change pas, l'algorithme reste linéaire et c'est pourquoi dans la notation big-O, on ne garde que le terme de degré le plus élevé et on ignore les constantes. La figure 24 donne les différents types de complexité les plus courants.
| Notation | Type |
|---|---|
| $\mathcal{O}(1)$ | constante (ne dépend pas de la taille du problème) |
| $\mathcal{O}(\log n)$ | logarithmique |
| $\mathcal{O}(n)$ | linéaire |
| $\mathcal{O}(n \log n)$ | quasi-linéaire |
| $\mathcal{O}(n^2)$ | quadratique |
| $\mathcal{O}(n^3)$ | cubique |
| $\mathcal{O}(n^p)$ | polynomial |
| $\mathcal{O}(n^{\log n})$ | quasi-polynomiale |
| $\mathcal{O}(2^n)$ | exponentielle |
| $\mathcal{O}(n!)$ | factorielle |
Pour résumer, la notation big-O donne l'ordre de grandeur de la complexité temporelle dans le pire des cas. On ignore donc toute constante, qui peut pourtant influer le temps d'exécution effectif.