Análisis de algoritmos y complejidad · Calculus × Computing

¿Qué es?

Predecir cómo crecen los recursos de un algoritmo con el tamaño de la entrada. Sus herramientas son cálculo de sucesiones puro: notación asintótica, límites, sumas e integrales, logaritmos y exponenciales, recurrencias.

Fórmulas

$T(n) = aT(n/b) + \Theta(n^c) \implies T(n) = \begin{cases}\Theta(n^c) & c > \log_b a\\ \Theta(n^c\log n) & c = \log_b a\\ \Theta(n^{\log_b a}) & c < \log_b a\end{cases}$
teorema maestro

¿Por qué importa?

La diferencia entre un algoritmo $O(n^2)$ y uno $O(n\log n)$ es, a gran escala, la diferencia entre horas y segundos, y ninguna mejora de hardware la cierra.

Las matemáticas que hay detrás

Funciones logarítmicas★★★★★fundamental
La búsqueda binaria es $O(\log n)$ y la ordenación por comparaciones $\Theta(n \log n)$ .
Límites en el infinito★★★★★fundamental
$f = \Theta(g)$ cuando $f(n)/g(n)$ se mantiene entre constantes positivas cuando $n \to \infty$ .
Serie geométrica★★★★★fundamental
El análisis amortizado de los arrays dinámicos y los casos del teorema maestro son sumas geométricas.
Órdenes de magnitud★★★★★fundamental
Elegir entre un algoritmo $O(n^2)$ y otro $O(n \log n)$ es comparar órdenes de crecimiento.
Notación asintótica (O, o, Ω, Θ)★★★★★fundamental
El lenguaje estándar de tiempo y memoria: $O(n)$ , $\Theta(n\log n)$ , cotas inferiores $\Omega(n)$ .
Desigualdades★★★★★frecuente
Las cotas superiores e inferiores de tiempo de ejecución se demuestran con cadenas de desigualdades.
Funciones exponenciales★★★★★frecuente
La búsqueda exhaustiva sobre $n$ bits cuesta $2^n$ pasos: el tiempo exponencial es la firma de lo intratable.
Límite de una función★★★★★frecuente
Las comparaciones asintóticas de tiempos de ejecución son límites cuando $n \to \infty$ .
Series numéricas★★★★★frecuente
Los costes de bucles y recursiones son sumas; los números armónicos dan el $\Theta(n\log n)$ medio de quicksort.
Criterio de la integral★★★★★frecuente
Convertir sumas como $\sum_{k\le n} \log k$ en integrales da $\log n! = n\log n - n + O(\log n)$ .
Funciones polinómicas★★★★★frecuente
«Tiempo polinómico» $O(n^k)$ es la frontera entre problemas tratables e intratables (P).
Sucesiones★★★★★frecuente
El tiempo de ejecución $T(n)$ es una sucesión, a menudo definida por una recurrencia como $T(n) = 2T(n/2) + n$ .
Regla de L'Hôpital★★★★★frecuente
Demuestra la jerarquía de crecimiento usada para comparar algoritmos: $\log n = o(n^\varepsilon)$ , $n^k = o(2^n)$ .
Series de potencias★★★★★avanzada
Las funciones generatrices $\sum a_n x^n$ resuelven recurrencias y cuentan estructuras en el análisis de algoritmos.
Criterios de comparación★★★★★frecuente
Acotar una suma de costes complicada por otra más sencilla es exactamente como se prueban las cotas asintóticas.
Método de bisección★★★★★indirecta
La misma idea que la búsqueda binaria (y git bisect): partir por la mitad da $O(\log n)$ pasos.