Sabemos que, para un mismo problema, pueden existir varias soluciones. ¡Pero hay soluciones más eficientes que otras! Acá vemos un ejemplo (escrito en lenguaje Python, pero el ejemplo es válido para otros lenguajes).
Más abajo puede verse el código ejecutable en Python y también en C++, con medición del tiempo de ejecución de ambas versiones del algoritmo. Si bien en estos ejemplos de arreglos pequeños el tiempo no parece variar demasiado, para el caso de una gran cantidad de elementos (¿miles, cientos de miles, millones?) la diferencia sería muy notable.
Click acá para ver info sobre complejidad algorítmica
Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)
Ejercicio: complejidad algorítmica (resuelto)
Dada una lista de números, este algoritmo retorna dos elementos que, sumados, den un cierto resultado (o bien 0, 0 en caso de no hallarlos):
def sumandos(numeros, suma):
for a in numeros:
diferencia = suma - a
for b in numeros:
if (b != a) and (b == diferencia):
return (a, b)
return (0, 0)
Su complejidad es O(n2) porque tiene bucles anidados. ¿Puede mejorarse la complejidad a O(n)?
Resolución:
def sumandos(numeros, suma):
conjunto = set()
for a in numeros:
diferencia = suma - a
if diferencia in conjunto:
return (a, diferencia)
else:
conjunto.add(a)
return (0, 0)
Su complejidad es O(n). El bucle que itera por los n elementos de la lista nos da una complejidad de O(n). El operador “in” de Python tiene complejidad O(1), por lo que no influye en este resultado.