6.1.2 : Pourquoi le changement d'échelle est-il un problème ?
La figure 11 montre le nombre de calculs qu'implique différentes complexités en fonction du nombre d'éléments à traiter.
Figure 11 : Illustration de différentes complexité.
Les problèmes apparaissent lorsque le nombre de calcul devient très grand devant le nombre de calcul qui peut être atteint par un CPU en un temps donnée, environ une seconde dans la figure 12. On remarque qu'un algorithme qui a une complexité exponentielle sera très difficile à utiliser avec $40$ éléments (soit $10^9$ secondes CPU) tandis qu'un algorithme avec une complexité linéaire ($O\left(N\right)$ ) sera très performant.
Figure 12 : Illustration de différentes complexité comparées à la puissance de calcul d'environ une seconde de CPU.