Algoritmos y análisis de complejidad

El problema define entradas permitidas y respuestas válidas. El algoritmo especifica los pasos. La corrección parcial dice que, si termina, entrega una respuesta válida. Para corrección total se demuestra además que termina en toda entrada permitida. Acertar en varias pruebas sirve para detectar fallos, pero no sustituye esa garantía.

Un invariante es una afirmación que vale al inicio y se conserva al repetir un bucle. Junto a la condición de salida demuestra la respuesta. Para terminar se usa, por ejemplo, una medida entera no negativa que disminuye estrictamente en cada repetición. Hay que comprobar inicio, conservación, salida y terminación, no solo nombrarlos.

Para una lista, n suele ser el número de elementos. Para un entero positivo N escrito en binario, su longitud es b=⌊log₂N⌋+1 bits. Un algoritmo que hace N pasos puede ser exponencial respecto a b, aunque parezca lineal al usar N como variable.

En un modelo unitario se cuentan comparaciones, accesos o sumas como una operación cuando los operandos caben en palabras apropiadas. Si los números crecen sin cota, ese modelo no describe el coste de bits. La suma escolar de b bits necesita recorrer como máximo b posiciones y un acarreo; la multiplicación escolar realiza un orden cuadrático de operaciones de bits.

No se concluye que todos los algoritmos de multiplicación tengan ese coste.

T(n) cuenta trabajo; S(n) cuenta memoria máxima ocupada al mismo tiempo. Se declara si incluye entrada y salida o solo espacio auxiliar. Guardar resultados intermedios puede reducir trabajo repetido y aumentar memoria. Sumar todo lo reservado y liberado durante una ejecución no mide necesariamente el máximo simultáneo.

La recursión mantiene llamadas pendientes en una pila. Su profundidad y lo guardado en cada llamada cuentan aunque el código no declare un arreglo. Si se copian sublistas, esas copias también importan; pasar intervalos de una lista evita confundir una descripción de subproblema con una copia completa.

Con costes no negativos y g positiva desde cierto umbral, T=O(g) significa que existen C>0 y n₀ con T(n)≤Cg(n) para todo n≥n₀. Ω usa una cota inferior cg(n), c>0. Θ exige ambas. Las constantes se eligen una vez, no dependen de n.

Una función puede tener varias cotas superiores: T(n)=n pertenece a O(n), O(n²) y O(2ⁿ), pero estas últimas son menos precisas. Escribir O no afirma que la cota sea óptima ni una igualdad exacta de operaciones. Los términos de menor orden no cambian Θ si se justifican las dos cotas.

El peor caso maximiza el coste entre entradas de igual tamaño y el mejor lo minimiza. El promedio necesita una distribución explícita de entradas. No se obtiene promediando sin más las dos cifras extremas: las probabilidades de cada caso deciden el resultado.

El análisis amortizado reparte el coste total de una secuencia de operaciones. No necesita azar: puede garantizar un coste medio por operación para cualquier secuencia válida. Una operación particular puede ser cara y el total seguir siendo pequeño porque esas operaciones caras no pueden ocurrir continuamente.

Un bucle con n repeticiones de trabajo constante cuesta Θ(n). Dos bucles consecutivos suman; uno dentro de otro exige sumar cuántos pasos internos se hacen para cada valor exterior. Si el interior tiene siempre n pasos, la suma es n·n; si tiene i, la suma es 1+⋯+n.

La sumatoria escribe límites e índice para que no se pierdan filas. Para 1+⋯+n, escribir la suma en ambos sentidos da n pares de valor n+1; dividir por dos produce n(n+1)/2. Si el cuerpo cuesta i en vez de una unidad, ese trabajo también entra dentro de la suma.

Con n=2ᵏ, reducir a la mitad k veces deja uno: n/2ᵏ=1. Para la regla abstracta s←⌈s/2⌉ hasta s=1, el máximo de reducciones es ⌈log₂n⌉. Es una cuenta de cambios de tamaño, no una cifra universal de comparaciones para todo código de búsqueda binaria.

La búsqueda binaria usa una lista ordenada y acceso al elemento central con el coste supuesto. Tras comparar, descarta una parte conservando todos los candidatos que podrían contener el objetivo. En una lista enlazada, llegar al centro puede costar más; si hay que ordenar antes, ese trabajo se suma.

Logaritmos de bases fijas mayores que uno difieren por un factor constante.

En T(n)=2T(n/2)+n, con T(1)=1 y n potencia de dos, cada llamada crea dos mitades. El primer nivel trabaja n; el siguiente, 2·n/2=n; el siguiente vuelve a sumar n. Hay log₂n niveles internos y n hojas de coste uno. El total exacto es n log₂n+n.

Si el trabajo de combinación está entre constantes positivas por n, el argumento da Θ(n log n). Con tamaños generales se fijan suelos, techos y caso base; los niveles cambian en sus bordes pero mantienen el orden para la división equilibrada usual. Una sola llamada por nivel no tiene el mismo árbol y puede costar mucho menos.

Las constantes pueden decidir qué algoritmo conviene en entradas pequeñas. Medir tiempos complementa el análisis, pero depende del equipo, implementación y entradas. “Polinómico” respecto a longitud significa O(nᵏ) para algún exponente fijo; ni una constante enorme ni un exponente enorme garantizan viabilidad práctica.

Mostrar que un algoritmo tarda Θ(n²) no prueba que todos los que resuelven el problema deban hacerlo. Para una cota inferior del problema se considera cualquier algoritmo dentro de un modelo declarado. Un argumento de información puede demostrar límites del modelo de comparaciones, sin trasladarlos automáticamente a otros modelos.