Livre_silo 30 août 2013 16:32 Page 147
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
147
6 – Notions de complexité et algorithmique sur les tableaux
deux fois plus rapide que l’autre. Cela ne change évidemment rien à l’efficacité intrinsèque
de l’algorithme et ce qui nous intéresse réellement n’est pas le temps précis d’exécution d’un
programme, mais l’ordre de grandeur de ce temps en fonction de la taille des données.
Une dernière notion à considérer est celle du terme dominant dans le temps d’exécution
d’un algorithme. Par exemple, si on a déterminé que ce temps était proportionnel à n
2 +3n,
dès que la taille n des données devient un peu importante, il est connu que le terme 3n
augmente beaucoup moins vite que n
2 : on dit qu’il est négligeable devant ce dernier. Pour
décrire l’efficacité d’un algorithme, seul le terme qui croît le plus vite a donc un intérêt. Par
exemple, ici pour n ⩾ 3, on a n
2 +3n ⩽ 2n
2 ; la quantité n
2 +3n est donc bornée, à partir
d’un certain rang, par le produit de n
2 et d’une constante. On dit alors que la quantité de
n
2 + 3n est « un grand O de n
2 » et on écrira n
2 + 3n = O(n
2 ). De manière générale,
on dira qu’un algorithme a une complexité en O(f (n)) si son coût est, à partir d’un certain
rang, inférieur au produit de f (n) par une constante ¹.
On va ébaucher un rapide inventaire des complexités qu’on pourra être amené à rencontrer.
Il n’est pas possible, sur le plan théorique, de dire combien de temps un algorithme en O(n)
met à s’exécuter pour une valeur particulière de n, puisque deux algorithmes dont les temps
de calcul seraient respectivement n × 10
−9 s et n × 10
9 s seraient tous les deux en O(n),
bien que le rapport de leurs temps d’exécution soit 10
18 . Cependant, on peut donner les
ordres de grandeur des temps d’exécution que l’on rencontre en pratique pour un problème
de taille n = 10
6 sur un ordinateur personnel effectuant un milliard d’opérations par
seconde.
Tableau 6.1 Ordres de grandeur des temps d’exécution
d’un problème de taille 10 6 sur un ordinateur à un milliard d’opérations par seconde
Nom courant
Temps
Remarques
pour n = 10 6
O(1)
temps constant
1 ns
Le temps d’exécution ne dépend pas des données traitées, ce
qui est assez rare !
O(log n) logarithmique
10 ns
En pratique, cela correspond à une exécution quasi instantanée. Bien souvent, à cause du codage binaire de l’information,
c’est en fait la fonction log 2 n qu’on voit apparaître ; mais
comme la complexité est définie à un facteur près, la base du
logarithme n’a pas d’importance.
O(n)
linéaire
1 ms
Le temps d’exécution d’un tel algorithme ne devient supérieur à une minute que pour des données de taille comparable
à celle des mémoires vives disponibles actuellement. Le problème de la gestion de la mémoire se posera donc avant celui
de l’efficacité en temps.
O(n 2 )
quadratique
1/4 h
Cette complexité reste acceptable pour des données de taille
moyenne (n < 10 6 ), mais pas au-delà.
1. Le sens de cette notation sera précisé en cours de mathématiques.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
147
6 – Notions de complexité et algorithmique sur les tableaux
deux fois plus rapide que l’autre. Cela ne change évidemment rien à l’efficacité intrinsèque
de l’algorithme et ce qui nous intéresse réellement n’est pas le temps précis d’exécution d’un
programme, mais l’ordre de grandeur de ce temps en fonction de la taille des données.
Une dernière notion à considérer est celle du terme dominant dans le temps d’exécution
d’un algorithme. Par exemple, si on a déterminé que ce temps était proportionnel à n
2 +3n,
dès que la taille n des données devient un peu importante, il est connu que le terme 3n
augmente beaucoup moins vite que n
2 : on dit qu’il est négligeable devant ce dernier. Pour
décrire l’efficacité d’un algorithme, seul le terme qui croît le plus vite a donc un intérêt. Par
exemple, ici pour n ⩾ 3, on a n
2 +3n ⩽ 2n
2 ; la quantité n
2 +3n est donc bornée, à partir
d’un certain rang, par le produit de n
2 et d’une constante. On dit alors que la quantité de
n
2 + 3n est « un grand O de n
2 » et on écrira n
2 + 3n = O(n
2 ). De manière générale,
on dira qu’un algorithme a une complexité en O(f (n)) si son coût est, à partir d’un certain
rang, inférieur au produit de f (n) par une constante ¹.
On va ébaucher un rapide inventaire des complexités qu’on pourra être amené à rencontrer.
Il n’est pas possible, sur le plan théorique, de dire combien de temps un algorithme en O(n)
met à s’exécuter pour une valeur particulière de n, puisque deux algorithmes dont les temps
de calcul seraient respectivement n × 10
−9 s et n × 10
9 s seraient tous les deux en O(n),
bien que le rapport de leurs temps d’exécution soit 10
18 . Cependant, on peut donner les
ordres de grandeur des temps d’exécution que l’on rencontre en pratique pour un problème
de taille n = 10
6 sur un ordinateur personnel effectuant un milliard d’opérations par
seconde.
Tableau 6.1 Ordres de grandeur des temps d’exécution
d’un problème de taille 10 6 sur un ordinateur à un milliard d’opérations par seconde
Nom courant
Temps
Remarques
pour n = 10 6
O(1)
temps constant
1 ns
Le temps d’exécution ne dépend pas des données traitées, ce
qui est assez rare !
O(log n) logarithmique
10 ns
En pratique, cela correspond à une exécution quasi instantanée. Bien souvent, à cause du codage binaire de l’information,
c’est en fait la fonction log 2 n qu’on voit apparaître ; mais
comme la complexité est définie à un facteur près, la base du
logarithme n’a pas d’importance.
O(n)
linéaire
1 ms
Le temps d’exécution d’un tel algorithme ne devient supérieur à une minute que pour des données de taille comparable
à celle des mémoires vives disponibles actuellement. Le problème de la gestion de la mémoire se posera donc avant celui
de l’efficacité en temps.
O(n 2 )
quadratique
1/4 h
Cette complexité reste acceptable pour des données de taille
moyenne (n < 10 6 ), mais pas au-delà.
1. Le sens de cette notation sera précisé en cours de mathématiques.