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.


SommaireComplexité (6)
précédent sommaire suivant
 

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
Ce code effectue n somme (en considérant que l'incrémentation de i n'est pas une somme), c'est un algorithme en O(n).

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
Si la multiplication se fait en temps constant (comme c'est le cas sur les processeurs actuels en général, car on considère les entiers bornés), l'algorithme effectue une somme, une multiplication et une division, il est en O(1) = 3 opérations.

Ainsi, on a un exemple d'une fonction admettant deux algorithmes qui la détermine, mais de complexités différentes.

Mis à jour le 9 juillet 2008 millie

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.

Mis à jour le 9 juillet 2008 snake264

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.

Mis à jour le 9 juillet 2008 Alp PRomu@ld snake264

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.

Mis à jour le 9 juillet 2008 Alp PRomu@ld snake264

Un problème est dit X-complet si et seulement s'il est :

  • de classe X (P, NP…) ;
  • de type X-difficile.

Mis à jour le 9 juillet 2008 Alp PRomu@ld snake264

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.

Mis à jour le 9 juillet 2008 Alp snake264

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


Réponse à la question

Liens sous la question
précédent sommaire suivant
 

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 © 2018 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.

 
Contacter le responsable de la rubrique Débuter - Algorithmique