Algoritmos y complejidad: preguntas de práctica con explicaciones

1Qué mide la complejidad

Un algoritmo es una lista finita de pasos precisos que resuelve un problema, como ordenar una lista o encontrar un nombre en una guía telefónica.

Dos algoritmos pueden resolver el mismo problema pero tardar tiempos muy distintos. La complejidad describe cómo crece el trabajo cuando la entrada se hace mayor.

El tamaño de la entrada se llama n: el número de elementos a ordenar, la longitud de una lista, el número de nodos de un grafo.

Piensa en buscar un nombre en una guía telefónica de 1000 páginas. Leer todas las páginas lleva hasta 1000 pasos. Abrirla por la mitad y dividir por la mitad cada vez lleva unos 10 pasos.

La complejidad temporal cuenta los pasos. La complejidad espacial cuenta la memoria extra. Ambas se escriben como función de n.

Normalmente se mira el peor caso: el mayor trabajo entre todas las entradas de tamaño n. A veces se pide en su lugar el caso medio o el mejor caso.

2Notación O grande y clases de crecimiento

La notación O grande conserva solo lo que importa para n grande. Se descartan los factores constantes y se conserva solo el término de crecimiento más rápido.

Para n = 1000 el término n² es 3 000 000, mientras que 5n es solo 5000. Los términos menores apenas cambian el total.

Estas clases aparecen una y otra vez, de crecimiento más lento a más rápido:

• O(1), constante: leer un elemento de un array por su índice.
• O(log n), logarítmica: la búsqueda binaria, que reduce el problema a la mitad en cada paso.
• O(n), lineal: una pasada por todos los elementos, como encontrar el valor mayor.
• O(n log n): buenos algoritmos de ordenación como merge sort.
• O(n²), cuadrática: dos bucles anidados sobre los elementos, como bubble sort.
• O(2ⁿ), exponencial: probar todos los subconjuntos. Se vuelve inutilizable enseguida.

O grande es una cota superior: el trabajo crece como mucho a este ritmo. Ω (omega grande) es una cota inferior, y Θ (theta) es una cota ajustada, superior e inferior a la vez.

La base de un logaritmo no importa en O grande, porque los logaritmos de bases distintas se diferencian solo en un factor constante.

3Búsqueda, ordenación y recursión

Unos pocos algoritmos aparecen en casi todos los cursos. Aprende sus complejidades como hechos.

• La búsqueda lineal revisa los elementos uno a uno: O(n). La búsqueda binaria necesita un array ordenado y reduce el rango a la mitad en cada paso: O(log n).
• La ordenación burbuja, por inserción y por selección comparan e intercambian elementos en bucles anidados: O(n²). La ordenación por inserción es O(n) en un array que ya está ordenado.
• La ordenación por mezcla (merge sort) divide el array por la mitad, ordena las mitades y las mezcla: O(n log n) en todos los casos, con O(n) de memoria extra.
• La ordenación rápida (quicksort) divide en torno a un pivote: O(n log n) de media, pero O(n²) en el peor caso, por ejemplo un array ordenado con el primer elemento como pivote.
• Ninguna ordenación que solo compare elementos puede superar Ω(n log n) en el peor caso. La ordenación por conteo es más rápida porque no compara.

Una función recursiva se llama a sí misma con una entrada más pequeña hasta llegar a un caso base que responde directamente. Su tiempo de ejecución se escribe como una recurrencia:

• T(n) = T(n/2) + O(1) da O(log n), como la búsqueda binaria.
• T(n) = 2T(n/2) + O(n) da O(n log n), como merge sort.
• T(n) = T(n − 1) + O(n) da O(n²).
• T(n) = 2T(n − 1) + O(1) da O(2ⁿ).

Conviene conocer tres ideas de diseño. Divide y vencerás divide, resuelve y combina. Los algoritmos voraces toman en cada paso la mejor opción local. La programación dinámica guarda las respuestas de subproblemas solapados para calcularlas una sola vez.

4El método paso a paso

Para hallar la complejidad temporal de un trozo de código:

1. Decide qué es n: el tamaño de la entrada.
2. Cuenta cuántas veces se ejecuta cada bucle. Un bucle que suma 1 cada vez se ejecuta unas n veces. Un bucle que duplica o divide por la mitad se ejecuta unas log₂ n veces.
3. Los bucles anidados se multiplican. Los bucles uno tras otro se suman.
4. Para una función recursiva, escribe la recurrencia: cuántas llamadas, de qué tamaño, más el trabajo por llamada.
5. Conserva el término de crecimiento más rápido y descarta las constantes.
6. Comprueba con un número pequeño, por ejemplo n = 8 o n = 1024.

En una pregunta de teoría, nombra primero el algoritmo o la idea que describe, y luego recuerda su complejidad y sus condiciones (entrada ordenada, pesos no negativos, subproblemas solapados).

5Un ejemplo resuelto

Sigue cada paso. Intenta adivinar el siguiente antes de abrirlo.

6Errores frecuentes

• Multiplicar bucles que se ejecutan uno tras otro. n + n = 2n sigue siendo O(n).
• Conservar constantes, como en O(2n) o O(n/2). Ambos son O(n).
• Contar un bucle que duplica como n vueltas. Se ejecuta unas log₂ n veces.
• Usar la búsqueda binaria con datos sin ordenar, o con una lista enlazada donde no se puede llegar al medio en un solo paso.
• Dar el caso medio de quicksort cuando se pide el peor caso.
• Pensar que O grande significa “exactamente”. O(n²) es una cota superior; Θ(n²) es el crecimiento exacto.

7Cómo son las preguntas de examen

• Fácil: términos y datos clave. La complejidad de la búsqueda binaria, de merge sort o del acceso a un array, el significado de O, Ω y Θ, qué es la recursión.
• Medio: aplicar los conceptos. La complejidad de un fragmento de código, una recurrencia que resolver, cómo cambia el tiempo cuando n se duplica, qué algoritmo encaja con una tarea.
• Difícil: casos y análisis. El teorema maestro, los peores casos de quicksort, voraz frente a programación dinámica, y las clases P, NP y NP-completo.

P contiene los problemas que se pueden resolver en tiempo polinómico. NP contiene los problemas cuyas soluciones se pueden comprobar en tiempo polinómico. Todo problema de P está en NP; si P = NP sigue siendo desconocido.