{"id":5964,"date":"2018-03-07T15:21:17","date_gmt":"2018-03-07T14:21:17","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5964"},"modified":"2018-03-11T09:22:49","modified_gmt":"2018-03-11T08:22:49","slug":"i1m2017-analisis-de-la-complejidad-de-los-algoritmos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-analisis-de-la-complejidad-de-los-algoritmos\/","title":{"rendered":"I1M2017: An\u00e1lisis de la complejidad de los algoritmos"},"content":{"rendered":"<p>En la primera parte de la clase hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha explicado el tema de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\/temas\/tema-28.html\">an\u00e1lisis de la complejidad de los algoritmos<\/a>.<\/p>\n<p>Se empez\u00f3 explicando la notaci\u00f3n de Landau y los \u00f3rdenes de complejidad. A continuaci\u00f3n se presentaron varios ejemplos de definiciones de distintos \u00f3rdenes. En cada ejemplo, se especific\u00f3 el problema, se defini\u00f3 la funci\u00f3n, se hizo una tabla sobre la variaci\u00f3n de los tiempos y su correspondiente gr\u00e1fica, se extrajeron las ecuaciones en recurrencia, se resolvieron con Wolfram Alpha y se demostr\u00f3 por inducci\u00f3n el orden de la definici\u00f3n.<\/p>\n<p>Como resumen, en la siguiente tabla se muestra los ejemplos presentados<\/p>\n<pre><code>| Ejemplo     | Ecuaciones         | Orden      |\n|-------------|--------------------|------------|\n| suma        | T(1)   = k         | O(n)       |\n|             | T(n+1) = T(n)+k'   |            |\n|-------------|--------------------|------------|\n| suma2       | T(1) = k           | O(1)       |\n|-------------|--------------------|------------|\n| sumaDeSumas | T(1)   = k         | O(n\u00b2)      |\n|             | T(n+1) = T(n)+n    |            |\n|-------------|--------------------|------------|\n| potencia    | T(1)   = k         | O(log(n))  |\n|             | T(n)   = T(n\/2)+k' |            |\n|-------------|--------------------|------------|\n| raiz        | T(0)   = k         | O(2\u207f)      |\n|             | T(n+1) = 2T(n)+k'  |            |\n|-------------|--------------------|------------|\n| ordenaci\u00f3n  | T(1)   = k         | O(nlog(n)) |\n| por mezcla  | T(n)   = 2T(n\/2)+n |            |\n<\/code><\/pre>\n<p>Los apuntes correspondientes a la clase son<br \/>\n\n<!-- iframe plugin v.5.0 wordpress.org\/plugins\/iframe\/ -->\n<iframe loading=\"lazy\" src=\"https:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\/temas\/tema-28.html\" width=\"100%\" frameborder=\"1\" height=\"500\" scrolling=\"yes\" class=\"iframe-class\"><\/iframe>\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha explicado el tema de an\u00e1lisis de la complejidad de los algoritmos. Se empez\u00f3 explicando la notaci\u00f3n de Landau y los \u00f3rdenes de complejidad. A continuaci\u00f3n se presentaron varios ejemplos de definiciones de distintos \u00f3rdenes. En cada ejemplo,&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[265],"tags":[244,270,316],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5964"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5964"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5964\/revisions"}],"predecessor-version":[{"id":5965,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5964\/revisions\/5965"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5964"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5964"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5964"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}