Complejidad algorítmica
Qué se mide cuando se dice que un algoritmo es más eficiente que otro, qué significa exactamente la O grande y cómo se ordena la escala de órdenes de crecimiento.
Complejidad temporal y complejidad espacial
Medir un algoritmo con un cronómetro no sirve para compararlo: el resultado depende de la máquina, del lenguaje, del compilador y de lo que estuviera haciendo el ordenador en ese momento. Por eso se mide otra cosa: cómo crece el trabajo cuando crece el tamaño de la entrada, llamado n.
Ese crecimiento se mide en dos ejes que hay que declarar por separado. La complejidad temporal cuenta operaciones elementales y responde a cuánto tarda. La complejidad espacial cuenta memoria adicional y responde a cuánto ocupa. No van siempre de la mano: mergesort y heapsort tardan lo mismo en el peor caso, pero el primero necesita un vector auxiliar del tamaño de los datos y el segundo no necesita prácticamente nada.
La complejidad no dice cuántos segundos tarda un algoritmo, sino por cuánto se multiplica su trabajo cuando se multiplica el tamaño de la entrada. Es lo que permite compararlos sin ejecutarlos.
Para el examen
Complejidad temporal: operaciones en función de n
Complejidad espacial: memoria adicional en función de n
Que no van juntas: mergesort ocupa O(n) extra; heapsort, prácticamente nada
La notación O grande
La notación O grande expresa la cota superior asintótica: el ritmo de crecimiento que el algoritmo no supera cuando n se hace grande. Por eso se descartan dos cosas al escribirla: las constantes multiplicativas y los términos de orden menor, que dejan de importar frente al término dominante.
// Recuento de operaciones de un algoritmo cualquiera:
//
// 3n² + 500n + 2000
//
// Con n = 10 -> 300 + 5.000 + 2.000 (manda el término lineal)
// Con n = 1.000 -> 3.000.000 + 500.000 + 2.000
// Con n = 1.000.000 -> el término cuadrático se lo come todo
//
// Complejidad: O(n²)Esa es también la causa de un malentendido frecuente: un algoritmo O(n²) puede ser más rápido que uno O(n log n) para entradas pequeñas, porque las constantes que la notación desprecia sí existen en la práctica. La complejidad describe el comportamiento cuando n crece, no cuál gana con diez elementos.
Para el examen
Qué expresa: la cota superior asintótica
Qué se descarta: constantes y términos de menor orden
Ejemplo: 3n² + 500n + 2000 es O(n²)
O, Omega y Theta
La O grande no está sola. Son tres notaciones y cada una acota por un lado distinto, lo que se pregunta con frecuencia porque solo la primera es de uso corriente.
| Notación | Qué acota | Se lee como |
|---|---|---|
| O(f(n)) | Cota superior | No crece más deprisa que f(n) |
| Omega(f(n)) | Cota inferior | No crece más despacio que f(n) |
| Theta(f(n)) | Cota ajustada, superior e inferior a la vez | Crece exactamente al ritmo de f(n) |
En la práctica casi siempre se habla en O grande porque lo que interesa es la garantía de que no se va a tardar más de eso. Theta es la afirmación más fuerte, y por eso es menos habitual: exige que la cota valga por arriba y por abajo.
Para el examen
O grande: cota superior
Omega: cota inferior
Theta: cota ajustada: por arriba y por abajo a la vez
La escala de órdenes de crecimiento
Esta escala es lo más rentable del tema: se pregunta tanto por el orden de un algoritmo concreto como por cuál de dos órdenes es peor. Va de menor a mayor coste.
| Orden | Nombre | Operaciones con n = 1.000 | Ejemplo característico |
|---|---|---|---|
| O(1) | Constante | 1 | Acceder a una posición de un array |
| O(log n) | Logarítmica | unas 10 | Búsqueda binaria |
| O(n) | Lineal | 1.000 | Recorrer una lista, búsqueda secuencial |
| O(n log n) | n logarítmica o cuasilineal | unas 10.000 | Mergesort, heapsort, quicksort en caso medio |
| O(n²) | Cuadrática | 1.000.000 | Burbuja, inserción, selección |
| O(2 elevado a n) | Exponencial | un número de 302 cifras | Generar todos los subconjuntos de un conjunto |
| O(n!) | Factorial | inabordable | Probar todas las permutaciones (viajante de comercio por fuerza bruta) |
| O(n elevado a n) | Potencial exponencial | inabordable | El extremo superior de la escala |
La frontera práctica está entre O(n log n) y O(n²): por debajo de ella los algoritmos escalan a millones de datos, y por encima dejan de ser viables enseguida. A partir de O(2 elevado a n) solo se resuelven entradas muy pequeñas.
Para el examen
La escala, de menor a mayor: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), O(n!) y O(n^n)
Búsqueda binaria: O(log n)
Burbuja: O(n²)
Mejor caso, caso medio y peor caso
Un mismo algoritmo no tarda lo mismo con todas las entradas del mismo tamaño, así que su complejidad se declara para tres situaciones distintas.
- Mejor caso: la entrada más favorable posible. Por ejemplo, la burbuja optimizada sobre datos ya ordenados hace una sola pasada y termina, con lo que baja a O(n).
- Caso medio: el comportamiento esperado con una entrada cualquiera. Es el más difícil de calcular, porque hay que suponer cómo se distribuyen los datos.
- Peor caso: la entrada más desfavorable. Es la garantía dura, y por eso es la que suele darse por defecto y la que más se pregunta.
La diferencia entre caso medio y peor caso es lo que distingue a algoritmos que parecen equivalentes. Quicksort y mergesort son los dos O(n log n) en caso medio, pero en el peor caso quicksort se desploma a O(n²) y mergesort se mantiene en O(n log n).
Cuando una pregunta da un orden sin decir para qué caso, se refiere casi siempre al peor caso. Si el enunciado dice explícitamente «en el mejor caso» o «en promedio», la respuesta cambia.
Para el examen
Si no se especifica el caso: la complejidad declarada es la del PEOR caso
Quicksort: O(n log n) medio, pero O(n²) en el peor
Mergesort: O(n log n) siempre