{"id":1732,"date":"2016-02-08T13:07:14","date_gmt":"2016-02-08T12:07:14","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1732"},"modified":"2022-12-03T22:58:52","modified_gmt":"2022-12-03T21:58:52","slug":"diviser-pour-regner","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmico\/divide-y-venceras\/","title":{"rendered":"Divide y vencer\u00e1s"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1732\" class=\"elementor elementor-1732\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fd226f2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fd226f2\" 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-2975a7d\" data-id=\"2975a7d\" 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-5cea53d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5cea53d\" 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\/es\/algoritmico\/\">\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\">Algor\u00edtmico<\/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-48b46df\" data-id=\"48b46df\" 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-0ddbda5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0ddbda5\" 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\/es\/\">\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\">Pagina de inicio<\/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-84acb83\" data-id=\"84acb83\" 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-a54ac62 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a54ac62\" 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\/Diviser_pour_r%C3%A9gner_(informatique)\" 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-1d3efab0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1d3efab0\" 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-2894f838\" data-id=\"2894f838\" 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-3e1e785d elementor-widget elementor-widget-text-editor\" data-id=\"3e1e785d\" 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_83 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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/divide-y-venceras\/#Diviser-pour-regner\" >Divide y vencer\u00e1s<\/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\/divide-y-venceras\/#Principe\" >Principio<\/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\/divide-y-venceras\/#Exemple\" >Ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Diviser-pour-regner\"><\/span>Divide y vencer\u00e1s<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\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;\">El m\u00e9todo de divide y vencer\u00e1s es un m\u00e9todo que permite, en ocasiones, encontrar soluciones efectivas a problemas algor\u00edtmicos. La idea es cortar el problema inicial, de tama\u00f1o. <strong>no<\/strong>, en varios subproblemas m\u00e1s peque\u00f1os, luego recombine las soluciones parciales hasta obtener la soluci\u00f3n final.<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Principe\"><\/span>Principio<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/progdyn.png\" alt=\"Divide y vencer\u00e1s\" width=\"757\" height=\"246\" title=\"\"><\/figure>\n\n<p class=\"wp-block-paragraph\">A diferencia del <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/\">programaci\u00f3n din\u00e1mica<\/a>, los resultados de los subproblemas solo son \u00fatiles para el resultado del problema principal.<\/p>\n\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>El algoritmo divide y vencer\u00e1s se puede dividir en tres pasos:<\/p>\n<ol style=\"text-align: justify;\">\n<li>Dividir: el problema se divide en subproblemas de tama\u00f1o. <strong>b \/ n<\/strong>. Estos subproblemas son de la misma naturaleza que sus padres. Por tanto, estamos en presencia de <strong>Para<\/strong> subproblemas id\u00e9nticos. Cuando <strong>b = 2<\/strong>, estamos hablando de dicotom\u00eda.<\/li>\n<li>Regla: los subproblemas se resuelven de forma recursiva.<\/li>\n<li>Recombina: las soluciones de los subproblemas se recombinan para reconstruir la soluci\u00f3n al problema inicial.<\/li>\n<\/ol>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p class=\"wp-block-paragraph\">Para comprender mejor la construcci\u00f3n del algoritmo, tomaremos el ejemplo de exponenciaci\u00f3n r\u00e1pida. El principio de este <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> es calcular x<sup>no<\/sup>.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Una forma ingenua ser\u00eda hacer un bucle donde a*= x con a = 1 inicialmente. los <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/complejidad-en-el-tiempo\/\">complejidad<\/a> del m\u00e9todo ingenuo es por lo tanto lineal 0(n).<\/div>\n\n<p class=\"wp-block-paragraph\">Para usar el m\u00e9todo de dividir y conquistar, necesitamos encontrar un programa matem\u00e1tico que nos permita reescribir nuestro problema en subproblemas equivalentes. Dado que este es un m\u00e9todo recursivo, no olvide incluir un estado final. Por tanto, estamos en presencia del siguiente programa matem\u00e1tico:<\/p>\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-1754 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/exprapide.png\" alt=\"Divide y conquista la exponenciaci\u00f3n r\u00e1pida\" width=\"492\" height=\"99\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/exprapide.png 492w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/exprapide-300x60.png 300w\" sizes=\"(max-width: 492px) 100vw, 492px\" \/><\/figure>\n\n<p class=\"wp-block-paragraph\">El algoritmo es como sigue:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>doble potencia (doble x, int n) {\n   <strong>tejo<\/strong> (n == 0) devuelve 1;\n   <strong>dem\u00e1s<\/strong> {\n      <strong>tejo<\/strong> (n%2 == 0) retorno de potencia (x * x, n \/ 2);\n      <strong>dem\u00e1s<\/strong> devuelve x * potencia (x * x, (n-1) \/ 2);\n      <strong>terminara si<\/strong>\n   <strong>terminara si<\/strong>\n}<\/pre>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Su complejidad es 0 (log n) - tama\u00f1o del \u00e1rbol binario completo en <strong>no<\/strong> tapas.<\/p>\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<\/div>","protected":false},"excerpt":{"rendered":"<p>P\u00e1gina de inicio de Algorithmics Wiki Divide y vencer\u00e1s El m\u00e9todo de divide y vencer\u00e1s es un m\u00e9todo que a veces permite encontrar soluciones efectivas a \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-1732","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1732","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=1732"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1732\/revisions"}],"predecessor-version":[{"id":18343,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1732\/revisions\/18343"}],"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=1732"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}