Tu dois savoir
- l'algorithme
- le chemin le plus court à travers l'algorithme
- le plus long chemin à travers l'algorithme
- comment les longueurs de chemin ou le nombre d'itérations varient avec le nombre d'éléments de données traités
- à quoi ressemble un ensemble de données « moyenne ».
La complexité temporelle du meilleur des cas peut être calculée en considérant ce qui arrive au temps d'exécution ou au nombre d'itérations lorsque vous augmentez l'ensemble de données d'1 élément, de 2 éléments, d'un facteur 2, d'un facteur 3. Si le temps d'exécution l'augmentation est linéaire avec le nombre de données, on dit que la complexité temporelle est O(N), c'est-à-dire de l'ordre de N, le nombre de données. Si le temps d'exécution varie comme le carré du nombre d'éléments de données, alors on dit que la complexité temporelle est O(N
2 ). La complexité temporelle peut être d'autres ordres, exponentielle, ou avoir une autre relation avec le nombre d'éléments de données, par exemple, O(N
3/2 ).
La même évaluation de la complexité temporelle peut être effectuée pour les cas les plus défavorables et les cas moyens.