Hace poco empece a resolver los problemas de codility y al final de cada explicación del problema te ponen algo como esto:

Complexity:

  • expected worst-case time complexity is O(1);

Ya había escuchado y leído un poco sobre Big O y entendía un poco a que se referían con O(n) pero nunca se me hizo útil ni tampoco le tome importancia. Hasta que me tope con varios problemas de codility que pedían O(1) y en mi resultado daba algo como “10% performance, O(n) detectado”, ahí fue cuando dije ah ok quieren O(1) y lo hice O(n) y ahora que hago?

Antes que nada aclarar que esta no es una publicación donde veremos a fondo la definición teórica y matemática, es simplemente para que programadores como yo, que no sepan que es O notation puedan entenderlo, no se pierdan cuando se habla del tema  o simplemente puedan entender cuando en algún problema les pidan una solución O(log n) en lugar de O(n) como en codility.

Que es Big O?

Si van a wikipedia o a algún paper científico a buscar la definición de Big O posiblemente se asusten, así que definíamos Big O de esta manera: Simplemente es una forma de clasificar algoritmos dependiendo de como se comporta este cuando el tamaño del input va creciendo.

O(n)

Este tipo de algoritmo es el mas común, por ejemplo, nos piden encontrar un elemento en una lista:

Ejemplo:

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


def find(missing, A):
    for x in A:
        if x == missing:
            return True
    return False
    

Nuestro algoritmo es O(n) por que para encontrar nuestro elemento en la lista dependerá del tamaño de nuestro input, en este caso A. Como pueden ver vamos elemento por elemento de A y lo comparamos con nuestro elemento perdido, en el caso de que sea nuestro elemento perdido retornamos True y si al final no lo encontramos retornamos False, tal vez se pregunten pero que tal vez si el elemento esta en la primera posición de la lista? no seria O(1) en ese caso?, en ese caso tal vez si, pero O notation es acerca del PEOR caso y el peor caso es que este hasta el final o que no este.

Si graficamos su tiempo de ejecución, este crecería proporcionalmente al tamaño de su input:

Big O(n)

O(1)

En este caso nuestra función suma 1 a nuestro input:


def add(n):
    return n + 1

En este caso nuestra función es O(1) por que no importa si el input de nuestra función es 1 o 1, 000, 000 siempre va a tardar lo mismo por que lo único que hace es agregar 1 a nuestro input, en este caso si graficamos el tiempo de ejecución se vera una linea recta.

Big O(1)

O(n^2)
Seguramente todos han escuchado de bubble sort, es un algoritmo de ordenamiento simple que es O(n^2):


def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

Es O(n^2) por que su complejidad es igual al cuadrado del tamaño del input, si nuestro input tiene 5 elementos iterara 25 veces.
Big O(n^2)

Comparación:

Big O

Espero y a alguien le sirva de algo, estos son solo unos ejemplos pero podemos tener cosas como O(n + m) donde nuestra función hace una iteracion y después hace otra o O(log n) o O(n log n), etc…

It's only fair to share...Share on Facebook14Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Email this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *

Comment moderation is enabled. Your comment may take some time to appear.