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{aligned} &\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{aligned}

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{aligned} t(n) &= \begin{cases} c & ,\; n \leq 1 \\ a * t(n / b) + g(n) & ,\; n > 1 \end{cases} \end{aligned}

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{aligned} 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{aligned}

Ejemplo:

\begin{aligned} &\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{aligned}

Siguiendo el anterior esquema, obtenemos:

\begin{aligned} 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{aligned}

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{aligned} r(n) &= \begin{cases} 0 & ,\; n \leq 1 \\ 8 * r(n/2) + n^3 & ,\; n > 1 \\ \end{cases} \end{aligned}

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$

Algoritmo de búsqueda binaria

La búsqueda binaria es un algoritmo para encontrar un elemento en una lista ordenada. Dividiendo repetidamente la lista en mitades y comparando el elemento buscado con el elemento del medio.

\begin{aligned} &\\ &\{ 1 \leq lft \leq n+1 \; \land 0 \leq rgt \leq n \; \land \; a \; \textnormal{está ordenado} \} \\ &\fun \; binary\_search\_rec(a: \array[1..n] \; \of \; T , \; x: T, \; lft, rgt: \nat) \; \ret \; i : \nat \\ &\quad \var \; mid: \nat \\ &\quad \if \; lft > rgt \; \to \; i := 0 \\ &\quad \quad lft \leq rgt \to mid := (lft + rgt) \; \textnormal{div} \; 2 \\ &\quad \quad \quad \if \; x < a[mid] \to i := binary\_search\_rec(a, x, lft, mid - 1) \\ &\quad \quad \quad \quad x = a[mid] \to i := mid \\ &\quad \quad \quad \quad x > a[mid] \to i := binary\_search\_rec(a, x, mid + 1, rgt) \\ &\quad \quad \quad \fi \\ &\quad \fi \\ &\bfend \; \fun \\ &\{ i = 0 \implies x \; \textnormal{no está en} \; a[lft,rgt] \; \land \; (i \not=0 \implies x = a[i]) \} \\ &\\ &\\ &\{ n \geq 0 \} \\ &\fun \; binary\_search(a: \array[1..n] \; \of \; T , \; x: T) \; \ret \; i : \nat \\ &\quad i := binary\_search\_rec(a, x, 1, n) \\ &\bfend \; \fun \\ &\{ i = 0 \implies x \; \textnormal{no está en} \; a \; \land \; (i \not=0 \implies x = a[i]) \} \end{aligned}

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{aligned} &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{aligned}

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$ :

\begin{aligned} &g(n) \sqsubset h(n) \iff f(n)g(n) \sqsubset f(n)h(n) \\ &g(n) \simeq h(n) \iff f(n)g(n) \simeq f(n)h(n) \end{aligned}

Sea $\displaystyle{\lim_{n \to \infty}} h(n) = \infty$ :

\begin{aligned} &f(n) \sqsubset g(n) \iff f(h(n)) \sqsubset g(h(n)) \\ &f(n) \simeq g(n) \iff f(h(n)) \simeq g(h(n)) \end{aligned}

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:

\begin{aligned} &\displaystyle{\lim_{n \to \infty}} \frac{f(n)}{g(n)} = 0 \implies f(n) \sqsubset g(n) \\ &\displaystyle{\lim_{n \to \infty}}\frac{f(n)}{g(n)} = \infty \implies g(n) \sqsubset f(n) \\ &\textnormal{caso contrario} \implies f(n) \simeq g(n) \end{aligned}