En las ciencias de la computación, la notación O grande (también llamada notación asintótica) se usa para describir la complejidad de los algoritmos o el rendiemento de los algoritmos. Esto significa que la notación O grande es usada para describir el tiempo de ejecución o el espacio utilizado por un algoritmo relativo al input cuando el input se hace arbitrariamente grande. En general, la notación O grande muestra el peor de los casos, porque matemáticamente hablando, se supone que la O grande representa la cota superior de una función. Voy a explicar las matemáticas al final de esta publicación.

Ejemplos y Explicaciones

O(1) o Tiempo Constante

Cuando una persona dice que un algoritmo tiene un velocidad de O(1), eso significa que, indepediente del tamaño del conjunto de datos, el algoritmo produciría la misma cantidad de tiempo para procesar. Como se muestra por el siguiente ejemplo, el tiempo de procesamiento de la función ‘ejemplo1’ no cambiaría si la lista tuviera cien elementos o solo uno.

def ejemplo1(lista):
    print(lista[0])

O(n) o Tiempo Lineal

Esto siginifica que el tiempo de procesamiento cambia lineal a la cantidad de datos que se la da. Un ejemplo sería un bucle for. Si cinco elementos existieran en una lista, el peor escenario sería que cinco búsquedas ocurrieran, en comparación con diez elementos, que sería diez búsquedas.

def ejemplo2(lista):
    for i in lista:
        print(lista[i])

O(n2) o Tiempo Cuadrática

O(n2) representa un algoritmo cuyo rendiemento es directamente proporcional al cuadrado del tamaño del conjunto de datos. Esto ocurre cuando hay un algoritmo que involcura bucles anidados. Las iteraciones más profundas darán resultados como O(n3), O(n4) y etcétera.

def ejemplo3(lista):
    for i in lista:
        for j in lista:
            print(lista[i][j])

O(2n)

Representa un algoritmo cuyo rendiemento se duplica con cada nueva adición al conjunto de datos. Un ejemplo sería un cálculo recusivo de los números de Fibonacci.

def ejemplo3():
     if n == 0: return 0
     elif n == 1: return 1
     else: return F(n-1)+F(n-2)

O(log n) y O(n log n)

No voy a mostrar ejemplos para ninguno de estos. Sin embago, una función con rendiemento de O(log n) sería una búsqueda binaria, y O(n log n) sería ordenamiento por mezcla (o mergesort, en inglés).

Mejor al Peor

También, quiero explicar qué funciones tienen el mejor rendiemento, como mínimo requerimiento de recursos. Del mejor al peor es O(1), O(log n), O(n), O(n log n), O(n2), O(n3), y el último es O(2n).

Resultado de imagen para plot n log n, n, log n

Las Reglas para Escribir Notación Grande O

Soltar las Constantes y Términos Menos Significativos

Notación O grande se trata de observar el rendimiento de un algoritmo, como el conjunto de datos se vuelven arbitrariamente grande, por lo que si los datos se multiplican por una constante o se dividen por una constante, se vuelve cada vez más insignificante al efecto del procesamiento de algoritmo. Por este razonamiento, soltamos los términos menos significativos. Por ejemplo,

O(2n) would be O(n)

O(n^3 + 15n) would be O(n^3)

Las Matemáticas

En realidad, hay es cuatro formas de describir las tasa de crecimiento de los algoritmos: O grande, o pequeño, omega y theta. O grande es el que se usa más comúnmente, y o pequeño es el segundo. En verdad, o pequeño no se puede explicar sin explicar omega y theta, también.

Las definiciones formales serían:

  • “T(n) = O(f(n))” ssi (si y solo si) para algunas constantes c y n0, T(n) <= cf(n) por todo n >= n0.
  • “T(n) = Ω(f(n))” ssi para algunas constantes c y n0, T(n) >= cf(n) por todo n >= n0.
  • “T(n) = Θ(f(n))” ssi T(n) = O(f(n)) y T(n) ≠ Ω(f(n)).
  • “T(n) = o(f(n))” ssi T(n) = O(f(n)) y T(n) ≠ Θ(f(n)).

 

Informalmente,

  • “T(n) = O(f(n))” basicamente significa que f(n) describe la cota superior por T(n) o que la tasa de crecimiento de T(n) <= la tasa de f(n).
  • “T(n) = Ω(f(n))” basicamente significa que f(n) describe el límite inferior por T(n) o que la tasa de crecimiento de T(n) >= la tasa de f(n).
  • “T(n) = Θ(f(n))” basicamente significa que f(n) describe el límite exacto por T(n) o que la tasa de crecimiento de T(n) == la tasa de f(n).
  • “T(n) = o(f(n))” basicamente significa que f(n) es la cota superior por T(n) pero T(n) nunca puede ser iqual a f(n) o que la tasa de crecimiento de T(n) < la tasa de f(n).

Nota de Autor: Muchos de los enlaces a continuación usan C ++ para sus ejemplos, pero como se trata más de teoría, no debería ser demasiado difícil de seguir.

Enlaces:

https://es.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation

https://www.campusmvp.es/recursos/post/Rendimiento-de-algoritmos-y-notacion-Big-O.aspx

https://es.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

http://www.itnuevolaredo.edu.mx/takeyas/apuntes/Matematicas%20para%20Computacion/Apuntes/Notacion%20O%20grande.pdf

http://www.lab.dit.upm.es/~lprg/material/apuntes/o/index.html

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *