AALIE

Algoritmos Iterativos — Patrones y Costos

Patrones de ciclos, búsqueda secuencial, crecimiento de funciones y comparación formal mediante límites.

3.1 Patrones típicos de ciclos

Patrones típicos de ciclos iterativos

Patron	Estructura	Ejecuciones del cuerpo	Costo típico
for simple	`for i <- 1 to n`	$n$	$O (n)$
for anidado (límite fijo)	`for i... for j <- 1 to n`	$n^{2}$	$O (n^{2})$
for anidado (límite variable)	`for i... for j <- 1 to i`	$\frac{n ( n + 1 )}{2}$	$O (n^{2})$
while con duplicación	`while j<=n: j<-j*2`	$lo g_{2} (n)$	$O (lo g n)$
for + while interno	`for i... while j<=n: j*=2`	$n \cdot lo g_{2} (n)$	$O (n lo g n)$

3.2 Busqueda Secuencial — Análisis por casos

BusquedaSecuencial

int BusquedaSecuencial (E int A[n], E int x) {
  i <- 1                             # C1 * 1
  while (A[i]<>x) and (i<=n)         # C2 * (n+1) en peor caso
    i <- i + 1                       # C3 * n
  endwhile
  if (i <= n) then                   # C4 * 1
    return i
  else
    return -1                        # C5 * 1
}

Precondiciones

$A [i] \in Z$ , $1 \leq i \leq n$ . Si $x$ no está en el arreglo, retorna $- 1$ .

Análisis por casos de búsqueda secuencial

Caso	Distribucion de entrada	Función de Eficiencia
Mejor caso	$x$ está en $A [1]$ (primera posición)	$T_{b es t} (n) = constante$
Peor caso	$x$ no está en el arreglo	$T_{w ors t} (n) = an + b$ (lineal)
Caso promedio	$x$ puede estar en cuálquier posición con igual probabilidad	$T_{a vg} (n) = \frac{n + 1}{2}$ (lineal)

Nota

¿Es tan malo como que $x$ esté en la última posición? No. Si $x$ no está en el arreglo, el algoritmo llega al final y hace una verificación más (la que causa la salida). Por eso el peor caso es que $x$ no esté.

3.3 Tabla de Crecimiento de Funciones Comunes

Esta tabla es fundamental para comparar funciones rápidamente. Cuanto más arriba en la tabla, más lenta crece la función (mejor). Cuanto más abajo, más rápido crece (peor).

Tabla de crecimiento de funciones comunes

Orden	Nombre	n=10	n=100	n=1000	Comportamiento
$O (1)$	Constante	1	1	1	Ideal. No depende de n.
$O (lo g n)$	Logaritmica	3.32	6.64	9.97	Excelente. Crece muy lento.
$O (n)$	Lineal	10	100	1, 000	Bueno. Crece proporcional.
$O (n lo g n)$	Linealitmica	33	664	9, 966	Aceptable (ej: Merge Sort).
$O (n^{2})$	Cuadratica	100	10, 000	1, 000, 000	Lento para n grande.
$O (n^{3})$	Cubica	1, 000	1, 000, 000	$1 0^{9}$	Muy lento.
$O (2^{n})$	Exponencial	1, 024	$1 0^{30}$	$≫ 1 0^{300}$	Inmanejable para n grande.
$O (n!)$	Factorial	3, 628, 800	$≫ 1 0^{157}$ inmenso	inmenso	Practicamente imposible.

Orden de crecimiento (de menor a mayor)

1 < lo g (n) < n < n lo g (n) < n^{2} < n^{3} < \dots < 2^{n} < 3^{n} < n!

Nota

En logaritmos, si no aparece la base, se asume base 2 (convención del curso).

3.4 Como comparar funciones correctamente

La manera correcta de comparar funciones no es graficando ni tabulando. Se usan desigualdades y límites.

Método de los límites

Para comparar $f (n)$ y $g (n)$ , calculamos:

n \to \infty lim \frac{f ( n )}{g ( n )} = L

Interpretación del límite para comparar funciones

Resultado L	Significado	Relacion
$L = 0$	$g (n)$ crece más rápido que $f (n)$	$f (n)$ crece más lento que $g (n)$
L = constante $(c > 0)$	$f (n)$ y $g (n)$ crecen a la misma velocidad	Son del mismo orden
$L = \infty$	$f (n)$ crece más rápido que $g (n)$	$f (n)$ domina a $g (n)$

Ejemplo

Comparar $f (n) = 3 n^{2} + 5 n$ y $g (n) = n^{2}$ .

Cálculo del límite

Plantear el cociente

n \to \infty lim \frac{3 n ^{2} + 5 n}{n ^{2}}

Dividir por n^2

n \to \infty lim (3 + \frac{5}{n})

Evaluar el límite

3 + 0 = 3

Conclusión

$L = 3$ es una constante positiva. Entonces $f (n)$ y $g (n)$ son del mismo orden. Crecen a la misma velocidad.