El mejor algoritmo

Este post está dedicado a una persona que quiero mucho y que a pesar que cambió la informática por la economía, aún tiene un bichito informático dentro que se pregunta: ¿cómo saber si un algoritmo es mejor que otro? 

La respuesta es el clásico "depende":

- Depende de los datos, en algunos casos a medida que se evalúan más datos el algoritmo se va degradando, porque la función del rendimiento es exponencial por ejemplo.

- Depende de la arquitectura, en algunos casos el procesador está preparado para soportar operaciones más complejas en menor número de instrucciones.

- Depende del objetivo, en algunos casos se puede hacer un algoritmo muy complejo y casi ininteligible, con lo que a otro programador le costaría mucho entenderlo como para probarlo o modificarlo, se debe tener siempre en consideración que además de apoyarnos en buenos comentarios en el código y nombres de variables que ayuden a la comprensión, el código en sí, si es para uso masivo y cualquiera puede modificarlo no debería ser tan complejo, sin embargo si es un código cerrado, se puede elevar la complejidad.

Existen más variables que hacen que un algoritmo sea mejor o peor que otro, pero en este post quería centrarme estrictamente en la función de rendimiento que nos puede ayudar a hacer comparaciones entre diferentes soluciones.

Para entender mejor esto del rendimiento, trataremos el cálculo del factorial de un número:

Problema: Calcular el Factorial de N, donde N es un numero Natural >= 1
Supuestos:
1) Cada instrucción tarda una unidad de tiempo T
2) No consideraremos el tiempo en que se reserva memoria en la función recursiva

Propuesta 1 de Factorial
Función FactorialIterativa(N)
  F = N; --> T
  //la variable i va desde N-1 hasta 1 y es la que se va multiplicando
  i = N - 1; --> T 
  Mientras (i > 1) --> La comparación se realiza N-1 veces: T * (N-1)
    F = F * i; --> La comparación se realiza N-2 veces: T * (N-2)
    i = i - 1; --> La comparación se realiza N-2 veces: T * (N-2)
  Fin_Para
  Return F; --> T 
Fin_Función
Tiempo Total = T + T + T * (N-1) + T * (N-2) + T * (N-2) + T = (3N - 2) T

Propuesta 2 de Factorial

Funcion FactorialRecursiva (N)

  Si N = 1 --> Cada vez que se llama a la recursiva se hace la comparación, por tanto se hace N veces. N * T

    Return N --> Esta se hace sólo una vez, la última. T

  Caso Contrario

    Return N * FactorialRecursiva(N-1) --> Se ejecuta N - 1 veces. (N - 1) * T

  Fin_Si

Fin_Funcion

Tiempo Total = N * T + T + (N-1) * T = 2N * T

Con estas funciones de rendimiento, podríamos decir que para los supuestos considerados y para N > 2, la propuesta 2 tiene mejor rendimiento que la propuesta 1.

Con esto logramos tener una herramienta simple para comparar algoritmos, siempre bajo supuestos. 

Sería muy difícil contemplar todas las variables que intervienen, pero podemos aproximarnos y nos puede servir para optar por algún algoritmo u otro.