{"id":1100,"date":"2019-03-19T17:01:52","date_gmt":"2019-03-19T16:01:52","guid":{"rendered":"https:\/\/www.mathweb.fr\/euclide\/?p=1100"},"modified":"2020-04-19T16:27:41","modified_gmt":"2020-04-19T14:27:41","slug":"initiation-a-la-complexite-algorithmique","status":"publish","type":"post","link":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/","title":{"rendered":"Initiation \u00e0 la complexit\u00e9 algorithmique"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Loin de moi l&rsquo;id\u00e9e de faire un article complet sur la notion de complexit\u00e9, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur \u00e0 la rentr\u00e9e 2019), je me suis aper\u00e7u que cette notion allait pointer le bout de son petit museau perfide&#8230; Je voudrais donc par cet article familiariser les \u00e9l\u00e8ves avec elle.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-white ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Au menu sur cette page...<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Cest_quoi_la_complexite_dun_algorithme\" >C&rsquo;est quoi la complexit\u00e9 d&rsquo;un algorithme ?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Exercice_1\" >Exercice 1<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Solution\" >Solution<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Structures_iteratives\" >Structures it\u00e9ratives<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Exercice_2\" >Exercice 2<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Solution-2\" >Solution<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Exercice_3\" >Exercice 3<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Solution-3\" >Solution<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Ordre_de_grandeur_de_la_complexite\" >Ordre de grandeur de la complexit\u00e9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Fonction_recursive\" >Fonction r\u00e9cursive<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Generalites\" >G\u00e9n\u00e9ralit\u00e9s<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Exercice_4\" >Exercice 4<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#Solution-4\" >Solution<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Cest_quoi_la_complexite_dun_algorithme\"><\/span>C&rsquo;est quoi la complexit\u00e9 d&rsquo;un algorithme ?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">C&rsquo;est le nombre d&rsquo;op\u00e9rations et d&rsquo;affectations faites. On appelle cela des <em>op\u00e9rations \u00e9l\u00e9mentaires<\/em>. Prenons le programme Python suivant:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def convert(n):\n    h = n \/\/ 3600\n    m = (n - 3600*h) \/\/ 60\n    s = n % 60\n    return h,m,s\n\nn = 102152\n\nprint(\"{} secondes = {} h {} min {} sec.\".format(n,convert(n)[0],convert(n)[1],convert(n)[2]))\n<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Dans la fonction \u00ab\u00a0convert\u00a0\u00bb, il y a :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>3 affectations (h, m et s)<\/li><li>5 op\u00e9rations (n\/\/3600, 3600*h, n-3600*h, (n-3600*h)\/\/60 et n%60)<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">La complexit\u00e9 de cette fonction est donc \u00e9gale \u00e0 8.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exercice_1\"><\/span>Exercice 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Montrer que la complexit\u00e9 de la fonction suivante est \u00e9gale \u00e0 5.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def myFunction(n):\n    if n%3 == 0:\n        p = n\/3 + 2\n    else:\n        p = n*2 + 1\n    return p<\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution\"><\/span>Solution<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">il y a d&rsquo;abord un test (if) dans lequel il y a une op\u00e9ration (n%3), ce qui nous fait pour le moment une complexit\u00e9 de 2.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ensuite, quelle que soit l&rsquo;issue du test, il y a 1 affectation (p) et 2 op\u00e9rations (pour calculer p), soit une complexit\u00e9 augment\u00e9e de 3.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Au final, on obtient bien une complexit\u00e9 de 5.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Structures_iteratives\"><\/span>Structures it\u00e9ratives<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Dans un programme, il y a souvent des boucles. Nous allons voir un exemple avec une boucle \u00ab\u00a0for\u00a0\u00bb:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def recherche(l,x):\n    for i in range(len(l)):\n        if l[i]==x:\n            return i\n    return -1\n\nl = \"Bonjour.\"\nx = \"p\"\n\nprint(recherche(l,x))<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">La fonction <em>recherche<\/em> a pour but d&rsquo;afficher le rang o\u00f9 se trouve le caract\u00e8re \u00ab\u00a0x\u00a0\u00bb dans la cha\u00eene de caract\u00e8res \u00ab\u00a0l\u00a0\u00bb, et affiche \u00ab\u00a0-1\u00a0\u00bb si ce dernier n&rsquo;est pas trouv\u00e9.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Au niveau de la boucle <em>for<\/em>, il y a 1 addition (sur i), une affectation (i) et une comparaison (test si i&lt;len(l));<\/li><li>dans la boucle <em>for<\/em>, il y a un test (if l[i]==x).<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Au final, si <em>n<\/em> est la longueur de la cha\u00eene de caract\u00e8res, il y a 4<em>n<\/em> op\u00e9rations \u00e9l\u00e9mentaires, qui correspond \u00e0 la complexit\u00e9 de la fonction <em>recherche<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exercice_2\"><\/span>Exercice 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Calculer la complexit\u00e9 de la fonction <em>somme<\/em> d\u00e9finie dans ce programme:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def somme(n):\n    s = 0\n    for i in range(n+1):\n        s += i\n    return s\n\nprint(somme(100))<\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution-2\"><\/span>Solution<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Il y a :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>au d\u00e9but, 1 affectation (s = 0);<\/li><li>au niveau de la boucle <em>for<\/em>, 3 op\u00e9rations \u00e9l\u00e9mentaires (affectation sur i, op\u00e9ration d&rsquo;incr\u00e9mentation sur i, test sur i);<\/li><li>dans la boucle <em>for<\/em>, il y a 2 op\u00e9rations \u00e9l\u00e9mentaires (1 affectation sur s et une op\u00e9ration sur s).<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Ainsi, il y a 5 op\u00e9rations \u00e9l\u00e9mentaires dans la boucle, r\u00e9p\u00e9t\u00e9es <em>n<\/em> fois, plus la premi\u00e8re (hors boucle). La complexit\u00e9 de la fonction <em>somme<\/em> est donc \u00e9gale \u00e0 5<em>n<\/em>+1.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En g\u00e9n\u00e9ral, on appelle <em>T<\/em> la complexit\u00e9 (initiale de <em>Time<\/em>).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exercice_3\"><\/span>Exercice 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Calculer la complexit\u00e9 de la fonction <em>mystere<\/em> du programme suivant:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def mystere(n):\n    m = 0\n    for i in range(n):\n        for j in range(i):\n            m += i+j\n    return m\n\nprint(mystere(100))<\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution-3\"><\/span>Solution<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Il y a avant tout 1 affectation d\u00e8s le d\u00e9but (m=0);<\/li><li>ensuite, au niveau de la boucle sur i, 3 op\u00e9rations \u00e9l\u00e9mentaires;<\/li><li>au niveau de la boucle sur j, il y a 3 op\u00e9rations \u00e9l\u00e9mentaires r\u00e9p\u00e9t\u00e9es i fois;<\/li><li>dans la boucle sur j, il y a 3 op\u00e9rations \u00e9l\u00e9mentaires (1 affectation sur m, une somme sur m et une somme de i et j).<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Ainsi, \u00e0 part la premi\u00e8re affectation, il y a 9 op\u00e9rations \u00e9l\u00e9mentaires pour chaque valeur de j possible. Il y a:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>1 valeur possible de j quand i=0 (j=0);<\/li><li>1 valeur possible de j quand i=1 (j=0);<\/li><li>2 valeurs possibles de j pour i=2 (j=0 et j=1):<\/li><li>etc.<\/li><li><em>n<\/em>-1 valeurs possibles de j pour i=<em>n<\/em>-1.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">La complexit\u00e9 est donc \u00e9gale \u00e0:$$\\begin{aligned} &amp; 1+9\\times(1+1+2+3+\\cdots+(n-1))\\\\=\\ &amp; 10+\\frac{9n(n-1)}{2}\\\\=\\ &amp; \\frac{1}{2}(9n^2-9n+20).\\end{aligned}$$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Ordre_de_grandeur_de_la_complexite\"><\/span>Ordre de grandeur de la complexit\u00e9<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Nous le voyons dans l&rsquo;exemple pr\u00e9c\u00e9dent, la complexit\u00e9 peut s&rsquo;exprimer par un polyn\u00f4me. Dans un tel cas, si <em>n<\/em> est relativement grand, on pourra assimiler la complexit\u00e9 \u00e0 son ordre de grandeur. Par exemple ici, la complexit\u00e9 de la derni\u00e8re fonction est de l&rsquo;ordre de \\(n^2\\). On \u00e9crira alors:$$T_n=O(n^2).$$On dira ici que la complexit\u00e9 est <em>quadratique<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour l&rsquo;exercice 2, \\(T_n=5n+1=O(n)\\). On dira que la complexit\u00e9 est <em>lin\u00e9aire<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Fonction_recursive\"><\/span>Fonction r\u00e9cursive<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Une des fonctions r\u00e9cursives la plus simple est celle qui permet de calculer <em>n<\/em>! (la factorielle de <em>n<\/em>), c&rsquo;est-\u00e0-dire \\(2\\times3\\times\\cdots\\times n\\).<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def factorielle(n):\n    if n == 0:\n        return 1\n    else:\n        return n*factorielle(n-1)<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Il y a un test pour commencer (sur <em>n<\/em>). Si le test est vrai, on s&rsquo;arr\u00eate, sinon on effectue une op\u00e9ration (un produit) en faisant appel \u00e0 la m\u00eame fonction. Ainsi, si <em>n<\/em> est non nul, il y a 2 op\u00e9rations \u00e9l\u00e9mentaires + le nombre d&rsquo;op\u00e9rations \u00e9l\u00e9mentaires de la fonction au rang <em>n<\/em> &#8211; 1.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Si \\(T_n\\) repr\u00e9sente la complexit\u00e9 de la fonction <em>factorielle(n)<\/em> alors:$$T_n=T_{n-1}+2,\\quad T_0=1.$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La complexit\u00e9 est donc donn\u00e9e par une suite arithm\u00e9tico-g\u00e9om\u00e9trique. C&rsquo;est toujours le cas pour les fonctions r\u00e9cursives.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">On peut alors montrer que \\(T_n=2n+1=O(n).\\)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Generalites\"><\/span>G\u00e9n\u00e9ralit\u00e9s<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Si on consid\u00e8re une fonction <em>toto<\/em>(<em>n<\/em>) dans laquelle on fait appel \u00e0 cette m\u00eame fonction <em>a<\/em> fois et dans laquelle il y a <em>b<\/em> op\u00e9rations \u00e9l\u00e9mentaires, si on note \\(T_n\\) sa complexit\u00e9 alors:$$T_n=aT_{n-1}+b.$$Ainsi, \\(T_n=O(a^n)\\). La complexit\u00e9 est alors <em>exponentielle<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exercice_4\"><\/span> Exercice 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Quelle est la complexit\u00e9 de la fonction suivante:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"dracula\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def fibo(n):\n    if n&lt;2:\n        return n\n    else:\n        return fibo(n-1) + fibo(n-2)<\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution-4\"><\/span>Solution<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Il y a 2 op\u00e9rations \u00e9l\u00e9mentaires (un test sur <em>n<\/em> et une addition de fibo(n-1) et fibo(n-1)) donc:$$T_n=T_{n-1}+T_{n-2}+2,\\quad T_0=T_1=1.$$ La complexit\u00e9 est donc une suite lin\u00e9aire d&rsquo;ordre 2 et d&rsquo;\u00e9quation caract\u00e9ristique:$$r^2-r-1=0$$ de solutions \\(r_1=\\frac{1+\\sqrt5}{2}\\) et \\(r_2=\\frac{1-\\sqrt5}{2}\\). Comme \\(|r_1|&gt;|r_2|\\), une propri\u00e9t\u00e9 nous dit que la complexit\u00e9 de la fonction <em>fibo<\/em>(<em>n<\/em>) est:$$T_n=O(r_1^n).$$La complexit\u00e9 est alors exponentielle.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Loin de moi l&rsquo;id\u00e9e de faire un article complet sur la notion de complexit\u00e9, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur \u00e0 la rentr\u00e9e 2019), je me suis aper\u00e7u que cette notion allait pointer le bout de son petit museau perfide&#8230; Je voudrais donc [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[21,4,5],"tags":[94,93,95,96],"class_list":["post-1100","post","type-post","status-publish","format-standard","hentry","category-enseignement","category-informatique","category-python","tag-algorithmique","tag-complexite","tag-factorielle","tag-fibonacci"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Initiation \u00e0 la complexit\u00e9 algorithmique - Mathweb.fr<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Initiation \u00e0 la complexit\u00e9 algorithmique - Mathweb.fr\" \/>\n<meta property=\"og:description\" content=\"Loin de moi l&rsquo;id\u00e9e de faire un article complet sur la notion de complexit\u00e9, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur \u00e0 la rentr\u00e9e 2019), je me suis aper\u00e7u que cette notion allait pointer le bout de son petit museau perfide&#8230; Je voudrais donc [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/\" \/>\n<meta property=\"og:site_name\" content=\"Mathweb.fr\" \/>\n<meta property=\"article:published_time\" content=\"2019-03-19T16:01:52+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-04-19T14:27:41+00:00\" \/>\n<meta name=\"author\" content=\"St\u00e9phane Pasquet\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"St\u00e9phane Pasquet\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/\"},\"author\":{\"name\":\"St\u00e9phane Pasquet\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"headline\":\"Initiation \u00e0 la complexit\u00e9 algorithmique\",\"datePublished\":\"2019-03-19T16:01:52+00:00\",\"dateModified\":\"2020-04-19T14:27:41+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/\"},\"wordCount\":974,\"commentCount\":6,\"publisher\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"keywords\":[\"algorithmique\",\"complexit\u00e9\",\"factorielle\",\"fibonacci\"],\"articleSection\":[\"Enseignement\",\"Informatique\",\"Python\"],\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/\",\"name\":\"Initiation \u00e0 la complexit\u00e9 algorithmique - Mathweb.fr\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\"},\"datePublished\":\"2019-03-19T16:01:52+00:00\",\"dateModified\":\"2020-04-19T14:27:41+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/2019\\\/03\\\/19\\\/initiation-a-la-complexite-algorithmique\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Accueil\",\"item\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Initiation \u00e0 la complexit\u00e9 algorithmique\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\",\"name\":\"Mathweb.fr\",\"description\":\"Math\u00e9matiques, LaTeX et Python\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"fr-FR\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#\\\/schema\\\/person\\\/e4d3bb07968238378f0d5052a70dcd69\",\"name\":\"St\u00e9phane Pasquet\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"contentUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\",\"width\":74,\"height\":77,\"caption\":\"St\u00e9phane Pasquet\"},\"logo\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2025\\\/06\\\/cropped-logo-mathweb.webp\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Initiation \u00e0 la complexit\u00e9 algorithmique - Mathweb.fr","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/","og_locale":"fr_FR","og_type":"article","og_title":"Initiation \u00e0 la complexit\u00e9 algorithmique - Mathweb.fr","og_description":"Loin de moi l&rsquo;id\u00e9e de faire un article complet sur la notion de complexit\u00e9, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur \u00e0 la rentr\u00e9e 2019), je me suis aper\u00e7u que cette notion allait pointer le bout de son petit museau perfide&#8230; Je voudrais donc [&hellip;]","og_url":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/","og_site_name":"Mathweb.fr","article_published_time":"2019-03-19T16:01:52+00:00","article_modified_time":"2020-04-19T14:27:41+00:00","author":"St\u00e9phane Pasquet","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"St\u00e9phane Pasquet","Dur\u00e9e de lecture estim\u00e9e":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#article","isPartOf":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/"},"author":{"name":"St\u00e9phane Pasquet","@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"headline":"Initiation \u00e0 la complexit\u00e9 algorithmique","datePublished":"2019-03-19T16:01:52+00:00","dateModified":"2020-04-19T14:27:41+00:00","mainEntityOfPage":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/"},"wordCount":974,"commentCount":6,"publisher":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"keywords":["algorithmique","complexit\u00e9","factorielle","fibonacci"],"articleSection":["Enseignement","Informatique","Python"],"inLanguage":"fr-FR","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/","url":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/","name":"Initiation \u00e0 la complexit\u00e9 algorithmique - Mathweb.fr","isPartOf":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#website"},"datePublished":"2019-03-19T16:01:52+00:00","dateModified":"2020-04-19T14:27:41+00:00","breadcrumb":{"@id":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#breadcrumb"},"inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.mathweb.fr\/euclide\/2019\/03\/19\/initiation-a-la-complexite-algorithmique\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Accueil","item":"https:\/\/www.mathweb.fr\/euclide\/"},{"@type":"ListItem","position":2,"name":"Initiation \u00e0 la complexit\u00e9 algorithmique"}]},{"@type":"WebSite","@id":"https:\/\/www.mathweb.fr\/euclide\/#website","url":"https:\/\/www.mathweb.fr\/euclide\/","name":"Mathweb.fr","description":"Math\u00e9matiques, LaTeX et Python","publisher":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.mathweb.fr\/euclide\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"fr-FR"},{"@type":["Person","Organization"],"@id":"https:\/\/www.mathweb.fr\/euclide\/#\/schema\/person\/e4d3bb07968238378f0d5052a70dcd69","name":"St\u00e9phane Pasquet","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","contentUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp","width":74,"height":77,"caption":"St\u00e9phane Pasquet"},"logo":{"@id":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2025\/06\/cropped-logo-mathweb.webp"}}]}},"_links":{"self":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/posts\/1100","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/comments?post=1100"}],"version-history":[{"count":0,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/posts\/1100\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/media?parent=1100"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/categories?post=1100"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/tags?post=1100"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}