Big Omega nos dice el límite inferior del tiempo de ejecución de una función, y Big O nos dice el límite superior.
A menudo, son diferentes y no podemos garantizar el tiempo de ejecución; variará entre los dos límites y las entradas. Pero, ¿qué pasa cuando son iguales? Entonces podemos dar un límite theta (Θ): nuestra función se ejecutará en ese tiempo, sin importar la entrada que le demos.
En general, siempre queremos dar un límite theta si es posible porque es el límite más preciso y más ajustado. Si no podemos dar un límite theta, la siguiente mejor opción es el límite O más estrecho posible.
Tomemos, por ejemplo, una función que busca en una matriz el valor 0:
def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false- ¿Cuál es el mejor caso? Bueno, si la matriz que le damos tiene 0 como primer valor, tomará un tiempo constante: Ω (1)
- ¿Cuál es el peor de los casos? Si la matriz no contiene 0, habremos iterado a través de toda la matriz: O (n)
Le hemos dado un omega y un límite de O, entonces ¿qué pasa con theta? ¡No podemos darle uno! Dependiendo de la matriz que le demos, el tiempo de ejecución será entre constante y lineal.
Cambiemos un poco nuestro código.
def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)¿Puedes pensar en el mejor y el peor de los casos? No puedo! No importa qué matriz le demos, tenemos que iterar a través de cada valor en la matriz. Entonces, la función tomará AL MENOS n tiempo (Ω (n)), pero también sabemos que no tomará más de n tiempo (O (n)). ¿Qué significa esto? Nuestra función tomará exactamente n tiempo: Θ (n).
Si los límites son confusos, piénselo así. Tenemos 2 números, xey. Se nos da que x <= y y que y <= x. Si x es menor o igual que y, e y es menor o igual que x, ¡entonces x tiene que ser igual a y!
Si está familiarizado con las listas enlazadas, pruebe usted mismo y piense en los tiempos de ejecución de cada una de estas funciones.
- obtener
- eliminar
- añadir
¡Las cosas se ponen aún más interesantes cuando se considera una lista doblemente vinculada!
Notación asintótica
¿Cómo medimos el valor de rendimiento de los algoritmos?
Considere cómo el tiempo es uno de nuestros recursos más valiosos. En informática, podemos medir el rendimiento con la cantidad de tiempo que tarda un proceso en completarse. Si los datos procesados por dos algoritmos son iguales, podemos decidir cuál es la mejor implementación para resolver un problema.
Hacemos esto definiendo los límites matemáticos de un algoritmo. Estas son las notaciones big-O, big-omega y big-theta, o asintóticas de un algoritmo. En un gráfico, la O grande sería lo más largo que podría tomar un algoritmo para cualquier conjunto de datos dado, o el "límite superior". Big-omega es como lo opuesto a big-O, el "límite inferior". Ahí es donde el algoritmo alcanza su máxima velocidad para cualquier conjunto de datos. Big theta es el valor de rendimiento exacto del algoritmo o un rango útil entre límites estrechos superior e inferior.
Algunos ejemplos:
- "La entrega estará allí durante su vida". (gran O, límite superior)
- "Puedo pagarte al menos un dólar". (omega grande, límite inferior)
- “El máximo de hoy será de 25ºC y el mínimo de 19ºC”. (big-theta, estrecho)
- "Es un kilómetro a pie de la playa". (big-theta, exacto)
Más información:
//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/