Teorema del Maestro en la práctica

stoogesort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## División y conquista, recursión\n",
    "\n",
    "**División y conquista** es un método de diseño de algoritmos que consiste en partir un problema en varios subproblemas. Como es un método de _algoritmos_ no tiene ligación a C ni Python ni a ningún lenguaje en particular. Es una **forma de pensar** la solución al problema que tenemos en frente.\n",
    "\n",
    "Por otro lado, la **recursión** es un método de programación de algoritmos, es decir, es una **forma de escribir** la solución, después de haberla pensado. La recursión se utiliza opuesto a la **iteración**. \n",
    "\n",
    "* Un algoritmo **recursivo** es un algoritmo que se invoca a sí mismo en la ejecución. \n",
    "\n",
    "* Un algoritmo **iterativo** es un algoritmo que recorre repeticiones definidas. \n",
    "\n",
    "División y conquista no implica recursión, ni recursión implica división y conquista. Hay algoritmos de D&C que no son recursivos, y hay algoritmos recursivos que no son D&C."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Teorema del maestro\n",
    "\n",
    "El **teorema del maestro** es un teorema que se aplica en algoritmos de D&C recursivos y nos permite calcular su complejidad temporal. Sabiendo las lineas generales del algoritmo (cuántas veces llama recursivamente, cuál es su entrada, y algunas cosas más), nos permite deducir el $\\mathcal O(n)$ de este. Este teorema es muy útil ya que hacer un seguimiento tradicional de este tipo de algoritmos es muy complejo\n",
    "\n",
    "La notación \"O-grande\" es la que marca el **crecimiento** de un algoritmo en su peor caso. Por ejemplo, si una función hace $2n+1$ pasos, su crecimiento depende de $n$, por lo tanto: $T(n) = 2n+1 \\in \\mathcal O(n)$. Mientras que si una función ejecuta $2n^2+1$ pasos, su crecimiento depende de $n^2$, dando $\\mathcal O(n^2)$. El crecimiento siempre esta dado en función de la entrada del algoritmo (es decir, los parámetros de la función). \n",
    "\n",
    "El primer paso para poder aplicar el teorema del maestro es el escribir su complejidad temporal en términos de sus llamados recursivos, la entrada de estos, y su complejidad temporal:\n",
    "\n",
    "\n",
    "$T(n) = $ <span style=\"color:purple\"> $a$ </span>* <span style=\"color:green\">$T \\left( \\frac{n}{b} \\right)$</span> + <span style=\"color:red\">$\\mathcal O( n^c )$</span>\n",
    "\n",
    "<p class=\"equation-label\"> \n",
    "En cada ejecución, el algoritmo se llama <span style=\"color:purple\">$a$ veces a si mismo</span>, con una <span style=\"color:green\">entrada de $\\frac{n}{b}$</span>, y la ejecución tiene una <span style=\"color:red\">complejidad temporal de $\\mathcal O(n^c)$</span>.\n",
    "</p>\n",
    "\n",
    "Teniendo estos parámetros definidos, se deduce la complejidad temporal de la siguiente forma:\n",
    "\n",
    "* $\\text{Si} \\quad a < b^c \\implies \\mathcal O( n^c )$\n",
    "\n",
    "* $\\text{Si} \\quad a = b^c \\implies \\mathcal O( n^c * \\log_{} n )$\n",
    "\n",
    "* $\\text{Si} \\quad a > b^c \\implies \\mathcal O(n^{\\log_b a})$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Búsqueda binaria\n",
    "\n",
    "Este sencillo algoritmo determina (recursivamente) si un elemento se encuentra en un arreglo ordenado.\n",
    "\n",
    "```cpp\n",
    "bool busqbin(int* vec, int ini, int fin, int elem){\n",
    "        if (ini > fin) return false;\n",
    "        int medio = (ini + fin) / 2;\n",
    "        if(vec[medio] == elem) return true;\n",
    "        if(elem < vec[medio])\n",
    "            return busqbin(vec, ini, medio - 1,elem);\n",
    "        else if (elem > vec[medio])\n",
    "            return busqbin(vec,medio + 1,fin,elem);\n",
    "}\n",
    "```\n",
    "\n",
    "Siendo los componentes del Teorema del Maestro:\n",
    "\n",
    "* $a$: La cantidad de llamados recursivos en un llamado. \n",
    "\n",
    "* $\\frac{n}{b}$: La entrada de cada llamado recursivo. \n",
    "\n",
    "* $\\mathcal O(n^c)$: La complejidad del llamado entero. \n",
    "\n",
    "Como en este caso la función se llama solamente una vez a sí misma (entra a un `if` o al otro, pero nunca ambos), se tiene solo un llamado recursivo por ejecución. Por lo tanto, $a = 1$.\n",
    "\n",
    "El llamado recursivo es sobre la mitad de la entrada, es decir, sobre $\\frac{n}{2}$, entonces, $b = 2$.\n",
    "\n",
    "En este ejemplo, solo tengo condicionales y una división. Estos pasos son constantes, es decir $\\mathcal O(1)$. Por lo tanto, $\\mathcal O(n^c) = \\mathcal O(1)$ y recordando que todo número elevado a la 0 da 1, queda $c = 0$.\n",
    "\n",
    "Finalmente, como $a=1$, $b=2$ y $c=0$ y viendo que $b^c = 1 = a$, se cae en el segundo caso del Teorema del Maestro\n",
    "\n",
    "$$T(n) = 1 * T ( \\frac n 2 ) + \\mathcal O (n^0) \\in \\mathcal O (n^0 \\log_2 n) = \\mathcal O (\\log n)$$\n",
    "\n",
    "Llamo 1 vez recursiva a una media parte de mi problema, y las operaciones constantes son O(1).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## StoogeSort\n",
    "\n",
    "> El StoogeSort es un algoritmo de ordenamiento basado en Los Tres Chiflados que funciona de la siguiente forma: \n",
    "* Si el primer elemento es más grande que el ultimo, los intercambia.\n",
    "* Si la cantidad de elementos del vector es mayor o igual a $3$:\n",
    "  1. Llama a StoogeSort recursivamente con los primero dos tercios del vector (desde $0$ hasta $\\frac{2}{3}* cantidad$)\n",
    "  2. Llama a StoogeSort recursivamente con los segundos dos tercios (desde $\\frac{1}{3}* cantidad$, hasta $cantidad$)\n",
    "  3. Vuelve a llamar recursivamente a StoogeSort con los primeros dos tercios del vector.\n",
    "\n",
    "Entrando al stoogesort, lo que queremos es tener $a$, $b$ y $c$ para poder escribir correctamente $T(n)$ y de ahí deducir $\\mathcal O(n)$.\n",
    "\n",
    "* Lo primero que vemos es que llama 3 veces a la función, sí o sí, en cada ejecución. Entonces, $a=3$ (número de subejecuciones por cada ejecución).\n",
    "\n",
    "* Lo segundo es que el problema está partido en partes de $\\frac{2}{3}$ de n, porque en la primera llamada utiliza los primeros dos tercios, en la segunda, a los últimos dos tercios, y en la tercera a los primeros dos tercios nuevamente. Por lo tanto, **siempre llama a $\\frac{2}{3}$ de n recursivamente**. $\\frac{n}{b} = \\frac{2}{3} \\implies b = \\frac{3}{2}$\n",
    "\n",
    "* Por último, como nos dice el enunciado, las funciones son en tiempo constante, $\\mathcal O(n^c) = \\mathcal O(1)$ y por ende $c = 0$.\n",
    "\n",
    "Este es el caso 3 del teorema del maestro, donde $b^c$ es menor que $a$.\n",
    "\n",
    "$$T(n) = 3 * T ( \\frac {n }{3/2} ) + \\mathcal O (n^0) \\in \\mathcal O (n^{\\log_{3/2} 3})$$\n",
    "\n",
    "En cada subejecución, llamo 3 veces a 2/3 de mi problema, y las operaciones son en tiempo constante.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bibliografía\n",
    "\n",
    "* Thomas Cormen, \"Introduction to Algorithms\": *4. Divide-and-Conquer*.\n",
    "\n",
    "* Rosa Guerequeta y Antonio Vallecillo, \"Técnicas de Diseño de Algoritmos\": *3. Divide y vencerás.* <a class=\"fa fa-link\" href=\"http://www.lcc.uma.es/%7Eav/Libro\"></a>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Más\n",
    "\n",
    "* [Como visualizar un ordenamiento logarítmico](https://www.interviewcake.com/article/java/logarithms)\n",
    "\n",
    "* [Demostración del teorema del maestro](https://www.coursera.org/lecture/algorithmic-toolbox/proof-of-the-master-theorem-7KR1r)\n",
    "\n",
    "* [Se puede ordenar en menos de O(n log n)?](https://www.coursera.org/lecture/algorithms-divide-conquer/omega-n-log-n-lower-bound-for-comparison-based-sorting-advanced-optional-P2uwC)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}