Paradigmes pour l'analyse de la complexité des algorithmes

L'analyse du pire et du cas moyen sont des mesures bien connues de la complexité d'un algorithme. L'analyse lissée récemment est apparue comme un autre paradigme pour expliquer pourquoi certains algorithmes exponentiels dans le pire des cas fonctionnent si bien dans la pratique, par exemple l'algorithme simplex.

Ma question est - existe-t-il d'autres paradigmes pour mesurer la complexité d'un algorithme? Je suis particulièrement intéressé par ceux qui tentent d'expliquer pourquoi certains algorithmes qui ont une mauvaise complexité dans le pire des cas fonctionnent bien dans la pratique.

$n$$k$$n$$k$$k$

$10$$O(2^k (|E|+|V|))$

[1] R. Niedermeier, Invitation aux algorithmes à paramètres fixes. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006.

Il y a une complexité amortie - pourquoi certaines opérations peuvent être coûteuses dans le pire des cas, mais si vous considérez de nombreuses opérations, le coût moyen par opération est bon.

Un exemple classique est une structure de données qui se vide lorsqu'elle est pleine en copiant tous ses éléments dans un certain stockage. L'opération de copie peut être coûteuse, mais elle ne se produit pas souvent - vous devez insérer suffisamment d'éléments dans la structure de données pour la provoquer.