En la computación moderna en mi opinión pocas veces se preocupa por la eficiencia de un algoritmo, ya no es problema obtener grandes recursos de memoria y capacidad de procesamiento. Sin embargo hay casos en que pueden ser cruciales para la ejecución de un programa cuando se cuentan con pocos recursos como un PIC/Arduino o son procesos críticos de seguridad. En estos casos se debe considerar y analizar el proceso con el fin de encontrar el más eficiente y adecuado dependiendo la situación donde se implementará.
Una herramienta útil para cuantificar o medir la eficiencia de un algoritmo es la complejidad algorítmica.
¿Qué es la complejidad de un algoritmo?
"La complejidad algorítmica representa la cantidad de recursos (temporales) que necesita un algoritmo para resolver un problema y por tanto permite determinar la eficiencia de dicho algoritmo."[1]. Esta medida no es absoluta sino relativa, pues depende de una entrada para poder medir el resultado. Siempre debe considerarse el peor resultado (El más largo).
La notación de Landau O(g)
Esta notación nos permite representar la complejidad algorítmica, sólo se considera el término más importante en caso de multiples algoritmos y se ignoran los factores constantes. Las principales ordenes de complejidad son:
| Orden | Nombre |
|---|---|
O(1)
|
constante
|
O(log n)
|
logarítmica
|
O(n)
|
lineal
|
O(n²)
|
cuadratica
|
O(n³)
|
cúbica
|
O(an)
|
exponencial
|
Ejemplos
Para los siguientes ejemplos usaremos JDOODLE y Python 3. Esta herramienta nos permite poner entradas personalizadas para poder analizar el orden de los algoritmos.
Asumiendo que el procesador pudiera calcular un número tan largo, si necesitamos calcular el factorial de 100 este hará 100 iteraciones, si fuera el de 1'000,000 también serían 1'000,000 iteraciones, es por ello que este algoritmo recibe un orden lineal.
En este ejemplo para encontrar el 5 se hicieron 18 iteraciones en un arreglo de 1'000,000. Si bien este fue casi el peor de los casos, este sería Log2(1'000,000) o Log2(n) es decir 19 iteraciones.
En este ejemplo para ordenar un arreglo de n = 1000 se tuvo que iterar 1'000,000 de veces. Es por ello que se considera cuadrático.
Si bien no consideramos el orden cúbico o exponencial es debido a su naturaleza, un algoritmo eficaz no debería cumplir con ese orden.
Fuentes:
https://www2.infor.uva.es/~jvalvarez/docencia/tema5.pdf
https://www.cs.us.es/~jalonso/cursos/i1m-18/temas/tema-28.html
O(1) - Constante
El orden constante son operaciones simples que no requieren iteraciones o que son constantes (No dependen de una entrada). Como ejemplo podríamos pensar en añadir IVA a una venta o bien Obtener la tabla de multiplicar del 7 del 1 al 10.
Url del ejemplo: https://www.jdoodle.com/a/1sni
c = 7
for x in range(10):
x = x + 1 # No empezar en 0
print("%s X %s = %s" % (x, c, x*c))
Si bien hay una iteración del 1 al 10 esta está definida y no cambiará; y aunque intentemos calcular la tabla de multiplicar de cualquier otro número esta seguirá siendo hacer una operación 10 veces.
O(n) - Lineal
El órden lineal son operaciones que dependen de n para iterar, tal como puede ser una sumatoria o un problema basado en entradas de lista. Como ejemplo usaremos la formula para calcular el factorial de un número, este es recursivo y depende de un número de entrada. Entre mayor sea el número a calcular esta serán el número de iteraciones a calcular para obtener el resultado de la función.
Url del ejemplo: https://www.jdoodle.com/a/1snk
def factorial(n):
if n == 2:
return n
elif n == 1:
return 1
else:
return n * factorial(n - 1)
n = 5 # Valor a calcular
print("Factorial: %s" % factorial(n))
Asumiendo que el procesador pudiera calcular un número tan largo, si necesitamos calcular el factorial de 100 este hará 100 iteraciones, si fuera el de 1'000,000 también serían 1'000,000 iteraciones, es por ello que este algoritmo recibe un orden lineal.
O(log n) - Logarítmica
El orden logaritmo no es tan común, aplica cuando el algoritmo itera en menor cantidad (constantemente) a la entrada, no es necesario especificar la base logarítmica. Podemos tomar como ejemplo la búsqueda binaria, en el peor de los casos revisará n / 2 veces hasta encontrar el número buscado. Si bien podría tardar un paso solamente para encontrar un número se debe considerar siempre el peor de los casos para encontrar el orden del algoritmo.
def busqueda_binaria(n, inf, sup, arreglo):
i = int((sup + inf) / 2)
print("sup:%s inf:%s pivote:%s" % (sup, inf, i))
if arreglo[i] is n:
return i
elif inf >= sup: # Los limites se alcanzaron
return -1
elif n > arreglo[i]:
return busqueda_binaria(n, i, sup, arreglo)
elif n < arreglo[i]:
return busqueda_binaria(n, inf, i, arreglo)
arreglo = range(1000000) # numeros del 1 al 1000
n = 5 # a buscar
print("Encontrado %s en posicion %s" % (n, busqueda_binaria(n, 0, len(arreglo) - 1, arreglo)))
En este ejemplo para encontrar el 5 se hicieron 18 iteraciones en un arreglo de 1'000,000. Si bien este fue casi el peor de los casos, este sería Log2(1'000,000) o Log2(n) es decir 19 iteraciones.
O(n²) - Cuadrática
El orden cuadrático es cuando un algoritmo itera el número de veces por si mismo una vez más. Este ya es considerado como el orden máximo que debería tener un algoritmo, pues no debería por qué iterar más de dos veces un sistema. Podemos considerar como ejemplo el ordenamiento burbuja que es comparar todos los números con todos otra vez para ordenarlos.
import random
def burbuja(arreglo):
length = len(arreglo)
for x in range(length):
for y in range(length):
if arreglo[y] > arreglo[x]:
aux = arreglo[x]
arreglo[x] = arreglo[y]
arreglo[y] = aux
return arreglo
arreglo = list(range(1000))
random.shuffle(arreglo)
print("Arreglo original: %s." % arreglo)
print("Arreglo ordenado: %s." % burbuja(arreglo))
En este ejemplo para ordenar un arreglo de n = 1000 se tuvo que iterar 1'000,000 de veces. Es por ello que se considera cuadrático.
Si bien no consideramos el orden cúbico o exponencial es debido a su naturaleza, un algoritmo eficaz no debería cumplir con ese orden.
Fuentes:
https://www2.infor.uva.es/~jvalvarez/docencia/tema5.pdf
https://www.cs.us.es/~jalonso/cursos/i1m-18/temas/tema-28.html
Comentarios
Publicar un comentario