Data Structure & Algorithms
Cómo definir contratos, demostrar correctitud, diseñar invariantes y construir casos mínimos, límite y adversariales para verificar algoritmos.
Una solución es correcta cuando produce la salida especificada para toda entrada válida, no solo para los ejemplos probados.
La correctitud exige responder dos preguntas:
Los ejemplos ayudan a descubrir errores. Los invariantes y argumentos de prueba explican por qué la solución funciona en general.
Una especificación clara separa:
Ejemplo: binary search.
Precondición:
- values está ordenado de forma ascendente.
Postcondición:
- devuelve un índice i donde values[i] === target;
- o -1 si target no aparece.
Mutación:
- no modifica values.Sin la precondición de orden, la misma implementación deja de ser correcta.
Considera:
“Encuentra dos números que sumen
target.”
Todavía faltan decisiones:
Un algoritmo puede ser correcto para una interpretación y fallar para otra. Antes de optimizar, fija el contrato.
Una recursión puede devolver el valor correcto para casos que terminan y aun así ser incorrecta si algunas entradas generan recursión infinita.
Un invariante es una afirmación que permanece verdadera en puntos específicos del algoritmo.
Para un loop se demuestra normalmente en tres pasos:
El invariante no es un comentario decorativo. Debe describir qué parte del problema ya está resuelta y qué sigue pendiente.
function maximum(values: readonly number[]): number | undefined {
if (values.length === 0) return undefined;
let best = values[0];
for (let index = 1; index < values.length; index += 1) {
if (values[index] > best) {
best = values[index];
}
}
return best;
}Antes de cada iteración con índice index:
bestes el máximo del prefijovalues[0..index).
Antes de index = 1, el prefijo contiene solo values[0], por lo que best es su máximo.
La iteración compara el siguiente valor con best. Después, best es el máximo del prefijo ampliado.
Cuando index === values.length, el prefijo es todo el array. Por lo tanto, best es el máximo global.
function binarySearch(
values: readonly number[],
target: number,
): number {
let left = 0;
let right = values.length - 1;
while (left <= right) {
const middle = left + Math.floor((right - left) / 2);
if (values[middle] === target) return middle;
if (values[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}Invariante:
Si
targetexiste, alguna de sus posiciones está dentro del intervalo inclusivo[left, right].
Cuando values[middle] < target, el orden demuestra que ninguna posición hasta middle puede contenerlo. Actualizar left = middle + 1 conserva el invariante y reduce el intervalo.
La terminación se garantiza porque cada iteración excluye middle; la longitud del intervalo disminuye.
Muchos algoritmos dividen una colección en regiones con significados distintos.
En una partición:
[0..boundary) cumple la condición
[boundary..index) no la cumple
[index..n) sin procesarEn Dutch National Flag:
[0..low) ceros
[low..current) unos
[current..high] desconocidos
(high..n) dosesNombrar las regiones ayuda a decidir qué puntero mover después de cada caso.
Una estructura debe conservar reglas después de cada operación.
tail.next === null;size coincide con nodos alcanzables;head y tail son null.Para cada nodo no raíz:
parent <= childToda clave del subárbol izquierdo es menor y toda la del derecho es mayor, según la política de duplicados.
Cada nodo sigue padres hasta una raíz que se apunta a sí misma.
Una operación puede parecer funcionar localmente y aun así corromper un invariante que fallará más tarde.
No toda precondición debe comprobarse en runtime.
Binary search podría verificar que el array está ordenado, pero hacerlo cuesta O(n) y elimina la ventaja de una búsqueda O(log n).
Opciones:
La correctitud del algoritmo depende de la precondición, aunque la función no la valide cada vez.
Para un loop, identifica una medida que avanza hacia el final:
index aumenta hasta n;[left, right] disminuye;remaining disminuye con valores positivos.Para recursión, define una medida bien fundada:
n ≥ 0 y disminuye
longitud del rango disminuye
cantidad de nodos pendientes disminuyeSi una rama no reduce la medida, el algoritmo puede no terminar.
Los algoritmos recursivos suelen probarse mediante inducción.
Ejemplo: merge sort.
merge combina ambas sin perder elementos y conserva el orden.La prueba necesita justificar también que las mitades son más pequeñas y que merge es correcto.
Aparece en greedy.
No basta con decir que una opción “deja más espacio”. Debes conectar esa intuición con una transformación segura.
Supón que la afirmación es falsa y deriva una imposibilidad.
Ejemplo: en un MST, añadir una arista que conecta dos componentes puede crear un ciclo solo si ya existía un camino entre ellas, contradiciendo que eran componentes diferentes.
La técnica es útil, pero la contradicción debe depender de las propiedades del problema, no de una frase circular.
Una solución directa aporta:
Ejemplo:
function hasPairBruteForce(
values: readonly number[],
target: number,
): boolean {
for (let left = 0; left < values.length; left += 1) {
for (let right = left + 1; right < values.length; right += 1) {
if (values[left] + values[right] === target) return true;
}
}
return false;
}Después puedes comparar una versión con hashing en muchos arrays pequeños generados.
Un buen conjunto incluye varias categorías.
Una entrada representativa donde se recorren varias ramas.
Construido para romper una suposición:
Coloca la respuesta justo en el límite:
true al inicio o final;Antes del código, simula variables.
| Iteración | left | right | middle | Región pendiente |
|---|---|---|---|---|
| 0 | 0 | 5 | 2 | \[0, 5\] |
| 1 | 3 | 5 | 4 | \[3, 5\] |
| 2 | 3 | 3 | 3 | \[3, 3\] |
Las tablas descubren off-by-one y actualizaciones que no reducen el espacio.
Un caso límite pertenece al dominio y debe funcionar. Un caso especial puede ser una rama de implementación elegida por comodidad.
Por ejemplo, usar sentinel nodes elimina la rama especial de eliminar head, pero head sigue siendo un caso límite del problema.
Reducir ramas especiales suele simplificar la prueba.
Los tests muestran presencia de errores, no su ausencia para entradas infinitas.
Aun así, son esenciales para verificar la implementación concreta:
La prueba puede validar el algoritmo y el test descubrir que el código no implementa ese algoritmo.
En lugar de enumerar solo ejemplos, genera entradas y comprueba propiedades.
Para sorting:
Para reverse:
reverse(reverse(values)) = valuesPara Union-Find:
connected(a, b) es simétrica
si union(a, b), entonces connected(a, b)La herramienta busca contraejemplos y puede reducirlos a una entrada mínima. No sustituye entender la especificación.
Cuando no conoces fácilmente la salida exacta, transforma la entrada y predice una relación.
Ejemplos:
Ejecuta dos implementaciones sobre las mismas entradas:
for (const sample of samples) {
expect(optimized(sample)).toEqual(bruteForce(sample));
}Es muy útil al optimizar, pero ambas versiones podrían compartir el mismo error conceptual. Mantén una referencia sencilla e independiente.
Una función puede devolver el resultado esperado y violar su contrato al modificar la entrada.
function sortedUsers(users: readonly User[]): User[] {
return [...users].sort(compareUsers);
}Si la función prometía preservar users, el test debe comprobarlo explícitamente.
También prueba estabilidad cuando claves equivalentes deben conservar orden relativo.
Una fórmula matemáticamente correcta puede fallar por representación:
number;NaN;-0;La especificación debe incluir el dominio numérico y textual real.
Una estructura correcta en ejecución secuencial puede fallar con operaciones concurrentes. Atomicidad, race conditions y orden de memoria pertenecen a otro nivel de garantías.
No asumas que una implementación educativa de queue o cache es thread-safe.
Un algoritmo pasa diez mil casos aleatorios. ¿Eso demuestra que es correcto para toda entrada válida?
No. Aumenta la confianza y puede descubrir errores, pero sigue cubriendo una cantidad finita de entradas. La garantía general necesita un argumento sobre el invariante, los descartes y la terminación, además de tests de la implementación.