Hace relativamente poco tiempo, que conozco la notación BIG O, usada comúnmente para hablar de la eficiencia y clasificación de los algoritmos basada en el tiempo en runtime y el espació utilizado.
Realmente, ser consciente de este concepto, hace que tengas en cuenta y pienses en BIG O, por cada algoritmo que desarrolles.
Si entráis en la wikipedia, pone: «En análisis de algoritmos una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.«
TIME IN RUNTIME
Para entender un poco de lo que estamos hablando, imaginaros que tenéis que hacer una suma de todos los números de una lista, esto implicaría, que tenemos que recorrerla si o si, por lo tanto tenemos un O(n) un resultado lineal con los valores de entrada n.
Otro ejemplo sería, devuelve el primer valor de una lista, sin importar el orden, esto sería O(1), da igual la cantidad de elementos, solo devolverás el primero.
Hay una cosa curiosa, que la anotación BIG O, debe representar una cota superior al resultado de la función que se esta evaluando.
Quiero decir, si ajustamos el tiempo en runtime de una función a O(N), también sería correcto decir O(N^2), dado que es una evaluación por encima del resultado de esta función. Aunque claro esta, se espera deducir que es O(N)
NOTACION BIG THETA
Antes de continuar, vamos hablar de otro tipo de anotación BIT THETA.
No sé de dónde he sacado esta imagen pero la usaré para ilustrar que tipo de anotación es BIG THETA.
Sí C2G(N) sería el resultado BIG O, CG(N) sería la estimación de THETA para f(N). Con esto quiero decir, que al igual que BIG O, BIG THETA es una aproximación por debajo al runtime de la función.
En conclusión BIG O seria el limite superior de la función y BIG THETA sería el limite inferior de la misma.
ESPACIO
Cuando hablamos de espacio, estamos hablando el espacio utilizado por nuestro algoritmo. No sería lo mismo hacer un sumatorio, utilizando una sola variable, que con dos (obviamente es algo a bajo nivel, el ejemplo preocupante sería algo a más escala).
Este espacio es igual de importante que time in runtime, dado que un algoritmo eficiente, puede superar el espacio de nuestra máquina siendo igualmente ineficiente.
Seguramente traiga ejemplos de anotaciones y optimización de algoritmos, será divertido!