{"id":4047,"date":"2016-06-28T15:19:49","date_gmt":"2016-06-28T14:19:49","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4047"},"modified":"2022-12-03T22:59:07","modified_gmt":"2022-12-03T21:59:07","slug":"complexite-en-temps","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmico\/complejidad-en-el-tiempo\/","title":{"rendered":"Complejidad del tiempo"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"4047\" class=\"elementor elementor-4047\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d2eef51 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d2eef51\" 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-5621cdc\" data-id=\"5621cdc\" 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-82ee80b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"82ee80b\" 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-b3a298f\" data-id=\"b3a298f\" 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-9995bf4 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9995bf4\" 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-eb7ba91\" data-id=\"eb7ba91\" 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-4362b25 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"4362b25\" 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:\/\/fr.wikipedia.org\/wiki\/Complexit%C3%A9_en_temps\" 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-5b3ab7d8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5b3ab7d8\" 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-69de6415\" data-id=\"69de6415\" 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-79403fc7 elementor-widget elementor-widget-text-editor\" data-id=\"79403fc7\" 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<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=\"Alternar tabla de contenidos\"><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\/es\/algoritmico\/complejidad-en-el-tiempo\/#Complexite-en-temps\" >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\/es\/algoritmico\/complejidad-en-el-tiempo\/#Operation-elementaire\" >Op\u00e9ration \u00e9l\u00e9mentaire<\/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\/es\/algoritmico\/complejidad-en-el-tiempo\/#Notation-de-Landau\" >Notation de Landau<\/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\/es\/algoritmico\/complejidad-en-el-tiempo\/#Exemples\" >Exemples<\/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\/es\/algoritmico\/complejidad-en-el-tiempo\/#Pire-meilleur-et-moyenne\" >Pire, meilleur et moyenne<\/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\/es\/algoritmico\/complejidad-en-el-tiempo\/#Exemples-2\" >Exemples<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Complexite-en-temps\"><\/span>Complexit\u00e9 en temps<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>La complexit\u00e9 en temps repr\u00e9sente de fa\u00e7on asymptotique le temps que met un <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algorithme<\/a> \u00e0 trouver une solution.<\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Soit un probl\u00e8me P et M une m\u00e9thode pour r\u00e9soudre ce probl\u00e8me. L&rsquo;algorithme est une description avec des structures de contr\u00f4le et de donn\u00e9es permettant d&rsquo;\u00e9crire la m\u00e9thode M dans un langage reconnaissable par tout individu ou machine.<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Pour rappel, les structures de contr\u00f4le sont : une s\u00e9quence, un embranchement (ou s\u00e9lection), une boucle (ou it\u00e9ration). Les structures de donn\u00e9es sont : des constantes, des variables, des tableaux (ou espace de stockage ordonn\u00e9), des structures r\u00e9cursives (listes, graphes etc).<\/div>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Operation-elementaire\"><\/span>Op\u00e9ration \u00e9l\u00e9mentaire<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>La complexit\u00e9 consiste \u00e0 \u00e9valuer l&rsquo;efficacit\u00e9 de la m\u00e9thode M et de comparer cette derni\u00e8re avec une autre m\u00e9thode M&rsquo;. Cette comparaison est ind\u00e9pendante de l&rsquo;environnement (machine, syst\u00e8me, compilateur, langage, etc). L&rsquo;efficacit\u00e9 d\u00e9pend du nombre d&rsquo;op\u00e9rations \u00e9l\u00e9mentaires. Ces derni\u00e8res d\u00e9pendent de la taille des donn\u00e9es et de la nature des donn\u00e9es.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Notons n la taille des donn\u00e9es et T(n) le nombre d&rsquo;op\u00e9rations \u00e9l\u00e9mentaires. L&rsquo;\u00e9valuation de efficacit\u00e9 se fera dans le meilleur des cas, le pire des cas et le cas moyen.<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Dans le cas d&rsquo;une structure de type s\u00e9quence, l&rsquo;\u00e9valuation est \u00e9gale \u00e0 la somme des co\u00fbts. Par exemple, si l&rsquo;algorithme poss\u00e8de un traitement T1(n) suivit de T2(n), alors T(n)=T1(n)+T2(n).<\/p>\n<p style=\"text-align: justify;\">Dans le cas d&rsquo;un embranchement, l&rsquo;\u00e9valuation est \u00e9gale au maximum des embranchements. Par exemple, l&rsquo;algorithme ex\u00e9cute T1(n) sinon T2(n), alors T(n)=max(T1(n), T2(n)).<\/p>\n<p style=\"text-align: justify;\">Dans le cas d&rsquo;une boucle, l&rsquo;\u00e9valuation est \u00e9gale \u00e0 la somme des co\u00fbts des passages successifs. Par exemple, si l&rsquo;algorithme est un \u00ab\u00a0tant que faire Ti(n) avec la complexit\u00e9 de Ti(n) d\u00e9pendant du num\u00e9ro i de l&rsquo;it\u00e9ration. Alors la complexit\u00e9 est T(n) = somme(i=1 \u00e0 n) Ti(n).<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Pour une version r\u00e9cursive, je vous invite \u00e0 aller sur la page correspondante. Posons C(n) le traitement effectu\u00e9 dans une fonction en divide&amp;conquer. Alors la complexit\u00e9 est T(n)=2*T(n\/2)+C(n) = n log(n) si C(n)=n.<\/div>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Notation-de-Landau\"><\/span>Notation de Landau<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>la notation de Landau caract\u00e9rise le comportement asymptotique d&rsquo;une fonction, c&rsquo;est \u00e0 dire le comportement de f(n) quand n tend vers l&rsquo;infini.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">On dit que f(n) est un grand O de g(n) si <img decoding=\"async\" class=\"mwe-math-fallback-image-inline\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/f0f682cb36f62f6e9ffac5d9f2174a7f34c81b6b\" alt=\"\\exists k&gt;0, \\exists n_0 \\; \\forall n&gt;n_0 \\; |f(n)| \\leq |g(n)|\\cdot k \" title=\"\">.<\/div>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-4079 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity1.png\" alt=\"complexit\u00e9 en temps big o notation de landau algorithme\" width=\"797\" height=\"349\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity1.png 797w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity1-300x131.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity1-768x336.png 768w\" sizes=\"(max-width: 797px) 100vw, 797px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-6271 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/complexity.png\" alt=\"complexit\u00e9 en temps big o notation de landau algorithme\" width=\"616\" height=\"400\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/complexity.png 616w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/complexity-300x195.png 300w\" sizes=\"(max-width: 616px) 100vw, 616px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemples\"><\/span>Exemples<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-4085 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity2.png\" alt=\"complexit\u00e9 en temps big o notation de landau algorithme\" width=\"797\" height=\"368\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity2.png 797w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity2-300x139.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity2-768x355.png 768w\" sizes=\"(max-width: 797px) 100vw, 797px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4088 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity3.png\" alt=\"complexit\u00e9 en temps big o notation de landau algorithme\" width=\"821\" height=\"361\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity3.png 821w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity3-300x132.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity3-768x338.png 768w\" sizes=\"(max-width: 821px) 100vw, 821px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4091 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity4.png\" alt=\"complexit\u00e9 en temps big o notation de landau algorithme\" width=\"966\" height=\"482\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity4.png 966w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity4-300x150.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity4-768x383.png 768w\" sizes=\"(max-width: 966px) 100vw, 966px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Pire-meilleur-et-moyenne\"><\/span>Pire, meilleur et moyenne<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Nous pouvons calculer pour la plupart des algorithmes une complexit\u00e9 dans le pire des cas (le plus grand nombre d&rsquo;op\u00e9rations \u00e9l\u00e9mentaires), le meilleur et en moyenne. La moyenne est une somme pond\u00e9r\u00e9e par la probabilit\u00e9 de pr\u00e9sence des complexit\u00e9s possibles. Le plus souvent, on utilise la complexit\u00e9 au pire car on souhaite connaitre une borne sup\u00e9rieur de temps d\u2019ex\u00e9cution.<\/div>\n<p><\/p>\n<p><\/p>\n<p>Consid\u00e9rons un algorithme de recherche d&rsquo;un \u00e9l\u00e9ment dans un tableau en forme it\u00e9rative. L&rsquo;algorithme s&rsquo;arr\u00eate lorsque la valeur a \u00e9t\u00e9 trouv\u00e9e. L&rsquo;algorithme se d\u00e9compose ainsi : affectation de 0 \u00e0 i, tant que i n&rsquo;a pas parcouru le tableau on incr\u00e9mente i, si tab[i]=valeur alors on retourne vrai, sinon \u00e0 la fin du tableau on retourne faux. Notons C la complexit\u00e9 du corps de la boucle.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Au pire des cas, l&rsquo;algorithme parcours tout le tableau, c&rsquo;est \u00e0 dire que T(n)=1+n*C=O(n). Au mieux, l&rsquo;\u00e9l\u00e9ment est au d\u00e9but du tableau, donc T(n)=1+C=O(1). Nous consid\u00e9rons qu&rsquo;en moyenne, il y a 50% de chance que l&rsquo;\u00e9l\u00e9ment ne soit pas dans le tableau, et 50% qu&rsquo;il soit \u00e0 la moiti\u00e9 du tableau (ceci est bien entendu absurde, mais nous ne ferons pas toutes les possibilit\u00e9s). Dans ce cas, la complexit\u00e9 en moyenne est de T(n)=0.5*(1+n*C)+0.5*(1+n*C\/2)=a*n+b avec a et b des constantes = O(n). Nous remarquons que le comportement asymptotique en moyenne est le m\u00eame qu&rsquo;au pire cas.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemples-2\"><\/span>Exemples<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Supposons que chacune des expressions ci-dessous donne le temps de traitement T(n) pass\u00e9 par un algorithme pour r\u00e9soudre un probl\u00e8me de taille n. S\u00e9lectionnez le terme dominant (s) ayant la plus forte augmentation de n et sp\u00e9cifiez la complexit\u00e9 Big-Oh la plus basse de chaque algorithme.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td><strong>Expression<\/strong><\/td>\n<td><strong>Dominant<\/strong><\/td>\n<td><strong>O(.)<\/strong><\/td>\n<\/tr>\n<tr>\n<td>5 + 0.001n<sup>3<\/sup>+ 0.025n<\/td>\n<td>0.001n<sup>3<\/sup><\/td>\n<td>O(n<sup>3<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>500n + 100n<sup>1.5<\/sup> + 50n log<sub>10<\/sub> n<\/td>\n<td>100n<sup>1.5<\/sup><\/td>\n<td>O(n<sup>1.5<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>0.3n + 5n<sup>1.5<\/sup> + 2.5 n<sup>1.75<\/sup><\/td>\n<td>2.5 n<sup>1.75<\/sup><\/td>\n<td>O(n<sup>1.75<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>n<sup>2<\/sup> log<sub>2<\/sub> n + n(log<sub>2<\/sub> n)<sup>2<\/sup><\/td>\n<td>n<sup>2<\/sup> log<sub>2<\/sub> n<\/td>\n<td>O(n<sup>2<\/sup> log n)<\/td>\n<\/tr>\n<tr>\n<td>n log<sub>3<\/sub> n + n log<sub>2<\/sub> n<\/td>\n<td>n log<sub>3<\/sub> n, n log<sub>2<\/sub> n<\/td>\n<td>O(n log n)<\/td>\n<\/tr>\n<tr>\n<td>\u00a0 3 log<sub>8<\/sub> n + log<sub>2<\/sub> log<sub>2<\/sub> log<sub>2<\/sub> n<\/td>\n<td>3 log<sub>8<\/sub> n<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<tr>\n<td>0. 100n + 0.01n<sup>2<\/sup><\/td>\n<td>0.01n<sup>2<\/sup><\/td>\n<td>O(n<sup>2<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>0.01n + 100n<sup>2<\/sup><\/td>\n<td>100n<sup>2<\/sup><\/td>\n<td>O(n<sup>2<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>2n + n<sup>0.5<\/sup> + 0.5n<sup>1.25<\/sup><\/td>\n<td>0.5n<sup>1.25<\/sup><\/td>\n<td>O(n<sup>1.25<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>0.01n log<sub>2<\/sub> n + n(log<sub>2<\/sub> n)<sup>2<\/sup><\/td>\n<td>n(log<sub>2<\/sub> n)<sup>2<\/sup><\/td>\n<td>O(n(log n)<sup>2<\/sup>)<\/td>\n<\/tr>\n<tr>\n<td>100n log<sub>3<\/sub> n + n<sup>3<\/sup> + 100n<\/td>\n<td>n<sup>3<\/sup><\/td>\n<td>O(n<sup>3<\/sup>)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p>Les instructions ci-dessous montrent quelques caract\u00e9ristiques de la notation \u00ab\u00a0Big-Oh\u00a0\u00bb pour les fonctions f \u2261 f (n) et g \u2261 g (n). D\u00e9terminez si chaque instruction est TRUE ou FALSE et corrigez la formule dans ce dernier cas.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td><strong>Fonction<\/strong><\/td>\n<td><strong>TRUE ou FALSE ?<\/strong><\/td>\n<td><strong>Apr\u00e8s correction<\/strong><\/td>\n<\/tr>\n<tr>\n<td>\u00a0O(f + g) = O(f) + O(g)<\/td>\n<td>FALSE<\/td>\n<td>O(f + g) = max {O(f), O(g)}<\/td>\n<\/tr>\n<tr>\n<td>O(f \u00b7 g) = O(f) \u00b7 O(g)<\/td>\n<td>TRUE<\/td>\n<td>\u00a0<\/td>\n<\/tr>\n<tr>\n<td>\u00a0if g = O(f) and h = O(f) then g = O(h)<\/td>\n<td>FALSE<\/td>\n<td>if g = O(f) and f = O(h) then g = O(h)<\/td>\n<\/tr>\n<tr>\n<td>5n + 8n 2 + 100n 3 = O(n 4 )<\/td>\n<td>TRUE<\/td>\n<td>\u00a0<\/td>\n<\/tr>\n<tr>\n<td>5n+8n 2 +100n 3 = O(n 2 log n)<\/td>\n<td>FALSE<\/td>\n<td>O(n<sup>3<\/sup> )<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/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<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Algorithms Wiki Home Page Complejidad del tiempo La complejidad del tiempo es una representaci\u00f3n asint\u00f3tica del tiempo que tarda un algoritmo en encontrar una soluci\u00f3n. \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-4047","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4047","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=4047"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4047\/revisions"}],"predecessor-version":[{"id":17937,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4047\/revisions\/17937"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=4047"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}