Complexité temporelle

La complexité temporelle modélise la croissance du nombre d'opérations d'un algorithme selon une mesure d'entrée déclarée. Elle prédit le changement d'échelle sous un modèle de coût abstrait ; elle ne remplace pas la mesure d'une implémentation sur du matériel et des données représentatifs.

Préciser le modèle

Avant de simplifier une borne, déterminez :

• ce que signifie $n$, ou si plusieurs paramètres comme $V$ et $E$ interviennent ;
• les opérations considérées comme étant en temps constant ;
• si le comportement étudié est celui du pire cas, du cas moyen, de l'espérance, de l'amortissement ou de la sensibilité à la sortie ;
• les hypothèses sur la représentation, l'ordre, le hasard et la taille binaire des nombres.

Par exemple, BFS est en $O(V+E)$ avec des listes d'adjacence, et non simplement en $O(V)$. De même, un algorithme polynomial en une capacité numérique peut être pseudo-polynomial par rapport à la longueur de l'entrée encodée.

Notation asymptotique

• $T(n)=O(f(n))$ : une borne supérieure à partir d'un certain rang.
• $T(n)=\Omega(f(n))$ : une borne inférieure à partir d'un certain rang.
• $T(n)=\Theta(f(n))$ : des bornes supérieure et inférieure qui coïncident.

Le grand O n'est pas synonyme de « pire cas ». L'analyse des cas et la notation asymptotique sont distinctes : on peut annoncer un temps espéré en $\Theta(n\log n)$ ou une borne du pire cas en $O(n^2)$.

Schémas d'analyse

• Les phases consécutives s'additionnent ; le terme dominant en croissance contrôle souvent le résultat.
• Les travaux imbriqués ne se multiplient que si le coût interne s'applique à chaque étape externe.
• Réduire un intervalle de moitié ou le doubler produit généralement une profondeur logarithmique.
• Les algorithmes récursifs exigent une récurrence ou un argument de comptabilité.
• Une énumération doit inclure la taille de la sortie : produire $n!$ permutations ne peut prendre un temps total inférieur à l'ordre factoriel.

Classes de croissance courantes

$$1 < \log n < n < n\log n < n^2 < c^n < n! \qquad(c>1)$$

Cet ordre est asymptotique. Les constantes, le comportement du cache, la vectorisation, les allocations et la distribution des entrées déterminent encore les points de bascule pratiques.

Quantificateurs et comptes concrets

Pour des fonctions finalement non négatives, $T(n)=O(f(n))$ signifie qu’il existe des constantes $c>0$ et $n_0$ telles que $T(n)\leq c f(n)$ pour tout $n\geq n_0$. Elles ne doivent pas croître avec $n$. Pour $T(n)=3n^2+2n+7$ et $n\geq1$, on a $3n^2\leq T(n)\leq12n^2$, prouvant $\Theta(n^2)$.

def pair_count(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count += 1
    return count

assert pair_count(4) == 6
assert pair_count(0) == 0

Pour un entier n non négatif, le corps interne s’exécute $\sum_{i=0}^{n-1}i=n(n-1)/2$ fois. Une variable interne qui double depuis 1 tant qu’elle reste sous n effectue plutôt $\lceil\log_2 n\rceil$ itérations pour $n\geq1$. Répéter cette boucle entière à chacune de $n$ étapes externes coûte $\Theta(n\log n)$, et non $\Theta(n^2)$ du seul fait de l’imbrication.

Meilleur, pire, moyen, espéré, amorti

Le meilleur et le pire cas prennent le minimum et le maximum sur les entrées de même taille. Le cas moyen prend l’espérance sous une distribution d’entrée déclarée. Le coût espéré randomisé moyenne les choix aléatoires de l’algorithme, éventuellement pour toute entrée fixe. Les sources de hasard sont différentes.

Le coût amorti ne demande aucun modèle probabiliste : il borne le coût total d’une suite d’opérations. Un tableau dynamique initialement vide, de capacité initiale un, double lorsqu’il est plein. Sur $m$ ajouts, les copies aux agrandissements coûtent $1+2+4+\cdots<2m$, et les nouvelles écritures $m$. Le total est $O(m)$, donc un ajout coûte $O(1)$ amorti, même si un agrandissement coûte $\Theta(m)$. Pour huit ajouts : $1+2+4=7$ emplacements copiés et huit écritures nouvelles. Augmenter la capacité d’une seule place copierait $1+2+\cdots+(m-1)$ emplacements, perdant la borne amortie constante. On compte ici des opérations sur références, pas des calculs entiers de taille arbitraire, des comparaisons coûteuses ou la latence réelle.

Source

• MIT OpenCourseWare : complexité asymptotique

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.