La complexité est une notion assez globale qui signifie que le système considéré n’est pas simple ; les composants et leurs relations sont nombreux. Il est donc plus difficile à comprendre, à modéliser et à simuler.

La complexité algorithmique est le coût nécessaire pour exécuter un programme et trouver la solution au problème que l’algorithme est sensé résoudre. Plus un algorithme (ou un programme) est complexe, plus il nécessite de ressources pour arriver à son terme. On distingue habituellement les deux axes de complexité algorithmique suivants :

1. La complexité en temps de calcul qui correspond au nombre d’opérations qu’il faut effectuer ;
2. La complexité en mémoire qui correspond à la quantité de données qu’il faut stocker au maximum.

Le Compromis temps-mémoire correspond à l’idée selon laquelle améliorer la complexité suivant un des axe la détériorera dans l’autre. Par exemple, on peut rendre la recherche dans une base de donnée plus rapide en ajoutant un index mais celui-ci prendra de la place. Le but est alors de choisir le bon compromis en fonction du contexte. Habituellement, on mesure la complexité en fonction de la taille des données et sous la forme d’une fonction qui, à un facteur près, a le même comportement asymptotique…

Estimer la complexité

La complexité d’un algorithme dépends de plusieurs facteurs, difficiles à prendre en compte. La donnée en entrée est la plus importante, et aussi la plus difficile à quantifier ; connaître le nombre exact d’opération est presque équivalent à résoudre le problème. La façon de développer et d’optimiser certaines parties ou instructions change également la donne.

Plutôt qu’avoir le nombre exact d’opération (ou la quantité de mémoire), on s’intéresse à un ordre de grandeur par rapport à la taille de la donnée en entrée. La question, de manière très générale est la suivante :

Si j’augmente la quantité de donnée en entrée, quel est l’impact sur le temps et la mémoire nécessaire pour obtenir une réponse ?

Paradoxalement (ou pas d’ailleurs), bien que ces estimations puissent être qualifiées d’à la louche (cf. NF-UNM-00-001), elle font appel à de réelles définitions et théories mathématiques.

On va donc chercher à comparer cette quantité exacte de ressources nécessaires $f(n)$, inconnue et très compliquée à modéliser, avec des fonctions plus simples $g(n)$. La comparaison se fera pour une taille assez grande ($n > N$) et à un facteur multiplicatif près ($c$). Voici les trois comparaisons usuelles :

1. $f \in O(g)$, borné supérieurement, $f(n) < c . g(n)$,
2. $f \in \Omega(g)$, borné inférieurement, $c . g(n) < f(n)$,
3. $f \in \Theta(g)$, du même ordre de grandeur, $c_1 . g(n) < f(n) < c_2 . g(n)$.

Si vous voulez des définitions plus formelles, je vous conseille ce cours.

Par prudence et pour avoir une certaine garantie de résultat, on utilise plus souvent la première borne $O$ à la seconde $\Omega$. Il est rare de posséder assez d’hypothèses sur les données d’entrée pour avoir une estimation plus fine et le meilleur des cas est souvent bien trop rare pour être utile.

Sauf en cryptographie où il est parfois utile de déterminer des caractéristiques communes aux cas faciles. Pour casser les algos des autres, ou renforcer les siens.

La troisième estimation établi des classes d’équivalence entre algorithmes. On suit un raisonnement similaire pour classer des problèmes et poser des questions comme $P = NP$. Passionnantes mais hors sujet pour aujourd’hui.

Exemple #1 chercher des éléments

Il arrive toujours un moment où on doit gérer et stocker un ensemble d’éléments et y faire ensuite des recherches suivant un critère ou en trouver un en particulier.

L’approche naïve consiste à utiliser un tableau (ou une liste). Ajouter un élément (en fin de tableau ou en début de liste) est instantané : $O(1)$. La recherche implique de le parcourir entièrement et est donc en $O(n)$.

Une approche plus subtile consiste à utiliser un arbre binaire de recherche, équilibré tant qu’à faire. On gagne alors sur la recherche qui est alors en $O(\log n)$ et on perd lors de l’insertion puisqu’elle est plus complexe (il faut trouver la bonne place et rééquilibrer), soit $O(\log n)$.

On retrouve ce type de question d’implémentation lorsqu’on crée un schéma pour une base de données :

Faut-il mettre un index ?

un Administrateur de Base de Donnée

Les index étant des arbres binaires, ils permettent d’accélérer la recherche, mais au détriment de l’insertion, suivant le mode d’accès à la donnée, un index peut aider (ou pas).

Exemple #2, trier des ensembles

L’autre exemple typique consiste à trier des ensembles. C’est l’équivalent de la clause ORDER BY en SQL.

L’approche naïve consiste ici à construire une structure vide puis à y insérer les éléments un par un à la bonne place. On utilise ici $n (n - 1) / 2$ comparaisons, soit une complexité en $O(n^2)$.

Les algorithmes les plus rapide dans un cadre général consistent à diviser le tableau en deux, trier récursivement chaque moitié puis les réunir. La complexité est plus complexe à calculer mais est plus petite : $O(n \log n)$.

Entre les deux, il existe d’autres algorithmes qui utilisent certaines propriétés de l’ensemble pour en améliorer la complexité. Leur complexité peut avoisiner $O(n)$ dans certains cas particulier mais reste entre $O(n \log n)$ et $O(n^2)$ en général.

Exemple d’optimisation pratique

Il y a quelques temps, j’ai eu l’occasion de travailler sur un problème de performance. Globalement, une fonction devant compter des éléments d’un certain type était tellement gourmande que le service web associé pouvait partir en timeout…

De l’avis général, c’était un problème de technologie. La base postgres était forcément obsolète et il fallait mettre tout à jour et passer à du NoSQL. En attendant, un trigger était utilisé pour supprimer les données au delà d’un seuil pour garantir que les fonctions répondent dans les temps… (d’où l’intérêt de les compter…)

La base de donnée était organisée autour d’une table principale, commune à tous les éléments, plus une table par type. Le champ id était commun à toutes les tables et permettait une jointure.

Le problème, c’est que pour compter les éléments d’un type, le code effectuait une jointure LEFT JOIN avec toutes les tables. Et comme ça fait trop de lignes, elles sont filtrées en retirant celles qui n’ont pas d’équivalent dans les autres types (la valeur est null après un LEFT JOIN)…

select count(*)
from global_table as g
left join type1_table as t1 on t1.id = g.id
left join type2_table as t2 on t2.id = g.id
left join type3_table as t3 on t3.id = g.id
left join type4_table as t4 on t4.id = g.id
where
    t1.id is not null and
    t2.id is     null and
    t3.id is     null and
    t4.id is     null
    ;

Une complexité en $O(n^5)$ pour compter des éléments…

L’optimisation a été très simple ; éviter les jointures inutiles en interrogeant uniquement la table nécessaire. La colonne id ayant déjà un index, il n’a pas été nécessaire de l’ajouter.

select count(id) from type1_table ;

Sans l’index, on aurait une complexité en $O(n)$, avec l’index, on est passé à $O(1)$, soit un temps constant (et négligeable) quelle que soit le nombre de données.

Comme quoi, souvent, ça n’est pas un problème de technologie mais d’algorithme 😉.

Et après ?

Les plus férus de complexité algorithmique en matière de sécurité informatique restent encore les cryptographes. La cryptographie moderne repose sur des problèmes réputés difficiles à résoudre. Par exemple, les meilleurs algorithmes pour la factorisation ou le logarithme discret ont une complexité sous exponentielle en $O(n^{\log n})$.

Toujours en cryptographie, cet article ne serait pas complet sans dire deux mots des attaques temporelles. Ici, le but est d’avoir une consommation des ressources constante, quelle que soit la valeur en entrée, et d’éviter ainsi toute fuite d’information (i.e. lors de la comparaison des hachés des mots de passes).

Pour le reste, i.e. la grande majorité des applications, la complexité est plus du ressort de la disponibilité de l’application ; lorsqu’elle doit gérer de grandes quantités de données. Lorsque ces applications deviennent lentes, on parle alors plus de problème de qualité que de sécurité.

Pour moi, la sécurité n’est qu’une étape de plus après la qualité. On ne peut pas vraiment vouloir faire l’un sans l’autre et toutes deux partagent un tableau clinique global qui englobe tout un tas d’indicateurs généralement corrélés. Un logiciel trop lent sera généralement mal écrit et donc plus facilement sujet aux bugs et autres vulnérabilités.

Pour éviter ces déni de services, il est bien plus efficace d’optimiser les applications au niveau conceptuel en choisissant les bonnes structures et les bons algorithmes. Économiser une instruction gagne effectivement un peu de temps mais ça restera moins efficace que de changer l’ordre de grandeur, i.e. en passant de $O(n^2)$ à $O(1)$.