{"id":3014,"date":"2020-07-31T16:52:10","date_gmt":"2020-07-31T14:52:10","guid":{"rendered":"https:\/\/www.mathweb.fr\/euclide\/?page_id=3014"},"modified":"2023-04-16T16:18:15","modified_gmt":"2023-04-16T14:18:15","slug":"complexite-algorithmique","status":"publish","type":"page","link":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/","title":{"rendered":"Complexit\u00e9 algorithmique"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">La complexit\u00e9 algorithmique d&rsquo;un programme informatique est d&rsquo;une importance majeure. En effet, c&rsquo;est elle qui permet de v\u00e9rifier l&rsquo;efficacit\u00e9 de ce dernier.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Vous l&rsquo;aurez donc compris, la complexit\u00e9 algorithmique est une <em>grandeur<\/em> : cela peut \u00eatre un nombre, mais c&rsquo;est tr\u00e8s souvent un <em>ordre de grandeur<\/em>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"640\" src=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-1024x640.png\" alt=\"complexit\u00e9 algorithmique python\" class=\"wp-image-3015\" srcset=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-1024x640.png 1024w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-300x188.png 300w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-600x375.png 600w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-768x480.png 768w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique.png 1080w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Un exemple \u00e9l\u00e9mentaire<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Consid\u00e9rons le programme \u00e9l\u00e9mentaire 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=\"\">a, b = 3, 6\nc = a + b\nprint(c)<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">La ligne 1 comporte 2 affectations; la ligne c comporte 1 affectation et une op\u00e9ration \u00e9l\u00e9mentaire (l&rsquo;addition); la ligne 3 de comporte aucune affectation ni op\u00e9ration \u00e9l\u00e9mentaire.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">On dit alors ici que la complexit\u00e9 (le co\u00fbt) du programme est \u00e9gal \u00e0 4. La complexit\u00e9 est <em>constante<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Complexit\u00e9 algorithmique d&rsquo;un programme avec une boucle<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Penchons-nous maintenant sur le 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 fct(n):\n    s = 0\n    for i in range(1,n+1):\n        s += i\n        \n    return s\n\nprint( fct(10) )<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Quelle est la complexit\u00e9 de la fonction <em>fct<\/em>(n) ? On voit qu&rsquo;il y a une premi\u00e8re affectation (s = 0). Ensuite, il y a <em>n<\/em> affectations pour la variable <em>i<\/em> ainsi que <em>n<\/em> op\u00e9rations (<em>s<\/em> + <em>i<\/em>) et <em>n<\/em> autres affectations (pour <em>s<\/em>). Ainsi, au total, il y a 3<em>n<\/em>+1 op\u00e9rations \u00e9l\u00e9mentaires, qui correspond \u00e0 la complexit\u00e9 de la fonction. On dit ici que la complexit\u00e9 est <em>lin\u00e9aire<\/em> car <em>C<\/em>(<em>n<\/em>) = 3<em>n<\/em> + 1, fonction donnant la complexit\u00e9, est une fonction lin\u00e9aire. On dit alors que la complexit\u00e9 est en \\(\\mathcal{O}(n)\\) : cela signifie qu&rsquo;elle est quasi-proportionnelle \u00e0 <em>n<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Complexit\u00e9 algorithmique pour une boucle dans une boucle<\/h2>\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 fctB(n):\n    s = 0\n    for i in range(1,n+1):\n        s += i\n        \n    return s\n\ndef fctA(n):\n    P = 1\n    for j in range(1,n+1):\n        P *= fctB(j)\n        \n    return P\n\nprint( fctA(10) )<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Quelle est la complexit\u00e9 de la fonction <em>fctA<\/em>(n) ? On voit qu&rsquo;il y a 1 premi\u00e8re affectation (P = 1) puis, pour chaque valeur de <em>j<\/em>, il y a 1 affectation (pour la variable <em>j<\/em> elle-m\u00eame), suivie de 3<em>j<\/em> + 1 pour le calcul de <em>fctB<\/em>(<em>j<\/em>), 1 autre op\u00e9ration (le produit de P par fctB(j)) et enfin 1 affectation pour P. Donc, pour \u00eatre plus clair:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>1 affectation avant la boucle;<\/li><li>pour <em>j<\/em> = 1, il y a 1 (<em>j<\/em>) + [3\\(\\times\\)1+1] (<em>fctB<\/em>(1)) + 2 op\u00e9rations \u00e9l\u00e9mentaires;<\/li><li>pour <em>j<\/em> = 2, il y a 1 (<em>j<\/em>) + [3\\(\\times\\)2+1] (<em>fctB<\/em>(2)) + 2 op\u00e9rations \u00e9l\u00e9mentaires;<\/li><li>pour <em>j<\/em> = 3, il y a 1 (<em>j<\/em>) + [3\\(\\times\\)3+1] (<em>fctB<\/em>(3)) + 2 op\u00e9rations \u00e9l\u00e9mentaires;<\/li><li>etc.<\/li><li>pour <em>j<\/em> = <em>n<\/em>, il y a 1 (<em>j<\/em>) + [3\\(\\times\\)<em>n<\/em>+1] (<em>fctB<\/em>(<em>n<\/em>)) + 2 op\u00e9rations \u00e9l\u00e9mentaires.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">La complexit\u00e9 totale est donc:$$\\begin{align}&amp;n\\times1 + 3(1+2+3+\\cdots+n)+n\\times1+2\\times n \\\\=&amp;4n+3\\times\\frac{n(n+1)}{2}\\\\=&amp;\\frac{3}{2}n^2+\\frac{11}{2}n\\end {align}$$C&rsquo;est une complexit\u00e9 polynomiale de degr\u00e9 2. On dit qu&rsquo;elle est <em>quadratique<\/em>, et on dit qu&rsquo;elle est en \\(\\mathcal{O}(n^2)\\).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Complexit\u00e9 algorithmique et recherche dichotomique<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Supposons connue une liste <strong>ordonn\u00e9e<\/strong> de <em>n<\/em> \u00e9l\u00e9ments. Nous souhaitons rechercher de mani\u00e8re <a href=\"https:\/\/www.mathweb.fr\/euclide\/numerique-et-sciences-informatiques-nsi\/\" target=\"_blank\" aria-label=\"undefined (s\u2019ouvre dans un nouvel onglet)\" rel=\"noreferrer noopener\">dichotomique<\/a> si un \u00e9l\u00e9ment donn\u00e9 se trouve dans cette liste. On peut alors imaginer le programme r\u00e9cursif 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 recherche_dichotomique(liste , element):\n    n = len(liste)\n    if len(liste) == 1:\n        if liste[0] == element:\n            return True\n        else:\n            return False\n    elif liste[ n\/\/2 ] == element:\n        return True\n    elif element > liste[n \/\/ 2]:\n        return recherche_dichotomique( liste[n\/\/2:] , element)\n    else:\n        return recherche_dichotomique( liste[:n\/\/2] , element)\n        \nprint( recherche_dichotomique([1,1,1,2,2,3,3,4,5,5,6,6,7,8,8,8,10] , 9 ) )<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Je n&rsquo;ai pas insist\u00e9 sur le fait de trier \u00e0 chaque fois la liste, car cela rajouterait un niveau de plus \u00e0 la complexit\u00e9, l&rsquo;id\u00e9e de cette page \u00e9tant ailleurs.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour ce type de programme, nous n&rsquo;allons pas nous lancer dans le calcul exact du nombre d&rsquo;op\u00e9rations \u00e9l\u00e9mentaires car c&rsquo;est tout simplement impossible car ce nombre d\u00e9pend de l&rsquo;issue. En effet, le nombre peut \u00eatre trouv\u00e9 d\u00e8s le d\u00e9but comme ne pas \u00eatre trouv\u00e9 du tout. Dans ce genre de situation, on pr\u00e9f\u00e8re regarder le nombre <em>maximum<\/em> d&rsquo;op\u00e9rations.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Notons alors <em>k<\/em> ce nombre maximum. Alors, au maximum, la liste sera divis\u00e9e <em>k<\/em> fois par deux et la taille de la \u00ab\u00a0derni\u00e8re liste\u00a0\u00bb (\u00e0 1 \u00e9l\u00e9ment) sera la partie enti\u00e8re de \\(\\displaystyle\\frac{n}{2^k}\\). Ainsi,$$1 \\leqslant \\frac{n}{2^k}$$c&rsquo;est-\u00e0-dire:$$2^k \\leqslant n$$soit:$$k \\leqslant \\log_2(n).$$On dit alors que la complexit\u00e9 est <em>logarithmique<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Les classes de complexit\u00e9<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Nous avons vu \u00e0 travers ces quelques exemples qu&rsquo;il pouvait exister plusieurs types de complexit\u00e9s. On appelle ces types des <em>classes de complexit\u00e9<\/em>. Ces classes peuvent \u00eatre vues ainsi:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"512\" src=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/classes-de-complexit\u00e9-1024x512.png\" alt=\"classes de complexit\u00e9\" class=\"wp-image-3019\" srcset=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/classes-de-complexit\u00e9-1024x512.png 1024w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/classes-de-complexit\u00e9-300x150.png 300w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/classes-de-complexit\u00e9-600x300.png 600w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/classes-de-complexit\u00e9-768x384.png 768w, https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/classes-de-complexit\u00e9.png 1077w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption>Les diff\u00e9rentes classe de complexit\u00e9<\/figcaption><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Source: <a aria-label=\"undefined (s\u2019ouvre dans un nouvel onglet)\" href=\"https:\/\/view.genial.ly\/5e8ed71d186d4e0dec349ef2\/presentation-la-complexite-des-algorithmes\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/view.genial.ly\/5e8ed71d186d4e0dec349ef2\/presentation-la-complexite-des-algorithmes<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Il est donc important de conna\u00eetre la classe de complexit\u00e9 d&rsquo;un algorithme, d&rsquo;un programme, pour savoir s&rsquo;il est performant: en effet, plus sa classe se rapprochera de \\(\\mathcal{O}(1)\\) ou (\\mathcal{O}(\\log(n))) et mieux se sera. Mais il faut aussi avoir \u00e0 l&rsquo;esprit que certains probl\u00e8mes n&rsquo;ont toujours pas de solutions algorithmiques de complexit\u00e9 avantageuse&#8230; pour le moment!<\/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=\"\">n = 100000000\n# l'\u00e9l\u00e8ve de NSI qui ne veut pas faire Maths sp\u00e9cialit\u00e9:\n\ndef fctA(n):\n    s = 0\n    for i in range(1,n+1):\n        s += i\n        \n    return s\n\n# --> complexit\u00e9 du programme = 1 + n + n + n = 3n + 1 (lin\u00e9aire ==> O(n))\n\n# vs\n\n# l'\u00e9l\u00e8ve qui a suivi son cours de math sp\u00e9cialit\u00e9 sur les suites:\n\ndef fctB(n):\n    return n * (n + 1) \/\/ 2\n\n# complexit\u00e9 = 3 (constante ==> O(1))\n\nprint ( fctA(n) ) # prend un max de temps...\nprint ( fctB(n) ) # quasi-imm\u00e9diat !<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La complexit\u00e9 algorithmique d&rsquo;un programme informatique est d&rsquo;une importance majeure. En effet, c&rsquo;est elle qui permet de v\u00e9rifier l&rsquo;efficacit\u00e9 de ce dernier. Vous l&rsquo;aurez donc compris, la complexit\u00e9 algorithmique est une grandeur : cela peut \u00eatre un nombre, mais c&rsquo;est tr\u00e8s souvent un ordre de grandeur. Un exemple \u00e9l\u00e9mentaire Consid\u00e9rons [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3014","page","type-page","status-publish","hentry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.3 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Complexit\u00e9 algorithmique - Mathweb.fr - Exemples concrets en Python<\/title>\n<meta name=\"description\" content=\"Comment calculer la complexit\u00e9 algorithmique ? Voyons cela \u00e0 travers plusieurs exemples de programmes \u00e9crits en Python et parlons de classes de complexit\u00e9.\" \/>\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\/complexite-algorithmique\/\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Complexit\u00e9 algorithmique - Mathweb.fr - Exemples concrets en Python\" \/>\n<meta property=\"og:description\" content=\"Comment calculer la complexit\u00e9 algorithmique ? Voyons cela \u00e0 travers plusieurs exemples de programmes \u00e9crits en Python et parlons de classes de complexit\u00e9.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/\" \/>\n<meta property=\"og:site_name\" content=\"Mathweb.fr\" \/>\n<meta property=\"article:modified_time\" content=\"2023-04-16T14:18:15+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-1024x640.png\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data1\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/\",\"name\":\"Complexit\u00e9 algorithmique - Mathweb.fr - Exemples concrets en Python\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/complexite-algorithmique-1024x640.png\",\"datePublished\":\"2020-07-31T14:52:10+00:00\",\"dateModified\":\"2023-04-16T14:18:15+00:00\",\"description\":\"Comment calculer la complexit\u00e9 algorithmique ? Voyons cela \u00e0 travers plusieurs exemples de programmes \u00e9crits en Python et parlons de classes de complexit\u00e9.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/complexite-algorithmique.png\",\"contentUrl\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/complexite-algorithmique.png\",\"width\":1080,\"height\":675},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/complexite-algorithmique\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Accueil\",\"item\":\"https:\\\/\\\/www.mathweb.fr\\\/euclide\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"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":"Complexit\u00e9 algorithmique - Mathweb.fr - Exemples concrets en Python","description":"Comment calculer la complexit\u00e9 algorithmique ? Voyons cela \u00e0 travers plusieurs exemples de programmes \u00e9crits en Python et parlons de classes de complexit\u00e9.","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\/complexite-algorithmique\/","og_locale":"fr_FR","og_type":"article","og_title":"Complexit\u00e9 algorithmique - Mathweb.fr - Exemples concrets en Python","og_description":"Comment calculer la complexit\u00e9 algorithmique ? Voyons cela \u00e0 travers plusieurs exemples de programmes \u00e9crits en Python et parlons de classes de complexit\u00e9.","og_url":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/","og_site_name":"Mathweb.fr","article_modified_time":"2023-04-16T14:18:15+00:00","og_image":[{"url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-1024x640.png","type":"","width":"","height":""}],"twitter_card":"summary_large_image","twitter_misc":{"Dur\u00e9e de lecture estim\u00e9e":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/","url":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/","name":"Complexit\u00e9 algorithmique - Mathweb.fr - Exemples concrets en Python","isPartOf":{"@id":"https:\/\/www.mathweb.fr\/euclide\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/#primaryimage"},"image":{"@id":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/#primaryimage"},"thumbnailUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique-1024x640.png","datePublished":"2020-07-31T14:52:10+00:00","dateModified":"2023-04-16T14:18:15+00:00","description":"Comment calculer la complexit\u00e9 algorithmique ? Voyons cela \u00e0 travers plusieurs exemples de programmes \u00e9crits en Python et parlons de classes de complexit\u00e9.","breadcrumb":{"@id":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/#breadcrumb"},"inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/"]}]},{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/#primaryimage","url":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique.png","contentUrl":"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/complexite-algorithmique.png","width":1080,"height":675},{"@type":"BreadcrumbList","@id":"https:\/\/www.mathweb.fr\/euclide\/complexite-algorithmique\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Accueil","item":"https:\/\/www.mathweb.fr\/euclide\/"},{"@type":"ListItem","position":2,"name":"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\/pages\/3014","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/types\/page"}],"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=3014"}],"version-history":[{"count":0,"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/pages\/3014\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.mathweb.fr\/euclide\/wp-json\/wp\/v2\/media?parent=3014"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}