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? Qu'est-ce que la complexité? [haut] 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? [haut] auteur : Rodriguez Eric TODO Qu'est-ce que la notation en grand O? [haut] 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? [haut] 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? [haut] 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) Consultez les autres F.A.Q's

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 ni 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.