Complexité des algorithmes

[egondragon]

Bonjour

Je suis en train de consulter des documents sur la complexité des algorithmes

J'ai un certain mal avec la notion de "O(f)"
Typiquement on dit qu'un algorithme est de complexité O(n)

Ca veut dire quoi au juste:
- Ca prend n secondes pour l'exécuter ?
- Il consomme n instructions ?

Pardon si les questions sont triviales

Par ailleurs qu'entends t'on par des problèmes P/NP ?

J'ai compris que certains pbme relèvent de la décision et que d'autres relèvent de l'optimisation

Les pbmes de décisions polynomiaux sont ceux dont on peut définir la complexité comme "temporelle"
Un pbme de décision est de classe P s'il peut être résolu par un algorithme de classe O(n exposant k)

Pour les problèmes NP, on dit que pour toute instance il existe un algo polynomial de vérifier que la réponse au problème est oui.
On parle également de NP complétude.

Je ne saisis pas bien ces notions (et surtout je ne vois pas à quoi ca sert), quelqu'un aurait il des pistes ?

Merci de vos lumières

Cordialement.
-----

[invitebe0cd90e]

Salut,

La notation O(n) vient de la : http://fr.wikipedia.org/wiki/Grand_O#Domination

Ce qui compte, ca n'est pas le temps, qui va dependre de l'ordinateur, mais le nombre d'operations "elementaires" que l'algorithme va effectuer. Ensuite, plutot que de donner une formule exacte qui n'aurait pas beaucoup de sens, on se contente de donner le terme dominant, celui qui est largment dominant sur les autres, sans se preoccuper des contantes... SI par exemple tu as un algorithmes qui va necessiter 2n^2+3n additions de petits nombres entiers, ou ici n est une variable, et sachant que chaque addition aura en gros toujours la meme complexité (cad que le nombre d'instructions pour une addition est constant, ne depend pas de n et on ne s'en preoccupe donc pas) tu diras que ton algorithme est en O(n^2). Attention, on dit souvent "en temps polynomial", mais on parle toujours de complexité (en fait, le temps mis par l'algorithme est egal a la complexité de l'algo, multiplié par une constante qui depend de l'ordinater, donc on assimile les deux notions).

Quand on parle de P/NP, on parle en fait toujours de problemes de decisions. Meme si par abus de langage on l'etend parfois a d'autre classe de probleme. Un probleme de decision est une question a laquelle la reponse est oui ou non. Si n est la taille du probleme (en un sens precis, n est un entier) :

Un probleme est dans P si on peut repondre oui ou non en un temps polynomial, cad en O(n^k) pourun certain k.

Un probleme est dans NP si a chaque fois que je teste une solution, alors je peux tester en temps polynomial si cette solution repond a ma question ou non. Donc en particulier un algorithme P est forcement NP, mais l'inverse n'est pas necessairement vrai. En fait on ne sait pas encore si toues les problemes NP sont en fait P.

Exemple typique : trouver le chemin le plus court qui passe par n villes et qui revient au point de depart. Question : est ce qu'il existe un chemin de moins de X kilometres.

Si je te donnes un chemin, il te suffit de calculer sa longueur, ce qui revient a faire n addition, donc tu peux savoir en O(n) si ce chemin fait moins de X km ou pas. Mais pour vraiment repondre definitivement a la question, on ne connait rien de plus efficace que de tester tous les chemins possibles, ce qui te donne un O(n!), ce qui est evidemment enorme.

Enfin, un probleme est NP complet s'il est NP, et s'il est au moins aussi dur que n'importe quel probleme NP. Autrement dit, un algorithme qui donne une solution d'un probleme NP complet, donne aussi une solution pour n'importe quel probleme NP.

TOut ca sert a classifier les algorithmes. EN gros, un algorithmes qui n'est pas polynomial (ou mieux, logarithmique par ex) a de grandes chances de ne pas etre utilisable en pratique.

[egondragon]

Bonsoir

Je crois voir pour la complexité
Donc si un algorithme (par exemple le tri fusion) met 2 puissance n + 12 opérations élémentaires pour trier un tableau on peut dire que c'est un algorithme en O(2 puissance n)

Mais si on dit qu'il est en O(15 * log(15)) cela signifie qu'il met 15 log 15 opérations élémentaires pour trier un tableau de 15

Or là j'ai du mal, car 15 log 15 pour moi ça donne 17.641368886 opérations élémentaires, ce qui n'est pas possible à mon sens (on ne peut exécuter qu'un nombre entier d'opérations élémentaires je pense).

Cordialement

[invite2734a185]

Bonjour,

jobherzt a déjà bien expliqué le concept de complexité. Il s'agit en fait de donner, pour un algorithme donné, un ordre d'idée du nombre d'opérations élémentaires qu'il va falloir nécessiter pour qu'il se termine.

Pour ta question avec O(15 * log(15)), je ne crois pas qu'on puisse écrire ça, pour la simple et bonne raison que dans la complexité tu fais sauter les paramètres constants, qui n'ont pas de rapport avec n. Par exemple O(3n) est équivalent à O(n), tu ne gardes que les choses ayant un rapport avec n. O(15 * log(15)) = O(1) car il n'y a rien en rapport avec n. Si ton algorithme est en O(n * log(n)) et que tu as une donnée de taille 15, il y aura en moyenne (15 * log(15)) opérations. Mais O(15 * log(15)) ne veut rien dire. Je pense que ce n'est pas ce que tu as voulu écrire, mais je préfère te reprendre .

Si ton algorithme de tri est de complexité O(n * log(n)), cela veut dire, si je ne me trompe pas, qu'il faudra en moyenne (pour une donnée de taille suffisamment grande, d'où le terme de complexité _asymptotique_) n * log(n) opérations. C'est vrai que quand tu prends une entrée donnée, de taille 15 par exemple, ça n'a pas l'air parlant. En fait, il faut juste se rendre compte que tu vas certainement rentrer dans une boucle itérant n fois, et qu'à l'intérieur tu vas réaliser moins de n opérations (c'est mon idée du log(n), qu'on fait moins de n opérations). La complexité d'un algorithme permet ainsi de savoir à peu près sa "structure" : les itérations, leur imbrication, etc...

Ce n'est pas très simple à expliquer, et j'espère ne pas dire d'âneries...

Pour les problèmes P/NP, les deux sont des problèmes de décision : on te pose une question, et pour chaque instance du problème tu dois être capable de répondre par oui ou par non. Par exemple : étant donné un nombre, est-il premier ? Etant donné un graphe, est-il 2-coloriable ? Il y en a des tas !

La particularité des problèmes P et NP c'est qu'ils sont décidables, c'est à dire que dans ces deux classes se retrouvent les problèmes que tu sais résoudre par un algorithme. Il existe des problèmes n'étant pas solvables, par exemple le célèbre problème de l'arrêt : étant donné un programme (une machine de Turing, ou n'importe quoi), peux-tu dire s'il s'arrête ou s'il va boucler infiniment ? Ce genre de questions n'est pas soluble car s'il boucle, comment savoir s'il ne va pas s'arrêter un jour ? Ce genre de problèmes est dit indécidable (ou semi-décidable), et ne sont ni P ni NP.

Maintenant la différence entre P et NP concerne les algorithmes de résolution : un problème P va être résolu par un algorithme en temps polynomial, c'est à dire avec une complexité linéaire avec la taille de l'entrée. Par exemple si il met un "temps" x pour résoudre un problème de taille n, il en mettra 2x pour un problème de taille 2n. Le temps de résolution ne "s'envole" pas avec l'augmentation de la taille de l'entrée.

Au contraire, les problèmes NP sont des problèmes pour lesquels on ne dispose pas d'une méthode "directe". Du coup l'algorithme va générer une solution de manière un peu "aléatoire" (i.e. sans être certain que ce sera la bonne), et tu vas pouvoir tester sa véracité en temps polynomial par la suite. Le N de NP signifie non-déterministe, et tu retrouves bien là-dedans l'idée que l'algorithme va devoir procéder à des choix à des moments-donnés...

Après il y a aussi les problèmes NP-Complets, qui sont les problèmes de décision de NP les plus durs. On sait les résoudre, mais pas en temps polynomial : de manière naïve on va utiliser des méthodes de force brute, en testant toutes les possibilités. Par exemple le problème NP-Complet le plus connu est SAT : étant donné une formule booléenne, peux-tu trouver une affectation de ses booléens pour qu'elle soit vraie ? Si ta formule a k variables, tu peux tester toutes les valeurs possibles, ce qui fait 2^k. Et comme tu le vois, ce n'est clairement pas polynomial... On retrouve bien l'idée que j'ai dite plus haut, à savoir que pour les problèmes NP il y a des "choix" à faire à un moment donné : la variable k1 de la formule doit-elle valoir vrai ou faux ? L'algorithme ne peut pas le savoir, donc il doit tester les deux possibilités, d'où une récursivité dans ton algorithme, et donc le caractère exponentiel de la complexité...

Enfin, il y a les problèmes NP-Difficiles. C'est un peu le même principe que les problèmes NP-Complets, sauf qu'ici ce sont des problèmes d'optimisation : plutôt que de chercher à répondre oui ou non à un problème, on va chercher à maximiser ou minimiser une fonction. Par exemple : étant donné un graphe pondéré, peux-tu trouver une partition de ses sommets en k classes équivalentes de sorte que la somme des poids des arêtes inter-classes soit minimale ? La fonction objectif, celle à optimiser, de ce problème est la somme des pondérations des arêtes inter-classes. Il s'agit ici d'un problème de minimisation.


J'espère ne pas t'avoir embrouillé, et si j'ai dit des bêtises j'espère que d'autres personnes sauront me reprendre ^^ .

[A voir en vidéo sur Futura]

[invite2734a185]

Après il ne faut pas s'attendre à avoir exactement le même nombre d'opérations que ce qu'indique la complexité : par exemple les algorithmes en O(n) comprennent ceux en O(2n), O(3n), etc ; car comme je te l'ai expliqué, les paramètres constants ne sont pas pris en compte. C'est juste un ordre d'idée, mais ce n'est pas une indication du nombre exact d'opérations qui vont être effectuées.

[invitebe0cd90e]

Salut, desolé je n'avais pas vu ta reponse, je n'avais pas du m'abonner a la discussion.

Ce qu'il faut bien comprendre, c'est que la notion de complexité permet de repondre a la question : a quelle vitesse augmente le nombre d'operation en fonction de la taille du probleme.

Donc il ne s'agit pas de donner quelque chose d'exact. On utilise des fonctions mathematiques qui ont des croissances connues et qui sont pertinentes pour les operations qu'on effectue.

Le top c'est le temps constant (qui ne depend pas de n), ensuite il y a le temps log(n) (qui augmente moins vite que n lui meme), puis n (temps lineaire) puis n^k (polynomial), etc..

Tu peux tres bien avoir des logs qui apparaissent. Par exemple, si tu manipules des suites de bits : 010101011... et que tu as un algorithme qui effectue un nombre d'operation en gros egal au nombre de chiffres apparaiisant dans cette suite.

Et en fait on peut tres bien avoir des logs qui apparaissent naturellement. Typiquement dans le tri fusion, l'operation de fusion est en log(n). En gros, dire que tu as une complexité en log veut dire qu'a chaque fois que tu multiplies la taille du probleme par un nombre, tu ajoutes seulement quelque chose a la complexité, et ca evidemment on aime bien. Par exemple, pour la fusion, si tu multiplies le nombre d'element a fusionner par 2, tu auras seulement une fusion supplementaire a effectuer, c'est pour ca que c'est en O(log(n)).