Tema
Notación asintótica
- Algoritmos
- Nivel base
La notación O grande acota por arriba el crecimiento del coste de un algoritmo cuando el tamaño de la entrada tiende a infinito, sin mirar constantes ni términos de orden menor.
Nombre en inglés
Asymptotic notation
Intuición
Conviene fijarse en la forma de la curva y no en su altura: Dos algoritmos cuadráticos se diferencian en una constante, mientras que uno cuadrático y otro lineal acaban separándose tanto que la constante deja de importar. Para entradas pequeñas la constante sí manda, razón por la que las bibliotecas de ordenación cambian al método de inserción por debajo de unas decenas de elementos.
Fórmula
f(n) = O(g(n)) si existen c > 0 y n_0 con f(n) <= c g(n) para todo n >= n_0 ; Omega acota por abajo ; Theta acota por los dos lados
Ejemplo resuelto
Sea f(n) = 3 n^2 más 100 n más 5000. Con c igual a 4 y n_0 igual a 140 se cumple que f(n) es menor o igual que 4 n^2, ya que en n igual a 140 el lado izquierdo vale 77 800 y el derecho vale 78 400. Por tanto f pertenece a O(n^2). También pertenece a O(n^3), cota correcta aunque poco informativa, y no pertenece a O(n).
Errores frecuentes
- Confundir la O grande con el caso peor: Son dimensiones distintas, ya que cabe dar una cota superior del caso mejor y una cota inferior del caso peor.
- Sumar los costes de bucles anidados en lugar de multiplicarlos: Dos bucles seguidos suman y dos bucles anidados multiplican.
- Olvidar el coste de las operaciones internas: Un bucle de n iteraciones que copia una lista de n elementos cuesta n al cuadrado y no n, error frecuente con las rebanadas de Python.
Ejercicio
Un algoritmo hace un bucle de n iteraciones y dentro de cada una recorre una lista de longitud n. Al terminar, ordena esa lista una sola vez. ¿Cuál es su coste?
Ver la solución
El doble bucle cuesta n al cuadrado y la ordenación cuesta n log n. Como n al cuadrado domina a n log n, la suma se queda en el mayor de los dos términos.
Respuesta: O(n^2)