FAQ algorithmesConsultez toutes les FAQ
Nombre d'auteurs : 6, nombre de questions : 125, dernière mise à jour : 23 août 2017 Ajouter une question
Cette FAQ a été réalisée à partir des questions fréquemment posées sur les forums de Developpez.com et de l'expérience personnelle des auteurs.
Nous tenons à souligner que cette FAQ ne garantit en aucun cas que les informations qu'elle propose sont correctes ; les auteurs font le maximum, mais l'erreur est humaine. Cette FAQ ne prétend pas non plus être complète. Si vous souhaitez devenir rédacteur, lisez ceci. Vous pouvez poster toutes vos remarques, questions, avis et corrections sur la FAQ sur le forum.
Nous espérons que cette FAQ saura répondre à un maximum de vos questions. Nous vous souhaitons une bonne lecture.
L'équipe algorithmique de Developpez.
La notation grand O est une notation mathématique très utilisée en algorithmique pour permettre de quantifier le nombre de calculs qu'effectue une fonction ou un algorithme.
Elle est définie mathématiquement comme suit :
- soit f et g deux fonctions de R (réel) dans R ;
- on note f=O(g) si et seulement s'il existe un réel strictement positif c et un réel x0 tel que : pour tout x>x0, |f(x)| < c.|g(x)|.
Cela signifie que f est dominée par g.
Exemple : n²+n = O(n²), car n est négligeable devant n². 2^n = O(exp(n)).
On utilise ainsi cette notation pour simplifier au maximum la fonction f et ne donner qu'un ordre de grandeur (l'ordre le plus important).
Ainsi, un algorithme est en O(f(t)) si en ordre de grandeur, l'algorithme nécessite moins de f(t) opérations où t est la taille de l'entrée (ou du paramètre) de l'algorithme. Par exemple, si le paramètre de l'algorithme est une liste L de taille n, alors on considère en général que la taille de L est n. Si l'entrée est un entier n, la taille de n est log_2(n) (il faut en effet de l'ordre de log_2(n) bits pour représenter un entier).
On utilise parfois la notation Theta pour dire que deux fonctions sont équivalentes. f=Theta(g) est équivalent à dire f=O(g) et g=O(f). On parle souvent de O alors que l'on devrait parler de Theta pour être plus précis.
Exemple avec un algorithme :
En général, on définit une fonction qui réalise quelque chose (par exemple ici, sommer les n premiers entiers). On cherche un algorithme qui la résout en effectuant un nombre de calculs le plus petit.
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 | Calcul de la somme des n premiers entiers fonction somme(Entier n) -> Entier j <- 0 Pour i=1 à n faire j <- j+i Retourner j |
On aurait également pu calculer la somme directement avec la formule bien connue :
| Code : | Sélectionner tout |
1 2 3 | Calcul de la somme des i premiers entiers fonction somme(Entier n) -> Entier Retourner (n+1)n/2 |
Ainsi, on a un exemple d'une fonction admettant deux algorithmes qui la détermine, mais de complexités différentes.
Pour commencer il faut distinguer deux types de complexité :
- complexité temporelle ;
- complexité spatiale.
D'abord, la complexité temporelle, qui permet d'évaluer la rapidité qu'un algorithme met à s'exécuter en fonction d'un ou plusieurs paramètre(s), dépend uniquement de une ou plusieurs données fournies en entrée. Ensuite la complexité spatiale, qui permet d'évaluer l'occupation de la mémoire que va prendre l'algorithme, dépend aussi uniquement de un ou plusieurs paramètres. Évidemment cette complexité n'est pas prioritaire, car vu l'espace que l'on a sur les PC actuels, c'est loin d'être un problème.
L'unité d'une complexité est le nombre de fois que l'instruction la plus coûteuse va s'exécuter, car par exemple, pour les algorithmes de tri les instructions les plus coûteuses sont les comparaisons que l'on fait sur les éléments d'un tableau ou d'une liste. Nous prendrons donc la taille d'un tableau ou d'une liste, la hauteur d'un arbre, etc. qui vont nous permettre d'exprimer ce nombre d'exécutions. Nous noterons la complexité par la lettre grand O. Les complexités d'algorithmes les plus courantes sont :
- O(1) : temps constant ;
- O(log(n)) : logarithmique ;
- O(n) : linéaire ;
- O(n*log(n)) : linéarithmique ;
- O(n^p) : polynomiales ;
- O(p^n) : exponentielle.
Un problème est dans la classe P si et seulement si c'est un problème de décision admettant un algorithme déterministe de temps polynomial. Un exemple classique d'un problème de cette classe est de savoir si un graphe est connexe ou non. On peut aussi dire que tous les problèmes de décisions (ceux qui ont une réponse par oui ou non) qui peuvent être facilement résolus par un algorithme polynomial sont dans cette classe.
Un problème est dans la classe NP si et seulement si c'est un problème de décision admettant un algorithme non déterministe de temps polynomial. Un exemple classique d'un problème de cette classe est de savoir si un graphe est hamiltonien ou non. On peut aussi dire que tous les problèmes que l'on résout par un algorithme qui énumère toutes les possibilités sont dans cette classe.
Un problème est dit X-complet si et seulement s'il est :
- de classe X (P, NP…) ;
- de type X-difficile.
Un problème est dit X-difficile si et seulement s'il est au moins aussi ardu que tous les problèmes dans X, sachant que X est une classe quelconque (P, NP…). Plus concrètement on dit que l'on réduit un problème difficile en un autre plus facile de la même classe et, si on arrive à résoudre le plus facile, alors on peut résoudre le difficile.
Proposer une nouvelle réponse sur la FAQ
Ce n'est pas l'endroit pour poser des questions, allez plutôt sur le forum de la rubrique pour ça
Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2024 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.