GUÍA 09-09-26 Teoría de la Computación

NE111 · miércoles 09/09/2026 · 16:00-17:15 · Sesión 10

Complejidad: medida de recursos y notación asintótica

CAMBIO DE PREGUNTA

La computabilidad pregunta si algo se puede resolver. La complejidad da por hecho que sí y pregunta cuánto cuesta. Es la diferencia entre posible y práctico.

QUÉ SE MIDE

• Complejidad temporal — número de pasos en función del tamaño de la entrada.
• Complejidad espacial — número de celdas de cinta utilizadas.

Se mide en función de n, el tamaño de la entrada, y en el peor caso, porque es la única garantía que se puede dar.

POR QUÉ ASINTÓTICA

Contar pasos exactos depende del modelo y de detalles irrelevantes de implementación. Lo que importa es cómo crece el costo cuando la entrada crece. Por eso se descartan constantes y términos de menor orden.

LAS NOTACIONES

• O(g) — cota superior. f crece a lo sumo como g.
• Ω(g) — cota inferior. f crece al menos como g.
• Θ(g) — cota ajustada. f crece exactamente como g.

JERARQUÍA DE CRECIMIENTO

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

LA FRONTERA QUE IMPORTA

Entre polinomial y exponencial hay un salto cualitativo, no de grado. Con n = 50, un algoritmo n³ hace 125 000 operaciones; uno de 2ⁿ hace más de 10¹⁵. Duplicar la velocidad de la máquina le agrega una unidad al tamaño de entrada tratable por el exponencial, mientras que al polinomial le multiplica el alcance.

Por eso la teoría identifica «tratable» con «tiempo polinomial», aunque un algoritmo n¹⁰⁰ no sea práctico. La distinción es cualitativa y resulta ser la correcta para clasificar problemas.

COMPLEJIDAD DE UN PROBLEMA, NO DE UN ALGORITMO

Un algoritmo tiene una complejidad; un problema tiene una cota inferior sobre todos los algoritmos posibles que lo resuelven. Demostrar cotas inferiores es mucho más difícil, porque hay que razonar sobre algoritmos que nadie ha escrito.

EJERCICIO

Determinar la complejidad de búsqueda secuencial, búsqueda binaria, ordenamiento burbuja y merge sort, y ubicarlas en la jerarquía.