Recurrencias y Jerarquía de Funciones
Algoritmo divide y vencerás
Divide y vencerás es un paradigma de diseño de algoritmos que consiste en resolver un problema dividiéndolo en subproblemas más pequeños, resolviendo los subproblemas y combinando sus soluciones para resolver el problema original.
El esquema de este algoritmo es el siguiente:
\[\begin{align} &\fun \; DyV(x) \; \ret \; y \\ &\quad \if \; x \; \textnormal{suficientemente simple} \; \then \; y:=ad\_hoc(x) \\ &\quad \else \; \textnormal{descomponer} \; x \; \textnormal{en} \; x_1,x_2,\ldots,x_a \\ &\quad \quad \for \; i:=1 \; \too \; a \; \do \; y_i:=DyV(x_i) \; \od \\ &\quad \quad \{- \;\; \textnormal{combinar} \; y_1,y_2,\ldots,y_a \; \textnormal{para obtener la solución} \; y \; \textnormal{de} \; x \;\; -\} \\ &\quad \fi \\ &\bfend \; \fun \end{align} \]Los \(x_i\) son subproblemas de \(x\), podemos considerarlos fracciones de \(x\):
\[|x_i| = \frac{x}{b} \]Si tomamos por ejemplo el algoritmo Merge Sort:
- ”\(x\) simple” \(=\) fragmento de arreglo de tamaño \(0 \lor 1\)
- “descomponer” \(=\) dividir en dos mitades \((b=2)\)
- \(a = 2\)
- “combinar” \(=\) intercalar
Recurrencias divide y vencerás
Para calcular el costo computacional de \(DyV\) definimos una función recursiva \(r(n)\) de la siguiente forma:
\[\begin{align} t(n) &= \begin{cases} c & ,\; n \leq 1 \\ a * t(n / b) + g(n) & ,\; n > 1 \end{cases} \end{align} \]Donde \(c\) es una constante que representa el costo computacional de la función \(ad\_hoc\) y \(g(n)\) es el costo computacional de procesos de descomposición/combinación.
Podemos determinar el orden de \(t(n)\) de la siguiente forma:
\[\begin{align} t(n) &= \begin{cases} n^{\log_b a} & ,\; a > b^k \\ n^k \; \log \; n & ,\; a = b^k \\ n^k & ,\; a < b^k \end{cases} \end{align} \]Ejemplo:
\[\begin{align} &\proc \; f_1 (\bfin \; n : \nat) \\ &\quad \if \; n \leq 1 \; \then \; \skip \\ &\quad \else \\ &\quad \quad \for \; i:=1 \; \too \; 8 \; \do \; f_1(n \; \textnormal{div} \; 2) \; \od \\ &\quad \quad \for \; i:=1 \; \too \; n^3 \; \do \; t:=1 \; \od \\ &\quad \fi \\ &\bfend \; \proc \end{align} \]Siguiendo el anterior esquema, obtenemos:
\[\begin{align} r(n) &= \begin{cases} 0 & ,\; n \leq 1 \\ \displaystyle{\sum^8_{i=1} \; r(n/2)} + \displaystyle{\sum^{n^3}_{i=1} \; 1} & ,\; n > 1 \\ \end{cases} \end{align} \]El primer término de la sucesión corresponde a la cantidad de veces que se llama a la función \(f_1\) y el segundo término corresponde a la cantidad de veces que se ejecuta la instrucción \(t:=1\).
\[\begin{align} r(n) &= \begin{cases} 0 & ,\; n \leq 1 \\ 8 * r(n/2) + n^3 & ,\; n > 1 \\ \end{cases} \end{align} \]Planteada la recurrencia tenemos que:
- \(a = 8\)
- \(b = 2\)
- \(g(n) = n^3 \implies k = 3\)
- \(8 > 2^3 \implies\) el orden de \(r(n)\) es \(n^3 \; \log \; n\)
Jerarquía de funciones
Es posible ordenar las funciones de acuerdo a su crecimiento. Se denota \(f(n) \sqsubset g(n)\) si \(g\) crece más rápido que \(f\), y \(f(n) \simeq g(n)\) si crecen al mismo ritmo.
Podemos establecer la siguiente jerarquía de funciones:
\[\begin{align} &1 \sqsubset \log(\log(\log(n))) \sqsubset \log(\log \; n) \sqsubset \log(n) \sqsubset n^{0.001} \sqsubset n \\ &\sqsubset n \log \; n \sqsubset n^{1.001} \sqsubset n^{100} \sqsubset 1.01^{n} \sqsubset n^{100} * 1.01^n \\ &\sqsubset 1.02^n \sqsubset 100^n \sqsubset 10000^n \sqsubset (n-1)! \sqsubset n! \sqsubset n^n \end{align} \]Propiedades:
- No afectan las constantes multiplicativas
- Sea \(a, b > 1 \implies \log_a \; n \simeq \log_b \; n\)
- Sea \(f(n) > 0\) para casi todo \(n \in \NN\):
- Sea \(\displaystyle{\lim_{n \to \infty}} h(n) = \infty\):
- Sean \(\displaystyle{\lim_{n \to +\infty}} f(n) = \infty = \displaystyle{\lim_{n \to +\infty}} g(n)\) y \(\displaystyle{\lim_{n \to +\infty}} \frac{f(n)}{g(n)}\) existente: