Developpez.com - Autres
X

Choisissez d'abord la catégorieensuite la rubrique :

logo
Sommaire > Définitions et Notations > Complexité
        Qu'est-ce que la complexité?
        Quelle est la différence entre complexité temporelle et spatiale?
        Qu'est-ce que la notation en grand O?
        Quels sont les différents types de notation?
        Quels sont les ordres de complexité typiques?

rechercher
precedent    sommaire    suivant


Qu'est-ce que la complexité?
auteur : Rodriguez Eric
La complexité d'un problème est le nombre d'étapes nécessaires à un alogrithme pour résoudre une instance du problème. On exprime souvent cette complexité comme une fonction de la taille des données en entrée. On distingue deux types de complexité: complexité temporelle et complexité spatiale. Le matériel ou le langage utilisés pour résoudre le problème n'interviennent pas dans l'évaluation de la complexité de l'algorithme.


Quelle est la différence entre complexité temporelle et spatiale?
auteur : Rodriguez Eric
TODO


Qu'est-ce que la notation en grand O?
auteur : Rodriguez Eric
Pour parler de complexité, on utilise habituellement une notation asymptotique pour décrire le comportement d'un algorithme en fonction de ses entrées. La notation la plus répandue est la notation en "grand O" (Big O notation): par exemple O(n^2). Formellement, O() est défini de la façon suivante Soit 2 fonctions réelles f(x) et g(x), f(x) est en O(g(x)) quand x -> +Inf si et seulement si Il existe x_0 et une constante M tels que |f(x)| <= M*|g(x)| pour x > x_0.


Quels sont les différents types de notation?
auteur : Rodriguez Eric
Quand on parle de complexité d'un algorithme, on peut vouloir décrire plusieurs cas de figure. La complexité peut ainsi être estimé selon: le pire des cas, le meilleur des cas, le cas moyen, ...
TODO:
  • O - grand O
  • o - petit o
  • omega
  • theta


Quels sont les ordres de complexité typiques?
auteur : Rodriguez Eric
La plupart des algorithmes peuvent être rangés dans les ordres de grandeurs typiques suivants (en notation "grand O"):

  • complexité constante: O(1)
  • complexité logarithmique: O(log(n))
  • complexité linéaire: O(n)
  • complexité quasi-linéaire: O(n*log(n))
  • complexité quadratique: O(n^2)
  • complexité polynomiale: O(n^k) (k doit être > 1)
  • complexité exponentielle: O(k^n)


rechercher
precedent    sommaire    suivant

Consultez les autres F.A.Q's

Valid XHTML 1.1!Valid CSS!


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 © 2005 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 Autres