{"id":409,"date":"2020-09-21T21:51:36","date_gmt":"2020-09-21T19:51:36","guid":{"rendered":"http:\/\/maths-code.fr\/cours\/?page_id=409"},"modified":"2024-11-11T14:29:40","modified_gmt":"2024-11-11T13:29:40","slug":"complexite","status":"publish","type":"page","link":"https:\/\/maths-code.fr\/cours\/complexite\/","title":{"rendered":"Complexit\u00e9 temporelle d’un algorithme"},"content":{"rendered":"

En informatique, le traitement de certains algorithmes complexes peut n\u00e9cessiter du temps et de la ressource machine : c’est ce qu’on appelle le co\u00fbt de l’algorithme.<\/strong> L’utilisation des ressources est fondamentale et la question du co\u00fbt est donc centrale en informatique.
\nCe co\u00fbt est calculable et refl\u00e8te son efficacit\u00e9 : plus l’algorithme est co\u00fbteux, moins il est efficace, et pour une m\u00eame t\u00e2che certains algorithmes se r\u00e9v\u00e8lent plus co\u00fbteux que d’autres.<\/p>\n

L’id\u00e9e centrale est de donner un calcul du co\u00fbt de l’algorithme en comptant les op\u00e9rations fondamentales. Ce calcul n’est pas exact : c’est un ordre de grandeur \u00e9crit avec une fonction math\u00e9matique.<\/p><\/blockquote>\n

La mesure du temps d’ex\u00e9cution se fait rarement de fa\u00e7on exacte<\/strong>, si on arrive \u00e0 comparer deux progammes en estimant leur co\u00fbt, on dira que l’un a une meilleure complexit\u00e9 temporelle. Notre objectif est donc de cataloguer<\/em> les algorithmes en les rangeant dans des familles suivants leur complexit\u00e9. Cette complexit\u00e9 est donn\u00e9e par une fonction math\u00e9mathique<\/strong> qui est un ordre de grandeur not\u00e9 O (qui est une fonction de n )<\/em>, voici les principales:<\/p>\n

1. O(1) <\/strong>:\u00a0complexit\u00e9\u00a0constante .
\n2. O( log(n) ) <\/strong>:\u00a0complexit\u00e9\u00a0logarithmique<\/strong> (recherche dichotomique).
\n3. O(n)\u00a0 <\/strong>:\u00a0complexit\u00e9\u00a0lin\u00e9aire<\/strong> (recherche s\u00e9quentielle d’une occurence).
\n4. O(n.log(n))\u00a0 <\/strong>:\u00a0complexit\u00e9\u00a0quasi\u00adlin\u00e9aire.
\n5. O(n^2)\u00a0 <\/strong>:\u00a0complexit\u00e9\u00a0quadratique<\/strong> (tri par insertion).
\n6. O(2^{ polyn\u00f4me(n)}) <\/strong>: complexit\u00e9 exponentielle<\/strong>.<\/p>\n

\n

Ressources<\/h4>\n