Coût d’un algorithme

C'est l'ordre de grandeur du nombre d'opérations arithmétiques ou logiques que doit effectuer un algorithme pour résoudre le problème auquel il est destiné, ce coût donne donc une indication de la rapidité de l'algorithme. Cet ordre de grandeur dépend évidemment de la taille N des données en entrée. On parlera de coût linéaire ou de l'ordre de N, si ce coût est proportionnel à cette taille, de coût quadratique s'il est proportionnel au carré de N. Les algorithmes se classent en deux grands groupes : ceux dont le coût est linéaire, quadratique ou polynomial en fonction de N, et ceux - plus complexes - où le coût est au moins exponentiel en fonction de N. La théorie de la complexité permet d'évaluer de tels coûts.