Complexité algorithmique

tbowan

4 Juin 2018

Après la Complexité du code, voici quelques explications sur la complexité des algorithmes. Différente mais non moins importante lorsqu'il s'agit d'avoir des applications efficaces.

De quoi parle-t-on ?

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éteriorera 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.

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. Mais 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 comliqué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 usuelles1 :

  1. f ∈ O(g), borné supérieurement, f(n)<c.g(n),
  2. f ∈ Ω(g), borné inférieurement, c.g(n)<f(n),
  3. f ∈ Θ(g), du même ordre de grandeur, c1.g(n)<f(n)<c2.g(n).

Par prudence et pour avoir une certaine garantie de résultat, on utilise plus souvent la première borne O à la seconde Ω. 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.

La troisème complexité é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 doive 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 naive 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 donc en O(n).

Une approche plus subtile consiste à utiliser un arbre binaire de recherche, équilibré. 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 dans tous les schéma de bases de données :

Faut-il mettre un index sur cette colonne ?

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(n2).

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(nlog 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 ces cas particulier mais reste entre O(nlog n) et O(n2) 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 webservice 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...

La base de donnée était organisée autour d'une table 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 puis sélectionnait les lignes où les valeurs étaient null pour les autres types...

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(n2) 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.

Et la sécurité dans tout ça ?

Les plus férus de complexité algorithmique en matière de sécurité informatique restent encore les cryptographes. La cryptographique moderne repose sur des problèmes réputés difficiles à résoudre. Les meilleurs algorithmes pour la factorisation ou le logarithme discret ont une complexité sous exponetielle en O(nlog 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.

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é2.

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(n2) à O(1).


  1. Si vous voulez des définitions plus formelles, je vous conseillece cours

  2. La sécurité est pour moi une étape de plus après la qualité 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.