AALIE

Cheatsheet — Resumen Rápido

Referencia rápida para resolver ejercicios de análisis iterativo, límites, notaciones, OE y sumatorias.

10. Cheatsheet — Resumen Rápido

Este módulo consolida los módulos 1 al 9 en formato de referencia rápida. Está pensado para repasar antes de parciales o para consultar durante ejercicios, no para reemplazar las explicaciones completas de los módulos anteriores.

10.1 Receta para analizar un algoritmo iterativo

Identificar todas las líneas, sin contar los end.
Para cada línea, determinar cuántas veces se ejecuta en función de $n$ .
Sumar todos los costos para obtener $T (n)$ .
Identificar el término dominante y aplicar la notación asintótica.

10.2 Receta para demostrar pertenencia a una familia asintótica

Calcular $L = lim_{n \to \infty} \frac{f ( n )}{g ( n )}$ o $L = lim_{n \to \infty} \frac{g ( n )}{f ( n )}$ .
Aplicar el teorema de límites para identificar qué notaciones aplican.
Concluir explícitamente con la notación correspondiente.

10.3 Técnicas para calcular límites

Dividir numerador y denominador por el término dominante del denominador.
Regla de L'Hôpital: si el límite es $\infty/\infty$ o $0/0$ , derivar numerador y denominador.
Logaritmos: para comparar funciones exponenciales, aplicar log a ambas.
Serie de Taylor: para aproximaciones más finas cerca del límite.

10.4 Resumen de OE por tipo de línea

Resumen de operaciones elementales por tipo de línea

Tipo de instrucción	OE	Notas
`x <- valor simple`	1	1 asignación
`x <- a + b` (o `-`, `*`, `/`)	2	1 aritmética + 1 asignación
`A[i] <- x`	2	1 acceso + 1 asignación
`if (a > b)`	1	1 comparación
`for i <- 1 to n`	3 por ejecución	asignación + comparación + incremento
`while (cond)`	OE de cond	Solo la evaluación de la condición
`llamar(fun)`	1	El cuerpo se analiza aparte

10.5 Trampa típica: cuándo NO mejorar un algoritmo

Cuando el análisis muestra que el orden de crecimiento es el mismo en el mejor y peor caso, como Bubble Sort con $O (n^{2})$ en ambos, no hay forma de mejorar el comportamiento del algoritmo sin cambiar su diseño fundamentalmente.

Si se pide “mejorar” la función de eficiencia pero no se puede bajar el orden, se puede intentar reducir las constantes, pero esto solo ayuda para $n$ pequeño. Para $n$ grande, el comportamiento asintótico domina.

Cuidado

Reducir constantes puede ser útil en implementación, pero no es una mejora asintótica. Si el orden sigue siendo el mismo, la familia de crecimiento no cambió.

10.6 Notación usada en el curso

Notación usada en el curso

Símbolo	Significado en clase
OE	Operación Elemental
$T (n)$	Función de eficiencia temporal
$T_{b es t} (n)$	Función de eficiencia en el mejor caso
$T_{w ors t} (n)$	Función de eficiencia en el peor caso
$A (n)$	Caso promedio (Average)
$n_{0}$	Valor de n a partir del cual aplica la cota
$c, c_{1}, c_{2}$	Constantes positivas en las definiciones formales
$\forall$	Para todo
$\exists$	Existe
$N$	Conjunto de los naturales
$R^{+} - {0}$	Reales positivos excluyendo el 0

10.7 Sumatorias — Las más usadas en el curso

Esta es la referencia rápida para el examen. Las sumatorias que aparecen en el 99% de los ejercicios del curso:

Sumatorias más usadas en el curso

Sumatoria	Resultado	Orden
$\sum_{i = 1}^{n} 1$	$n$	$Θ (n)$
$\sum_{i = 1}^{n} c$	$c \cdot n$	$Θ (n)$
$\sum_{i = 1}^{n} i$	$\frac{n ( n + 1 )}{2}$	$Θ (n^{2})$
$\sum_{i = 0}^{n} 2^{i}$	$2^{n + 1} - 1$	$Θ (2^{n})$
$\sum_{i = 1}^{n} i^{2}$	$\frac{n ( n + 1 ) ( 2 n + 1 )}{6}$	$Θ (n^{3})$
$\sum_{i = 1}^{n} \frac{1}{i}$	$\sim ln (n) + 0.5772$	$Θ (lo g n)$
$\sum_{i = 1}^{n} lo g (i)$	$\sim n lo g (n)$	$Θ (n lo g n)$
$\sum_{i = 1}^{n} \sum_{j = 1}^{i} 1$	$\frac{n ( n + 1 )}{2}$	$Θ (n^{2})$
$\sum_{i = 1}^{n} \sum_{j = 1}^{n} 1$	$n^{2}$	$Θ (n^{2})$
$\sum_{i = 1}^{n} \sum_{j = 1}^{i} i$	$\frac{n ( n + 1 ) ( 2 n + 1 )}{6}$	$Θ (n^{3})$
$\sum_{i = 1}^{n} \sum_{j = 1}^{l o g n} 1$	$n lo g (n)$	$Θ (n lo g n)$
$\sum_{i = 1}^{n} \sum_{j = 1}^{i} \sum_{k = 1}^{j} 1$	$\frac{n ( n + 1 ) ( n + 2 )}{6}$	$Θ (n^{3})$