Skip to content

Texte

La notion de grand \(O\)

Les exemples précédents montrent qu'il est souvent très difficile de calculer le temps moyen (ou maximal) d'exécution d'un algorithme. Ces calculs précis sont, de plus, inutiles puisqu'ils se basent sur des approximations grossières du temps d'exécution des actions élémentaires; évaluations qui ne tiennent pas non plus compte, par exemple, de l'ordinateur et de l'interpréteur utilisés.

Une évaluation du temps d'exécution d'un algorithme ne devient généralement intéressante que lorsque la taille du jeu de données, c'est-à-dire de \(n\) dans nos exemples précédents, est grande. En effet pour \(n\) petit, les algorithmes s'exécutent généralement très rapidement.

Supposons que la complexité maximale d'un algorithme \(A = 100.n\), que la complexité maximale d'un algorithme \(B = 15.n^2\) , celle de \(C = n^4\) et celle de \(D = 2^n\).

Le graphique montre qu'à partir de \(n\) valant quelques dizaines, \(2^n\) prend le pas sur \(n^4\) qui prend le pas sur \(15n^2\) et encore plus sur \(100n\)

La table suivante donne les valeurs de complexité pour \(n = 1,10,100,1,000, 10,000, 10^6\) et \(10^9\);

\(n\) \(A\) \(B\) \(C\) \(D\)
\(1\) \(100\) \(15\) \(1\) \(2\)
\(10\) \(1000\) \(1500\) \(10000\) \(\approx 10^3\)
\(100\) \(10000\) \(150000\) \(10^8\) \(\approx 10^{30}\)
\(1000\) \(100000\) \(15.10^6\) \(10^{12}\) \(\approx 10^{300}\)
\(10000\) \(10^6\) \(15.10^8\) \(10^{16}\) \(\approx 10^{3000}\)
\(10^6\) \(10^8\) \(15.10^{12}\) \(10^{24}\) \(\approx 10^{300000}\)
\(10^9\) \(10^{11}\) \(15.10^{18}\) \(10^{36}\) \(\approx 10^{3.10^{8}}\)

Valeur de \(100.n\), \(15.n^2\), \(n^4\) et \(2^n\) pour différentes valeurs de \(n\)

Ces valeurs doivent être divisées par le nombre d'instructions élémentaires par seconde pour obtenir un temps exprimé en seconde.

Les micro processeurs actuels permettent d'exécuter de l'ordre de \(10^9\) instructions par seconde soit environ \(10^{14}\) instructions par jour.

Cela signifie qu'en un jour, si aucune autre limitation ne perturbe l'exécution des algorithmes (telle que l'espace mémoire disponible par exemple), avec un microprocesseur, on peut résoudre avec l'algorithme

  • \(A\) , un problème pour \(n\) valant approximativement \(10^{12}\)
  • \(B\) , un problème pour \(n\) valant approximativement \(10^7\)
  • \(C\) , un problème pour \(n\) valant approximativement \(3000\)
  • \(D\) , un problème pour \(n\) valant approximativement \(50\)

et donc \(A\) est meilleur que \(B\), qui est meilleur que \(C\), lui-même étant meilleur que \(D\) (sauf pour de petites valeurs de \(n\)).

De façon générale, quand on regarde les complexités on voit un classement dans les fonctions n exposant n plus grand que 2 exposant n qui elle-même est plus grand que n exposant 3, plus grand que n exposant 2, plus grand que n log n plus grand que n plus grand que log de n plus grand que 1.

En vertu des remarques précédentes et de ces chiffres, on préfère donner un ordre de grandeur permettant d'avoir une idée du type d'algorithme en terme de complexité. Pour cela, on utilise la notation grand \(O\), qui permet:

  • de déterminer si un algorithme a une chance de s'exécuter pour un \(n\) donné,
  • connaissant le temps d'exécution pour un \(n\) donné, de faire une approximation de ce temps pour une autre valeur de \(n\).

Définition de complexité en O()

La notation grand \(O\) est définie comme suit:

Définition (\(O\)) : Une complexité \(T(n)\) est en \(O(f(n))\) si \(\exists N, c > 0 .\;\forall n > N \; T(n) \leq c.f(n)\)

Cette définition permet d'effectuer de nombreuses simplifications dans les calculs. En effet de cette définition il résulte que:

  • Les facteurs constants ne sont pas importants. Par exemple que \(T(n)=n\) ou \(T(n)=100n\), \(T(n)\) est toujours en \(O(n)\)
  • Les termes d'ordres inférieurs sont négligeables. Ainsi si \(T(n) = n^3 + 4n^2 + 20n + 100\), on peut voir que pour \(n > N = 5\)

    • \(n^3 > 4n^2\)
    • \(n^3 > 20n\)
    • \(n^3 > 100\)

et donc pour \(n>5\), \(T(n) = n^3 + 4n^2 + 20.n + 100 < 4n^3\).

De ce fait \(T(n)\) est en \(O(n^3)\).