Analizar la complejidad del código con Python

La complejidad de un algoritmo mide el tiempo y/o el espacio que necesita un algoritmo para una entrada de tamaño dado (n). Aunque la complejidad depende de factores concretos como: la arquitectura del ordenador (es decir, la plataforma de hardware), la representación del tipo abstracto de datos (ADT), la eficiencia del compilador, la complejidad del algoritmo subyacente y el tamaño de la entrada. Aun así, los factores más determinantes suelen ser la complejidad del algoritmo en sí y el tamaño de la entrada.

En el tutorial de estructuras de datos en Python del blog de DataCamp puedes conocer una visión general de las estructuras de datos y cómo implementarlas en Python. Este artículo introduce las estructuras de datos básicas de Python. Verás qué es un tipo abstracto de datos y una estructura de datos, las estructuras de datos primitivas y las no primitivas.

Análisis asintótico

El análisis asintótico consiste en calcular el tiempo de ejecución de un fragmento de código u operación en una unidad matemática de cómputo. Se expresa en términos de una función como f(n). En análisis matemático, el análisis asintótico (o asintótica) es un método para describir el comportamiento en el límite.

El tiempo requerido por un algoritmo se clasifica en tres tipos: peor caso: tiempo máximo que necesita un algoritmo y es el que más se usa al analizarlo; mejor caso: tiempo mínimo, que normalmente no se calcula; caso promedio: tiempo medio, que a veces se considera en el análisis.

Notación asintótica

Las notaciones más utilizadas para calcular la complejidad temporal de un algoritmo son:

• Notación Big O
• Notación Big θ
• Notación Big Ω

Notación Big Oh, Ο

Big O se usa para medir el rendimiento o la complejidad de un algoritmo. En términos matemáticos, es la cota superior de la tasa de crecimiento de una función: si una función g(x) no crece más rápido que una función f(x), entonces g pertenece a O(f). En general, se utiliza para expresar la cota superior de un algoritmo y sirve para estimar su complejidad temporal en el peor caso, es decir, el mayor tiempo que podría tardar en completarse.

Notación Big Omega, Ω

La notación Ω(n) es la forma formal de expresar la cota inferior del tiempo de ejecución de un algoritmo. Mide el mejor caso, el menor tiempo que podría tardar en completarse.

Notación Big Theta, θ

La notación θ(n) expresa formalmente tanto la cota inferior como la cota superior del tiempo de ejecución de un algoritmo.

La notación se usa para determinar la complejidad de distintos algoritmos

La notación Big O es la más usada y sirve para hallar la cota superior de un algoritmo. La notación Big θ se utiliza a veces para describir el caso promedio y la notación Ω es la menos frecuente de las tres.

A continuación verás ejemplos de cómo se usan estas notaciones para determinar la complejidad de algoritmos concretos.

Por ejemplo, para quicksort:

Quicksort es un algoritmo de divide y vencerás para ordenar. Es un método sistemático para colocar elementos en orden, por ejemplo, ordenar números de un array en orden ascendente o descendente. Este algoritmo elige un pivote (un índice) del array dado. El pivote puede seleccionarse de distintas formas; en el ejemplo de abajo se elige el último elemento como pivote.

La clave de quicksort es la partición. A partir de un array se elige un elemento de partición y se coloca en su posición correcta; los elementos mayores que la partición van a su derecha y los más pequeños a su izquierda.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print (\"The Sorted array is:\")
for i in range(n):
    print (\"%d\" %array[i]),

The Sorted array is:
2
4
6
8
10
12
Obtendrás la salida:

The Sorted array is: 2 4 6 8 10 12

Ahora toca analizar la complejidad temporal. Para empezar,

• Mejor caso: Ω(n log n)
• Caso promedio: Θ(n log n)
• Peor caso: O(n^2)

Analicemos ahora el código anterior.

Mejor caso: se da cuando el elemento de partición elige como pivote el elemento central. Como el algoritmo se invoca recursivamente sobre la primera y la segunda mitad, el número total de pasos necesarios es el número de veces que tardas en pasar de n a 1 si divides el problema entre 2 en cada paso. Es decir, n/2/2/2/.../2 = 1, k veces. En realidad: n / 2^k = 1. Como 2^{log n} = n, obtenemos k = log n. Por tanto, el número de iteraciones es O(log n), y como cada iteración cuesta O(n), el tiempo total es O(n log n).

Caso promedio: para calcularlo habría que considerar todas las permutaciones del array y el tiempo que tarda cada una. Puedes ampliar información en Merge sort.

Peor caso: si se elige como pivote el primer elemento, el peor caso se produce cuando la entrada ya está ordenada en orden creciente o decreciente. Tras la partición, un lado tendrá tamaño 1 y el otro n-1. Sea T(n) la función de tiempo: tiempo de particionar n elementos O(n) + tiempo de quicksort para n-1 elementos T(n-1). Así, T(n) = T(n-1) + O(n) => T(n) = O(n^2).

Ejemplos

El siguiente código no es especialmente sofisticado, y quizá no lo llamarías algoritmo, pero técnicamente cualquier código que hace algo es un algoritmo y una forma de resolver un problema concreto. El ejemplo muestra un bucle for con una sola instrucción print.

print('I love Python');

¡Hola, mundo!
La complejidad temporal del algoritmo anterior es O(1) porque siempre realiza un único paso. Es tiempo constante.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print(\"Here's a stuff: {}\".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs ¿Cómo describirías la eficiencia del algoritmo anterior en notación Big O?

Para analizarlo, fíjate en cuántos pasos ejecuta. En el ejemplo hay cuatro elementos en la lista y se imprime cada uno una vez. Pero ¿qué ocurre si hay más de 4 elementos, por ejemplo 15? ¿Tomaría el bucle for el mismo número de pasos? Como este bucle realiza tantos pasos como elementos haya, diremos que su eficiencia es O(N) y no O(1).

El siguiente ejemplo es un algoritmo sencillo en Python para determinar si un número es primo:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

El código anterior acepta un número como argumento e inicia un bucle for en el que divides entre todos los números desde 2 hasta ese número y compruebas si hay resto. Si no hay resto, sabes que el número no es primo y devuelves False inmediatamente. Si llegas hasta el final y siempre hay resto, entonces sabes que el número es primo y devuelves True.

La eficiencia de este algoritmo es O(N). En este ejemplo no se recibe un array o lista, sino un número como argumento. Si pasas, por ejemplo, 11, el bucle for realiza unas once iteraciones (en realidad nueve, porque empieza en 2 y termina justo antes del propio número). Para 101, el bucle hace unas 101 iteraciones. Como el número de pasos crece al mismo ritmo que el valor pasado a la función, es un ejemplo clásico de O(N).

def twoForLoops(n):
    for i in range(1,n):
        print(\"Printing:\"+i);
    for i in range(1,100):
        print(\"Printing:\"+i);

En el código anterior, la complejidad del algoritmo es O(N). El segundo bucle tiene 100 como argumento, lo que puede ignorarse porque expresamos la complejidad asumiendo N muy grande.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print(\"Printing:\"+i);
    for i in range(0,n):
        print(\"Printing:\"+i);

Hay dos bucles: uno de longitud m y otro de longitud n. Suponiendo m y n grandes, la complejidad es O(n + m). Como los bucles son independientes y reciben entradas distintas, la complejidad es aditiva.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print(\"Printing:\"+(i*j));

Hay un bucle for anidado y, de nuevo asumiendo n y m grandes, la complejidad es O(n * m). Como los bucles son iguales y están anidados, la complejidad es multiplicativa.

¡Enhorabuena!

¡Has llegado al final de este tutorial! Por el camino, has aprendido notación asintótica y una herramienta básica que usan programadores y especialistas en datos. Acabas de ver una forma sencilla de analizar complejidad explicada en lenguaje claro, sin tecnicismos ni excesivo formalismo matemático. Aunque los temas de estructuras de datos y algoritmos suelen estudiarse en grados de informática o afines, es igualmente importante tener nociones básicas, sin necesidad de ser experto. Si quieres profundizar, echa un vistazo a este enlace: curso de algoritmos de MIT OpenCourseWare

Si quieres aprender más sobre Python, explora estos cursos de DataCamp: