Mesurer le temps d’exécution

• Nécessite d’exécuter le programme
• Dépend du matériel, du langage de programmation, des autres processus en cours…

Quelque chose de plus abstrait : la complexité

• Nombre d’opérations en fonction de la taille de l’entrée $n$
• On utilise la notation $O(\cdot)$, ex., $O(n)$, $O(n^2)$, $O(n!)$

$\rightarrow$ Indépendant du matériel, du langage de programmation…

$\rightarrow$ Ne nécessite pas d’exécuter le programme

• Exemples – DFS/DFS : $O(|E|)$ ; Dijkstra : $O(|E| + |V| \cdot log(|V|))$

La complexité d’un problème est la complexité minimale des algorithmes qui résolvent ce problème

• Classes d’équivalence entre algorithmes et problèmes
• Dijkstra, BFS, DFS sont des algorithmes polynomiaux pour trouver des chemins (problèmes de la classe P)
• Certains problèmes ne peuvent pas être résolus par un algorithme polynomial connu, ex., le problème du voyageur de commerce (problème NP-complet)

Trouver le chemin le plus court qui passe par tous les emplacements

Trouver le chemin le plus court qui passe par tous les sommets d’un graphe complet

• Note – Cela revient à effectuer un DFS par branche

• Le nombre de branches sautées dépend de la qualité des premières explorées
• Cela ne change pas la complexité (dans le pire cas)

• Les algorithmes peuvent être comparés selon leur complexité

• La complexité d’un problème est déterminée par le meilleur algorithme pour le résoudre

• Il existe des problèmes très difficiles à résoudre, comme le TSP

• Ces problèmes ne peuvent être résolus qu’en testant toutes les solutions possibles