{"id":15139,"date":"2022-04-17T08:58:10","date_gmt":"2022-04-17T07:58:10","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15139"},"modified":"2024-02-11T13:55:55","modified_gmt":"2024-02-11T12:55:55","slug":"exercices-complexite-en-temps","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/","title":{"rendered":"7 Corrected exercises on time complexity"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"15139\" class=\"elementor elementor-15139\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-552225d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"552225d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-0ad6dec\" data-id=\"0ad6dec\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f985760 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f985760\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/algorithmique\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmique<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-645cdc7\" data-id=\"645cdc7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5534d71 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5534d71\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7154b43\" data-id=\"7154b43\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-24ce7cc elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"24ce7cc\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithm\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ce6f497 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ce6f497\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c127a2b\" data-id=\"c127a2b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-74dde4f elementor-widget elementor-widget-text-editor\" data-id=\"74dde4f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f2f1841 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f2f1841\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1a9516b\" data-id=\"1a9516b\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-b72fdb8 elementor-widget elementor-widget-heading\" data-id=\"b72fdb8\" data-element_type=\"widget\" data-widget_type=\"heading.default\"><div class=\"elementor-widget-container\"><div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/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:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercices-corriges-sur-la-complexite-en-temps\" >Exercices corrig\u00e9s sur la complexit\u00e9 en temps<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-1\" >Exercice 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-2\" >Exercice 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-3\" >Exercice 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-4\" >Exercice 4<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-5\" >Exercice 5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-6\" >Exercice 6<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/corrected-exercises-on-time-complexity\/#Exercice-7\" >Exercice 7<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-sur-la-complexite-en-temps\"><\/span>Exercices corrig\u00e9s sur la complexit\u00e9 en temps<span class=\"ez-toc-section-end\"><\/span><\/h2><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section><section class=\"elementor-section elementor-top-section elementor-element elementor-element-37d19a9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"37d19a9\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-42e4741\" data-id=\"42e4741\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-1af5f92 elementor-widget elementor-widget-text-editor\" data-id=\"1af5f92\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\"><div class=\"elementor-widget-container\"><div class=\"elementor-text-editor elementor-clearfix\"><p>Les exercices corrig\u00e9s suivants concernent l&rsquo;analyse d&rsquo;algorithmes, en particulier l&rsquo;exactitude, l&rsquo;exhaustivit\u00e9 et le calcul de la complexit\u00e9 en temps.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"calcul de la complexit\u00e9 en temps\" width=\"97\" height=\"97\" title=\"\"><\/p><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-dc806ca elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"dc806ca\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7af1385\" data-id=\"7af1385\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b96a4e9 elementor-widget elementor-widget-heading\" data-id=\"b96a4e9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercice 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b939d64 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b939d64\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3261052\" data-id=\"3261052\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0d66eb0 elementor-widget elementor-widget-text-editor\" data-id=\"0d66eb0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">D\u00e9terminez la complexit\u00e9 temporelle de l&rsquo;algorithme Check\u00a0:<\/span><\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-10595 size-full\" title=\"Corrected Exercises: Time Complexity 1\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture.png\" alt=\"complexit\u00e9 en temps complexit\u00e9 correction terminaison algorithme exercices corrig\u00e9s\" width=\"648\" height=\"334\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture.png 648w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture-300x155.png 300w\" sizes=\"(max-width: 648px) 100vw, 648px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-84b57a3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"84b57a3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d4d89cb\" data-id=\"d4d89cb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-158f88c elementor-widget elementor-widget-toggle\" data-id=\"158f88c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2261\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2261\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2261\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2261\"><p>Avant de calculer la complexit\u00e9, il faut v\u00e9rifier si l\u2019algorithme se termine. Les \u00e9l\u00e9ments de la matrice sont des entiers, donc peuvent d\u00e9passer la valeur de 9, ce qui signifie que tab[value-1] sort de la taille du tableau. L\u2019algorithme n\u2019est donc pas viable et inutile de continuer l\u2019analyse plus loin.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d09c11c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d09c11c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ed8fc70\" data-id=\"ed8fc70\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-47007f8 elementor-widget elementor-widget-heading\" data-id=\"47007f8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercice 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e494604 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e494604\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8d09f34\" data-id=\"8d09f34\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5dd70e6 elementor-widget elementor-widget-text-editor\" data-id=\"5dd70e6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Analyser la complexit\u00e9 de l&rsquo;algorithme. \u00c9crivez un autre <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithme<\/a> qui fait exactement la m\u00eame chose qu&rsquo;Algorithm mais avec une complexit\u00e9 en temps asymptotique strictement meilleure.<\/span><\/p><p><img decoding=\"async\" class=\"alignnone wp-image-10597 size-full\" title=\"Corrected Exercises: Time Complexity 2\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture2.png\" alt=\"complexit\u00e9 en temps complexit\u00e9 correction terminaison algorithme exercices corrig\u00e9s\" width=\"315\" height=\"421\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture2.png 315w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture2-224x300.png 224w\" sizes=\"(max-width: 315px) 100vw, 315px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4ebec44 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4ebec44\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-754c0e0\" data-id=\"754c0e0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0382071 elementor-widget elementor-widget-toggle\" data-id=\"0382071\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-3671\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-3671\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-3671\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-3671\"><p><span style=\"font-weight: 400;\">L\u2019algorithme est vraiment compliqu\u00e9 \u00e0 comprendre. Le plus simple est de tester son fonctionnement avec un petit vecteur comme par exemple &lt;3, 5, 4, 4, 5, 7&gt;. Je vous laisse tester pas \u00e0 pas sur papier.<\/span><\/p><p><span style=\"font-weight: 400;\">Dans la boucle, quand deux cases sont identiques, on incr\u00e9mente la valeur de c. Compte tenu du contenu s\u00e9quentiel dans la boucle, i reste stable tandis que j \u00e9volue. Donc on compte le nombre d\u2019occurence dans le tableau de la valeur de la case i. Le deuxi\u00e8me embranchement donne une condition lorsque j atteint sort de la taille du vecteur. Dans ce cas on v\u00e9rifie que le nombre d\u2019occurence de la valeur de la case i d\u00e9passe le dernier compte enregistr\u00e9 dans m. Puis on incr\u00e9mente i et place j sur la m\u00eame case.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Cela ne change pas le fonctionnement de trouver le nombre d\u2019occurence de chaque case car si la valeur se trouvait avant, il a d\u00e9j\u00e0 \u00e9t\u00e9 compt\u00e9 dans sa totalit\u00e9. Justement, faire commencer i et j au m\u00eame endroit produit moins de calcul.<\/span><\/p><p><span style=\"font-weight: 400;\">Si on reprend le fonctionnement, i et j se trouvent sur la m\u00eame case. j incr\u00e9mente jusqu\u2019\u00e0 la fin du tableau. Puis i avance d\u2019une case et j se place au m\u00eame endroit. Le nombre d\u2019it\u00e9ration est donc la somme de n (taille du tableau) \u00e0 1, soit n(n-1)\/2. Les deux embranchements ont la m\u00eame complexit\u00e9 en 0(1), donc la complexit\u00e9 de l\u2019algorithme est de O(n\u00b2).<\/span><\/p><p><span style=\"font-weight: 400;\">Pour faire plus simple, il suffit de r\u00e9aliser l\u2019algorithme en deux temps. Dans un premier temps, on trie le tableau (possible en O(n log(n)).Puis on lit le tableau par deux cases tab[i] et tab[i+1]. Tant que les valeurs sont \u00e9gales, on incr\u00e9mente un compteur c. Si c\u2019est diff\u00e9rent, on regarde si c&gt;m comme l\u2019algorithme propos\u00e9. La complexit\u00e9 est donc de O(n log(n) + n), soit O(n log(n)).<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f59cca0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f59cca0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d3b517e\" data-id=\"d3b517e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0599d7d elementor-widget elementor-widget-heading\" data-id=\"0599d7d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercice 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8210952 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8210952\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c93b88b\" data-id=\"c93b88b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9655885 elementor-widget elementor-widget-text-editor\" data-id=\"9655885\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Remplir les deux tableaux ci-dessous :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19279 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity.png\" alt=\"complexit\u00e9\" width=\"472\" height=\"374\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity.png 472w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity-300x238.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity-15x12.png 15w\" sizes=\"(max-width: 472px) 100vw, 472px\" \/><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19281 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity2.png\" alt=\"complexit\u00e9\" width=\"488\" height=\"295\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity2.png 488w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity2-300x181.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity2-18x12.png 18w\" sizes=\"(max-width: 488px) 100vw, 488px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ac7f0e8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac7f0e8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b5a1b0c\" data-id=\"b5a1b0c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c9b23a9 elementor-widget elementor-widget-toggle\" data-id=\"c9b23a9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2111\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2111\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2111\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2111\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19282 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity3.png\" alt=\"complexit\u00e9\" width=\"502\" height=\"760\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity3.png 502w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity3-198x300.png 198w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/complexity3-8x12.png 8w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3faa712 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3faa712\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8f92f57\" data-id=\"8f92f57\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f53f139 elementor-widget elementor-widget-heading\" data-id=\"f53f139\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Exercice 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ad2fd72 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ad2fd72\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-16738db\" data-id=\"16738db\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ada5022 elementor-widget elementor-widget-text-editor\" data-id=\"ada5022\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Quel est le temps d&rsquo;ex\u00e9cution (asymptotique) de chacun des algorithmes suivants, en fonction de n ? Justifiez vos r\u00e9ponses.<\/span><\/p>\n<p>a)<\/p>\n<pre>for i = 1 to n do<br>  &nbsp;&nbsp; for j = 1 to 2n + 1 do<br>  &nbsp;&nbsp; &nbsp;&nbsp; print (\u00ab Hello World \u00bb)<br>  &nbsp;&nbsp; end for<br>end for<\/pre>\n<p>b)<\/p>\n<pre>for i = 1 to 10 do<br>  &nbsp;&nbsp; for j = 1 to n do<br>  &nbsp;&nbsp; &nbsp;&nbsp; print (\u00ab&nbsp;Hello World&nbsp;\u00bb)<br>  &nbsp;&nbsp; end for<br>end for<\/pre>\n<p>c)<\/p>\n<pre>for i = 1 to n do<br>  &nbsp;&nbsp; for j = i to n do<br>  &nbsp;&nbsp; &nbsp;&nbsp; print (\u00ab&nbsp;Hello World&nbsp;\u00bb)<br>  &nbsp;&nbsp; end for<br>end for<\/pre>\n<p>d)<\/p>\n<pre>for i = 1 to n do<br>  &nbsp;&nbsp; for j = 1 to 2 \u2217&nbsp;i + 1 do<br>  &nbsp;&nbsp; &nbsp;&nbsp; print (\u00ab&nbsp;Hello World&nbsp;\u00bb)<br>  &nbsp;&nbsp; end for<br>end for<\/pre>\n<p>e)<\/p>\n<pre>for i = 1 to n \u2217 n do<br>  &nbsp;&nbsp; for j = 1 to i do<br>  &nbsp;&nbsp; &nbsp;&nbsp; print (\u00ab&nbsp;Hello World&nbsp;\u00bb)<br>  &nbsp;&nbsp; end for<br>end for<\/pre>\n<p>f)<\/p>\n<pre>for i = 0 to m do<br>  &nbsp;&nbsp; t \u2190 1<br>  &nbsp;&nbsp; while (t &lt; m) do<br>  &nbsp;&nbsp; &nbsp;&nbsp; print (\u00ab&nbsp;Hello world&nbsp;\u00bb)<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; t \u2190 t \u2217 2<br>  &nbsp;&nbsp; end while<br>end for<\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7bcb3d6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7bcb3d6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d9401f6\" data-id=\"d9401f6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b697ef0 elementor-widget elementor-widget-toggle\" data-id=\"b697ef0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1911\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1911\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1911\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1911\"><p><span style=\"font-weight: 400;\">a) O(n\u00b2). Ici la premi\u00e8re boucle fait (n-1) it\u00e9rations et la deuxi\u00e8me boucle 2n it\u00e9rations, donc un total de (n-1)*2n.<\/span><\/p><p><span style=\"font-weight: 400;\">b) O(n). Ici la premi\u00e8re boucle fait 10 it\u00e9rations et la deuxi\u00e8me boucle n it\u00e9rations, donc un total de 10n. Attention, selon certain calcul cela ferait 9 it\u00e9rations suivi de n-1 it\u00e9rations. Heureusement, dans la <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">notation de Landau<\/a> cela ne change rien donc inutile de chipoter pour le comptage d&rsquo;it\u00e9rations !<\/span><\/p><p><span style=\"font-weight: 400;\">c) O(n\u00b2). Tr\u00e8s classique, chaque boucle fait n-1 it\u00e9rations.<\/span><\/p><p><span style=\"font-weight: 400;\">d) O(n\u00b2). La premi\u00e8re boucle est classique. La deuxi\u00e8me va de 1 \u00e0 2i+1, donc si on fait quelques exemples : 3, 5, 7, \u2026, 2n+1 (ici on fait fonctionner les deux boucles en m\u00eame temps). On a donc la somme des n premiers termes inpairs donc quadratique.<\/span><\/p><p>Il est aussi possible de calculer la complexit\u00e9 en multipliant la complexit\u00e9 de chacune des boucles. La premi\u00e8re boucle tend vers n it\u00e9rations quand n est grand; la deuxi\u00e8me boucle tend vers n it\u00e9rations quand n est grand. Nous avons donc une complexit\u00e9 de O(n*n)=O(n\u00b2).<\/p><p>Attention \u00e0 bien v\u00e9rifier quand m\u00eame le nombre d&rsquo;it\u00e9ration quand n est grand, ce ne sera pas toujours en O(n) !<\/p><p><span style=\"font-weight: 400;\">e) O(n^<\/span><span style=\"font-weight: 400;\">4<\/span><span style=\"font-weight: 400;\">). La r\u00e9flection est la m\u00eame que pour l\u2019algorithme d. Ici, nous avons les n premiers termes au carr\u00e9.<\/span><\/p><p><span style=\"font-weight: 400;\">f) O(m log(m)). Pour la premi\u00e8re boucle tout va bien, le probl\u00e8me va venir de la deuxi\u00e8me. Ici la valeur de t double \u00e0 chaque it\u00e9ration et la boucle s\u2019arr\u00eate quand t d\u00e9passe la valeur de m. On pose k le nombre d\u2019it\u00e9ration r\u00e9alis\u00e9e. On s\u2019arr\u00eate quand 2^<\/span><span style=\"font-weight: 400;\">k<\/span><span style=\"font-weight: 400;\"> &gt;m donc quand k &gt; log(m). D\u2019o\u00f9 la complexit\u00e9.<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-af4754b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"af4754b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5ea1525\" data-id=\"5ea1525\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5dd4a6e elementor-widget elementor-widget-heading\" data-id=\"5dd4a6e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Exercice 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e2e1777 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e2e1777\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0b39b83\" data-id=\"0b39b83\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1241b9f elementor-widget elementor-widget-text-editor\" data-id=\"1241b9f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Soient T<\/span><sub style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight );\">A<\/sub><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">(n), T<\/span><sub style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight );\">B<\/sub><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">(n) et T<\/span><sub style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight );\">C<\/sub><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">(n) les temps d&rsquo;\u00e9xecution des algorithmes A, B et C, respectivement.<\/span><\/p><pre>Instruction A<br \/>if (n &lt; 100) then<br \/> \u00a0\u00a0\u00a0 Instruction B<br \/>else<br \/> \u00a0\u00a0\u00a0 for (j = 1 to n) do<br \/> \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 Instruction C<br \/> \u00a0\u00a0\u00a0 end for<br \/>end if<\/pre><p>Quelle est la dur\u00e9e d&rsquo;ex\u00e9cution de cet algorithme, sous chacun des ensembles d&rsquo;hypoth\u00e8ses suivants\u00a0? Justifiez vos r\u00e9ponses.<\/p><ol><li>T<sub>A<\/sub>(n) = O(n), T<sub>B<\/sub>(n) = O(n<sup>2<\/sup>) et T<sub>C<\/sub>(n) = O(log n).<\/li><li>T<sub>A<\/sub>(n) = O(n<sup>2<\/sup>), T<sub>B<\/sub>(n) = O(n<sup>2<\/sup>) et T<sub>C<\/sub>(n) = O(log n).<\/li><li>T<sub>A<\/sub>(n) = O(n<sup>2<\/sup>), T<sub>B<\/sub>(n) = O(n<sup>3<\/sup>) et T<sub>C<\/sub>(n) = O(log n).<\/li><\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-205a74f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"205a74f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d9cd256\" data-id=\"d9cd256\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9b15ad2 elementor-widget elementor-widget-toggle\" data-id=\"9b15ad2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1621\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1621\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1621\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1621\"><p>\u00c9tant donn\u00e9 que les grandes valeurs de n d\u00e9terminent le temps d&rsquo;ex\u00e9cution asymptotique, nous pouvons n\u00e9gliger la partie if de l&rsquo;instruction if. Par cons\u00e9quent, dans tous les cas, le temps d&rsquo;ex\u00e9cution de cet algorithme est O(TA(n) + nTC(n)).<\/p><ol><li>O(n log n)<\/li><li>O(n\u00b2)<\/li><li>O(n\u00b2)<\/li><\/ol><p>Si vous avez un doute sur vous pouvez aussi utiliser la formule classique en cas d&#8217;embranchement 0(max(T_branches)). Dans ce cas, on aurait eu O(TA(n) + max(TC(n), nTC(n)) ).<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ac744c9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac744c9\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2442c1b\" data-id=\"2442c1b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7a2b9c9 elementor-widget elementor-widget-heading\" data-id=\"7a2b9c9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Exercice 6<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-adc61ac elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"adc61ac\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f3031d0\" data-id=\"f3031d0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c9ee172 elementor-widget elementor-widget-text-editor\" data-id=\"c9ee172\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Quelle est la complexit\u00e9, dans le pire des cas, de chacun des fragments de code suivants\u00a0?<\/span><\/p><p>Deux boucles d&rsquo;affil\u00e9e :<\/p><ol><li>for (i = 0; i &lt; N; i++) {<\/li><li>sequence of statements}<\/li><li>for (j = 0; j &lt; M; j++) {<\/li><li>sequence of statements}<\/li><\/ol><p>Comment la complexit\u00e9 changerait-elle si la deuxi\u00e8me boucle passait \u00e0 N au lieu de M\u00a0?<\/p><p>Une boucle imbriqu\u00e9e suivie d&rsquo;une boucle non imbriqu\u00e9e\u00a0:<\/p><ol start=\"7\"><li>for (i = 0; i &lt; N; i++) {<\/li><li>for (j = 0; j &lt; N; j++) {<\/li><li>sequence of statements<\/li><li>}}<\/li><li>for (k = 0; k &lt; N; k++) {<\/li><li>sequence of statements}<\/li><\/ol><p>Une boucle imbriqu\u00e9e dans laquelle le nombre d&rsquo;ex\u00e9cutions de la boucle interne d\u00e9pend de la valeur de l&rsquo;index de la boucle externe\u00a0:<\/p><ol start=\"13\"><li>for (i = 0; i &lt; N; i++) {<\/li><li>for (j = N; j &gt; i; j\u2013) {<\/li><li>sequence of statements<\/li><li>}}<\/li><\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-55faf1a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"55faf1a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-072baa5\" data-id=\"072baa5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ba6f586 elementor-widget elementor-widget-toggle\" data-id=\"ba6f586\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1951\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1951\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1951\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1951\"><ol><li>La premi\u00e8re boucle est O(N) et la deuxi\u00e8me boucle est O(M). Puisque vous ne savez pas lequel est le plus grand, vous dites que c&rsquo;est O(N+M). Cela peut aussi s&rsquo;\u00e9crire O(max(N,M)). Dans le cas o\u00f9 la seconde boucle va vers N au lieu de M la complexit\u00e9 est O(N). Vous pouvez le voir \u00e0 partir de l&rsquo;une ou l&rsquo;autre des expressions ci-dessus. O(N+M) devient O(2N) et lorsque vous supprimez la constante, c&rsquo;est O(N). O(max(N,M)) devient O(max(N,N)) qui est O(N).<\/li><li>Le premier ensemble de boucles imbriqu\u00e9es est O(N\u00b2) et la deuxi\u00e8me boucle est O(N). C&rsquo;est O(N\u00b2+N) qui est O(N\u00b2).<\/li><li>Ceci est tr\u00e8s similaire \u00e0 notre exemple pr\u00e9c\u00e9dent d&rsquo;une boucle imbriqu\u00e9e o\u00f9 le nombre d&rsquo;it\u00e9rations de la boucle interne d\u00e9pend de la valeur de l&rsquo;index de la boucle externe. La seule diff\u00e9rence est que dans cet exemple, l&rsquo;indice de boucle interne compte \u00e0 rebours de N \u00e0 i+1. C&rsquo;est toujours le cas que la boucle interne s&rsquo;ex\u00e9cute N fois, puis N-1, puis N-2, etc., donc le nombre total de fois que la \u00ab s\u00e9quence d&rsquo;instructions \u00bb la plus interne s&rsquo;ex\u00e9cute est O(N\u00b2).<\/li><\/ol><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1a41627 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1a41627\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-deebfb4\" data-id=\"deebfb4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a3f9fea elementor-widget elementor-widget-heading\" data-id=\"a3f9fea\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Exercice 7<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b8ea67e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b8ea67e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1f6f424\" data-id=\"1f6f424\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4ef3e9d elementor-widget elementor-widget-text-editor\" data-id=\"4ef3e9d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">Donnez une analyse du temps d&rsquo;ex\u00e9cution (notation Big-Oh) pour chacun des 4 fragments de programme suivants. Notez que le temps d&rsquo;ex\u00e9cution correspond ici au nombre de fois que l&rsquo;op\u00e9ration sum++ est ex\u00e9cut\u00e9e. sqrt est la fonction qui renvoie la racine carr\u00e9e d&rsquo;un nombre donn\u00e9.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10598 size-full\" title=\"Corrected Exercises: Time Complexity 3\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image128.png\" alt=\"complexit\u00e9 en temps complexit\u00e9 correction terminaison algorithme exercices corrig\u00e9s\" width=\"229\" height=\"459\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image128.png 229w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image128-150x300.png 150w\" sizes=\"(max-width: 229px) 100vw, 229px\" \/><\/p><ol start=\"2\"><li>S&rsquo;il faut 10\u00a0ms pour ex\u00e9cuter le programme (b) pour n=100, combien de temps faudra-t-il pour ex\u00e9cuter n=400\u00a0?<\/li><li>S&rsquo;il faut 10 ms pour ex\u00e9cuter le programme (a) pour n=100, quelle taille de probl\u00e8me peut \u00eatre r\u00e9solu en 40 ms ?<\/li><\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a786c99 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a786c99\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-168d5a7\" data-id=\"168d5a7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-098901c elementor-widget elementor-widget-toggle\" data-id=\"098901c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-9991\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-9991\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-9991\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-9991\"><p>A est en O(sqrt(n)) c&rsquo;est une suite s\u00e9quentielle de boucles, on a 0(sqrt(n)\/2 + sqrt(n)\/4 + sqrt(n)\/4 +8)<\/p><p>B ne se termine pas, la deuxi\u00e8me boucle n&rsquo;st pas bien \u00e9crite ! En consid\u00e9rant la boucle \u00e9crite convenablement, on aurait eu trois boucles interd\u00e9pendantes born\u00e9es en 0(sqrt(n)), 0(1) et O(1) &#8212; de i \u00e0 i+8; de j \u00e0 j+8 cela fait seulement 8 it\u00e9rations. Ce qui vaut 0(sqrt(n)).<\/p><p>c est en O(n^5). Trois boucles imbriqu\u00e9es de complexit\u00e9s respectives 0(n), 0(n\u00b2), 0(n\u00b2) donc 0(n*n\u00b2*n\u00b2).<\/p><p>d poss\u00e8de une condition d&#8217;embranchement qui n&rsquo;est pas valide car cela ne renvoie pas un bool\u00e9en, l&rsquo;algorithme ne se termine pas donc pas besoin de calculer la complexit\u00e9.<\/p><p>Avec produit crois\u00e9 : sqrt(100)=x et y=10 ms ; sqrt(400)=2x prend 20ms<\/p><p>En 40ms, n=1600.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Algorithms Wiki Home Page Corrected Exercises on Time Complexity The following corrected exercises relate to the analysis of algorithms, in particular correctness, completeness and computation \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15139","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15139","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=15139"}],"version-history":[{"count":18,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15139\/revisions"}],"predecessor-version":[{"id":20225,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15139\/revisions\/20225"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=15139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}