Complexite

La complexité d’un algorithme désigne l’accroissement du temps et de l’espace nécessaires à la résolution d’un problème en fonction de la taille du jeu d’entrée de celui-ci.

Algorithmes polynomiaux

Par exemple pour trouver la plus petite valeur d’un tableau non trié, il faut le parcourir entierement, le temps à la solution de ce problème augmente linéairement par rapport au jeu d’entrée. Le meilleur algorithme qu’on peut créer pour ce problème sera donc un algorithme linéaire.

Si au lieu d’avoir un tableau de nombres son trié on a un tableau de nombres trié, sa plus petite valeur sera celle de la première case et sa recherche se fait en temps constant.

Si on veut trouver une valeur arbitraire dans un tableau trié on peut naivement faire par recherche exhaustive, en le parcourant entièrement, cet algoritme sera linéaire ; mais sachant que le tableau est trié on peut également vérifier sa valeur médiane et selon que le nombre trouvé est plus petit ou plus grand que celui qu’on recherche, regarder la médiane de la moitié gauche ou droite, récursivement.

Avec cette méthode par recoupes successives, si on double la taille du jeu d’entrée, le nombre de cycles n’augmente que de 1, c’est à dire qu’un tel algorithme travaille en temps logarithmique. Intuitivement cette facon de procéder est similaire à la façon dont on cherche un mot dans un dictionnaire papier ou un nom de famille dans un annuaire téléphonique en papier (même si ceux-ci tendent à disparaitre).

Admettons que nous voulions connaitre la somme des distances entre chaque point du tableau par rapport a tous les autres points: par exemple pour un tableau [10, 5, 6, 2], la somme des distances de la première case est 10-5 + 10-6 + 10-2, soit 17 ; pour la deuxieme case 5-10 + 5-6 + 5-2, soit -3 ; de la même façon on trouve 1 pour la troisième case et -15 pour la dernière case; si on additionne tous ces chiffres on obtient 0.

Si on devait ajouter une valeur a ce tableau on devra recalculer autant de distances qu’il y a de cases de cases deja existances, c’est a dire qu’o effectue autant d’itérations qu’il y a d’eléments , chaque nouvel element augmente le nombre et la longueur de chaque intération. Multiplier un nombre par lui même signifie le porter au carré, autrement un tel problème s’effectue en temps quadratique.

Si l’espace de problème se trouve dans un plan en 3d, la complexité augmente en temps cubique. Au dela la puissance 3 on parle de temps puissance N.

Tous les problèmes que nous avons vu s’exécutent en temps polynomial, c’est à dire que leur complexité est bornée par une fonction polynomiale de la taille de l’entrée et de type : n^2, n^3, etc. Plus généralement n^k où k est une constante : pour k = 0 on est en temps constant, pour k = 1 en temps linéaire, pour k = logN en temps logarithmique, k = 2 en temps quadratique, k = 3 en temps cubique. Pour k = 4 et plus on parle de complexité polynomiale d’ordre 4, 5, etc.

Algorithmes non polynomiaux

Lorsque k est fonction de la taille de l’entrée, le problème est considé s’exécuter en temps exponentiel : c’est à dire que pour chaque incrément de la taille de l’entrée, le temps nécessaire à la solution de l’algorithme double, triple, etc. Une complexité exponentielle est de la forme O(c^n) où c est supérieur à 1. On partle également parfois de complexité géométrique 🌍⤴ . Un algorithme exponentiel est généralement inefficace pour tout problème suffisamment grand. Le problème du sac à dos (knapsack problem) qui consiste à mettre dans un sac à dos un ensemble de poids et de tailles divers en maximisant l’espace occupé en fonction de la taille disponible est un exemple de problème exponentiel car il nécessite pour chaque élément de tester toutes les permutations possibles, même si des heuristiques et des techniques approximatives permettent d’obtenir des résultats satisfaisants.

Un algorithme de complexité factorielle a une complexité de la forme O(n!). Un algorithme de cette forme est généralement inefficace pour un problème suffisamment grand. Le problème du voyageur de comerce (TSP - Traveling Salesman Problem) est un exemple de problème factoriel : il consiste à trouver le plus court chemin entre un ensemble de villes, en revenant à la ville de départ, sans passer plusieurs fois dans la même ville. La solution consiste pour chaque ville à tester toutes les permutations possibles. Des heuristiques et des techniques approximatives permettent de donner des résultats satisfaisants à ce problème.

Le problème de satisfaisabilité (SAT problem) consite à prouver que pour une expression booleenne quelconque il existe une combinaison de valeurs qui satisfasse l’expression : par exemple pour (A ∨ B) ∧ (¬A ∨ C) ∧ (¬B ∨ C) existe-il une combinaison de A, B et C de telle sorte que l’expression soit vraie. Pour A = Vrai, B = Faux et C = Vrai, on trouve

Ainsi cette expression peut être satisfaite. Lorsque le nombre de paramètres augmente la difficulté augmente rapidement et il a été prouvé que le problème SAT pour une quantité de variables suffisamment grande et une expression suffisamment complexe ne peut être résolue en temps polynomial. Un problème au moins aussi complèxe que le problème SAT est considéré comme NP-complet. Un problème NP (nondeterministic polynomial) sur une machine hypothétiquement non déterministe capable de tester toutes les combinaisons en même temps s’exécute en temps polynomial. Un problème NP est simple à vérifier mais difficile à calculer. Tous les problèmes NP n’ont pas la même complexité et il existe pour certains des algorithmes approximatifs ou heuristiques satisfaisants. Un problème NP-complet est un problème NP au moins aussi complèxe que le problème SAT, c’est à dire un problème NP considéré comme parmi les plus difficiles à résoudre.

Enfin certains problèmes NP-complets ont une complexité indéterminée car leur complexité est difficile à déterminer correctement. Ils sont généralement résolus par des heuristiques et des algorithmes approximatifs et concernent des questions qui ne peuvent être réduits à un formalisme mathématique.

Finalement on remarque que pour le problème de calcul de distances des valeurs d’un tableau qu’on a présenté comme un problème de type quadtratique, il se trouve qu’en pratique la somme des distances d’un tableau de valeurs sera toujours égale à zero et donc il existe une solution en temps constant à ce problème qui consiste à affirmer que la somme des distances d’un tableau sera toujours égal à zero, donc pour ce problème en particulier il se trouve que O(n^2) == O(1). Dans le même ordre d’idée affirmer que tous les problèmes qui s’exécutent en apparence en temps non polynomial possèdent une solution non intuitive qui s’exécute en temps polynomial consiste à affirmer que P=NP.

Notation asymptotique

Pour qualifier la complexité d’un algorithme on utilise trois notation asymptotiques :

Il existe d’autres notations en plus de ces trois notations, et parmi ces trois notations, la notation grand O est la plus commune.

Dans un algorithme polynomial on considère les polynomes d’ordre inférieur comme négligeables C’est à dire que O(n^3 + n^1 + 1) se simplifie en O(n^3). Seul l’ordre du polynome nous intéresse, si bien O(3) se simplifie en O(1), O(2N^2) se simplifie en O(N^2). L’ordre du logarithme est considéré comme négligeable si bien que O(log10N) ou O(log2N) se simplifient en O(logN). Lorsqu’un polynome contient a la fois une partie logarithmique et non logarithmique, on conserve les deux : O(NlogN) ne se simplifie pas car pour des jeux d’entrée suffisamment petits la partie logarithmique peut être non négligeable et a une influence sur l’aspect asymptotique globale de l’algorithme.

Rechercher un élément dans un tableau non trié a une complexité Ω(1) et O(N), rechercher le nombre d’occurences d’un élément dans un tableau non trié a une complexité Θ(N). La recherche dans une table de hachage a une complexité Ω(1) et O(N) dans le pire des cas oú tous les éléments ont la même clé de hachage. Cette probabilité est toutefois infinitésimale et la compléxité « pratique » d’une recherche dans une table de hachage est en temps constant : il n’existe toutefois pas de notation pour l’exprimer.

Exercice

Considérons une tour de K etages et N oeufs, on souhaite trouver à partir de quel étage un oeuf se brise si on le laissait tomber en chute libre. Combien faut-il d’oeufs pour trouver cet étage, quelle est la complexité O, omega et theta dans le cas où l’on a

  • 2 oeufs et 100 etages
  • 2 oeufs et k étages
  • N oeufs et k etages.

Solution Pour 2 oeufs et 100 etages : une solution naive est d’utiliser une recherche dichotomique puis linéaire : tester au 50e etage, puis au 75 ou 25e, etc. Cependant dans le cas où le premier oeuf ne se brise (ou pas) que lorsqu’il reste deux etages à tester, on trouve la solution en temps logarithmique, mais si il se brisait à la première tentative, pour conserver le deuxième oeuf on sera obligé de partir du premier étage et tester chaque étage successivement, soit 50 tentatives dans le pire des cas – vu qu’on ne peut se permettre de perdre le deuxième oeuf.

Si on devait improprement et mécaniquement utiliser une notation asymptotique pour décrire la complexité de ce problème qui n’est pas asymptotique on écrirait Ω(2) (un oeuf se casse au 50ème puis au premier étage) et O(50), soient Ω(1) et O(1), soit Θ(1). Vu que ce problème n’est pas asymptotique cette notation n’est pas pertinente ou descriptive, tout comme il n’est pertinent de simplifier O(50) en O(1).

La meilleure solution est de tester au 14ème étage car si l’oeuf venait à briser, il n’y aurait que 13 tentatives à faire dans le pire des cas. Si l’oeuf ne se brise pas on ajoute 13 étages, puis 12 étages puis 11 étages, etc. C’est à dire que dans le pire des cas le nombre de tests n’exèdera jamais 14. Cette solution est Ω(2), O(13), soit Θ(1).

Pour k étages on veut trouver l’étage x de sorte que en suivant le même procédé que précédement, c’est à dire x + (x - 1) + (x - 2) + … + 2 + 1 on trouve un nombre supérieur ou égal à k.

Il s’agit ici de trouver le nombre triangulaire 🌍⤴ qui soit supérieur ou égal à k, soit (x(x+1))/2 >= k, soit x^2 + x -2k >= 0, soit x = (-1 + (1 + 8k)^0,5)/2 Pour k = 100, on trouve x = 13,65, soit 14 essais. Cette méthode est valide pour tout x supérieur ou égal à 1 et dans ce cas sa complexité est Ω(2), soit Ω(1) et O((-1 + (1 + 8k)^0,5)/2), soit O(k^0,5), ou encore O(√k).

Dans le cas où le nombre d’oeufs est variable il existe de nombreuses solutions récursives , dynamiques et qui nécessitent la connaissance de la propriété binomiale des nombres et du triangle de pascal. Ce problème et présent en programmation compétitive et il a des applications pratiques dans l’optimisation de procédures de test, de conception de matériaux, ou de tests fiabilité.