Algoritmos: procedimientos, eficiencia y límites

Un programa ordena correctamente una lista de diez nombres. Con diez millones tarda días. Otro termina enseguida porque omite elementos repetidos. Un tercero funciona con números positivos y entra en un ciclo con cero. Decir «el algoritmo funciona» oculta al menos tres preguntas: para qué entradas, con qué resultado y con cuántos recursos.

Un algoritmo es un procedimiento finito y no ambiguo para transformar entradas en resultados o efectuar una tarea. Puede describirse sin un lenguaje de programación concreto. El programa es una realización sometida además a tipos, memoria, máquina, bibliotecas y errores de implementación.

Este capítulo pregunta: ¿cómo pasar de una intención informal a un procedimiento cuya corrección, terminación y coste puedan defenderse, y cómo reconocer problemas que ningún algoritmo general puede resolver?

453.1. Problemas, entradas y resultados#

Un problema computacional define un conjunto de instancias y qué salidas son válidas para cada una. «Buscar rápido» no basta. Hay que declarar qué se busca, cómo se representa, si puede faltar, si hay duplicados y qué significa devolver uno o todos los resultados.

Los problemas de decisión responden sí o no; los de búsqueda producen un objeto; los de optimización eligen el mejor según una función; los de conteo preguntan cuántas soluciones existen. Transformar uno en otro puede cambiar dificultad y evidencia requerida. Verificar que una ruta dada visita todas las ciudades es distinto de encontrar la ruta más corta.

La precondición describe entradas admitidas. La poscondición expresa qué debe cumplir la salida si la precondición era cierta. Un contrato para dividir exige divisor distinto de cero; uno para búsqueda binaria exige datos ordenados bajo una relación coherente. Si una entrada viola el contrato, el sistema necesita rechazarla o definir una conducta, no producir silenciosamente cualquier cosa.

Los casos pequeños y extremos revelan ambigüedad: colección vacía, un elemento, valores iguales, máximos representables, texto inválido o grafo desconectado. Probar ejemplos ayuda a descubrir el contrato, pero no demuestra corrección para todas las entradas.

La especificación puede permitir varias respuestas. Un ordenamiento estable conserva el orden relativo de elementos equivalentes; otro no. Dos rutas pueden tener el mismo coste óptimo. La corrección debe juzgar la propiedad declarada, no exigir una salida idéntica cuando el problema admite muchas.

El tamaño de entrada se define de acuerdo con la representación. Un entero $n$ ocupa aproximadamente ${\log }_{2}n$ bits, no $n$ símbolos. Un algoritmo que repite $n$ pasos puede ser exponencial respecto de la longitud binaria de la entrada. Elegir la medida equivocada distorsiona la complejidad.

453.2. Representaciones y estructuras de datos#

Una representación decide qué operaciones son directas y cuáles costosas. Una lista mantiene secuencia; un arreglo permite acceso por posición; una tabla hash busca por clave en tiempo esperado bajo supuestos; un árbol ordenado conserva relaciones; un grafo representa conexiones. Ninguna estructura es universalmente mejor.

La interfaz declara operaciones observables; la implementación decide cómo realizarlas. Una cola promete insertar al final y retirar al frente. Puede construirse con arreglo circular o nodos enlazados. Separar ambas permite cambiar coste interno sin obligar a los usuarios a conocer cada puntero.

Las estructuras mantienen invariantes. En un árbol de búsqueda, las claves a cada lado respetan una relación; en un montículo, padre e hijos cumplen prioridad; en una tabla, cada registro corresponde a una clave según reglas. Una operación correcta preserva el invariante además de producir su resultado inmediato.

Representaciones redundantes aceleran consultas y encarecen actualizaciones. Un índice duplica claves y ubicaciones; una caché guarda resultados derivados; una matriz de adyacencia reserva espacio para conexiones ausentes. El diseño compara frecuencia de lectura, escritura, memoria, localidad y riesgo de inconsistencia.

Los datos reales no obedecen siempre al promedio supuesto. Una tabla hash puede sufrir muchas colisiones; un árbol sin balancear puede convertirse en cadena; un grafo puede ser disperso o denso. El análisis declara distribución o usa garantías de peor caso cuando la adversidad importa.

La representación también afecta seguridad y corrección. Índices fuera de rango, ciclos inesperados, alias entre referencias y desbordamientos convierten un modelo abstracto en fallos concretos. Definir propiedad, límites y mutabilidad reduce estados imposibles.

453.3. Corrección y terminación#

La corrección parcial afirma: si el algoritmo termina, su resultado cumple la poscondición. La corrección total añade que termina para toda entrada admitida. Separarlas evita aceptar un procedimiento que nunca entrega la respuesta en un caso difícil.

Para un bucle se usa un invariante: una propiedad cierta antes de empezar, preservada por cada iteración y suficiente, junto con la condición de salida, para concluir. En un ordenamiento incremental, por ejemplo, un prefijo puede permanecer ordenado y contener exactamente los elementos ya procesados.

La terminación puede demostrarse con una variante que disminuye en un orden bien fundado y no puede bajar indefinidamente: elementos pendientes, distancia a un límite o tamaño de un subproblema. Que «parezca acercarse» no basta si puede oscilar o decrecer en cantidades sin límite inferior adecuado.

La recursión necesita casos base y llamadas sobre instancias estrictamente menores según una medida. Un caso base alcanzable para ejemplos no garantiza que toda rama lo alcance. La profundidad puede además superar la pila aun cuando la definición termine matemáticamente.

Las pruebas de software complementan, no sustituyen, el razonamiento. Un test unitario cubre casos seleccionados; pruebas generativas exploran familias e invariantes; análisis estático aproxima propiedades; verificación formal relaciona programa y especificación dentro de un modelo. Cada técnica tiene alcance y supuestos.

La especificación también puede ser errónea. Probar que un programa cumple «aprobar a quien tenga identificador par» no vuelve justa la regla. La verificación responde si construimos el sistema según el contrato; la validación pregunta si el contrato resuelve la necesidad correcta.

453.4. Complejidad y órdenes de crecimiento#

La complejidad describe recursos como función del tamaño de entrada: tiempo, memoria, comunicaciones, accesos a disco o energía aproximada. No es un cronómetro concreto. Abstrae constantes y arquitectura para comparar crecimiento y luego se complementa con medición.

La notación $O(g(n))$ da una cota superior asintótica; $\mathrm{\Omega }(g(n))$, una inferior; $\mathrm{\Theta }(g(n))$, un orden ajustado. Decir $O(n^2)$ no significa exactamente $n^2$ operaciones ni que un algoritmo siempre sea lento. Para tamaños pequeños, constantes y localidad pueden dominar.

Un recorrido lineal crece aproximadamente con $n$; búsqueda binaria en datos ordenados, con $\log n$; ciertos ordenamientos, con $n\log n$; enumerar todos los subconjuntos, con $2^n$. Duplicar la entrada apenas añade un paso logarítmico y puede cuadruplicar un trabajo cuadrático o duplicar un exponente.

Se distingue peor caso, mejor caso, caso promedio y análisis amortizado. El promedio necesita distribución; el amortizado reparte operaciones costosas sobre una secuencia sin suponer azar. Un sistema expuesto a entradas controladas por adversarios no debe justificar seguridad con un promedio benigno.

La complejidad espacial importa porque memoria finita, cachés y transferencia cambian tiempo real. Un algoritmo puede ganar velocidad almacenando resultados; otro procesa flujo con poca memoria y varias pasadas. La mejor opción depende de restricciones, no sólo de una clase asintótica.

Los problemas tratables suelen asociarse a tiempo polinómico, pero «polinómico» no garantiza uso práctico y «exponencial» no vuelve inútil toda instancia. Estructura especial, aproximación, parámetros pequeños y heurísticas permiten resolver casos. Una heurística útil debe declarar cuándo puede fallar y cómo se evalúa.

453.5. Computabilidad y problemas sin solución algorítmica general#

Antes de preguntar cuánto tarda un algoritmo, hay que preguntar si existe. La computabilidad estudia qué funciones pueden realizarse mediante procedimientos efectivos bajo modelos formales. Máquinas de Turing, cálculo lambda y otros modelos razonables convergen en la misma clase de funciones, fundamento de la tesis de Church–Turing.

Una máquina universal puede recibir la descripción de otra máquina y sus datos y simularla. Esa generalidad permite tratar programas como datos, pero también construir autorreferencia. Turing mostró en 1936 límites a procedimientos generales al estudiar números computables y el problema de decisión.

El problema de parada pregunta si existe un algoritmo que, para cualquier programa y entrada, decida correctamente si terminará. Suponer ese decisor permite construir un programa que contradice su propia predicción. Por tanto, no existe un decisor total general. Esto no impide resolver casos particulares ni detectar muchas terminaciones; impide una garantía universal.

Un problema indecidible no es simplemente muy lento ni aún no resuelto. No existe algoritmo que siempre termine con la respuesta correcta para todas sus instancias bajo el modelo. Un problema decidible pero intratable sí tiene procedimiento, aunque sus recursos crezcan demasiado.

Las reducciones trasladan dificultad. Si toda instancia de A puede transformarse eficientemente en B, resolver B permite resolver A. En complejidad, la completitud identifica problemas representativos de una clase. El teorema de Cook relacionó satisfacibilidad booleana con problemas verificables eficientemente y abrió la teoría de NP-completitud; no demostró que $P\ne NP$.

Los límites formales no autorizan fatalismo. Restricciones de dominio, contratos, analizadores conservadores y supervisión resuelven tareas reales. Tampoco autorizan promesas absolutas: un analizador puede preferir falsas alarmas para no omitir cierta clase, o renunciar a terminar en algunos casos. La herramienta debe declarar su frontera.

Síntesis#

Un problema computacional necesita instancias, representación y criterio de salida. Las estructuras de datos hacen baratas unas operaciones y costosas otras. La corrección parcial, la terminación y el coste son afirmaciones diferentes y requieren evidencias distintas. La complejidad compara crecimiento bajo una medida explícita. La computabilidad establece una frontera anterior: algunos problemas carecen de algoritmo general, aunque casos restringidos sigan siendo resolubles.

Preguntas de transferencia#

1. Un algoritmo pasa un millón de pruebas. ¿Está demostrado que es correcto?#

No. Las pruebas aportan evidencia sobre casos; una demostración cubre el dominio mediante especificación e invariantes. Ambas pueden revelar fallos distintos.

2. Dos algoritmos son $O(n)$. ¿Tardan lo mismo?#

No. La notación omite constantes, operaciones, hardware y localidad. Indica crecimiento asintótico compatible, no igualdad de tiempo.

3. Un analizador no puede decidir la terminación de todo programa. ¿Es inútil?#

No. Puede decidir lenguajes restringidos, demostrar muchos casos o responder «desconocido» conservadoramente. El límite impide una solución total universal.

4. ¿Por qué cambiar una lista por una tabla hash no es mejora automática?#

Porque cambian memoria, orden, peor caso, actualizaciones y supuestos sobre claves. Mejora sólo respecto de operaciones y entradas relevantes.

Fuentes y lecturas del capítulo#

• Alan M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 1936.
• Stephen A. Cook. The Complexity of Theorem-Proving Procedures. Proceedings of STOC, 1971.
• National Institute of Standards and Technology. Dictionary of Algorithms and Data Structures. NIST, recurso mantenido.
• Edsger W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976; manuscritos EWD relacionados.
• Robert W. Floyd. Assigning Meanings to Programs. Proceedings of Symposia in Applied Mathematics, 1967.

Bibliografía de la parte XLI · Bibliografía general

Última revisión editorial

7 de octubre de 2026

Cierre de contenidos

7 de octubre de 2026