Page 14 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Para ver los tiempos de un algoritmo se requiere un análisis a priori, y no a posteriori. En un análisis a
priori se obtiene una función que acota el tiempo del algoritmo. En un análisis a posteriori se colecta
una estadística sobre el desarrollo del algoritmo en tiempo y espacio al momento de su ejecución. El
siguiente es un ejemplo de análisis a priori:

El análisis a priori ignora qué tipo de máquina es, así como el lenguaje, pues solo se concentra en
determinar el orden de magnitud de la frecuencia de ejecución.

Prácticamente todos los programas reales incluyen alguna sentencia condicional, lo que hace que
las sentencias efectivamente ejecutadas dependan de los datos concretos presentados. Por ello, se
debe hablar de un rango de valores, y no solo de un valor T(N):

T N) ≤ T(N) ≤ T (N)
min( max
Los extremos son habitualmente conocidos como peor caso y mejor caso, entre los cuales se hallará
algún caso promedio o más frecuente.
Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes K que depen-
den de factores externos al algoritmo, como pueden ser la calidad del código generado por el com-
pilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta. Dado que es fácil
cambiar de compilador y que la potencia de los ordenadores crece a un ritmo vertiginoso, se deben
intentar analizar los algoritmos con algún nivel de independencia de estos factores; es decir, buscar
estimaciones generales ampliamente válidas.

A la cantidad de operaciones básicas de un algoritmo que se representa como una función f(n) —
cuyo argumento es el tamaño de la entrada— se le denomina complejidad del algoritmo.

Se pueden emplear supercomputadoras para algoritmos altamente concurrentes; esto, en principio,
permite suponer que el problema se puede resolver n veces más rápido porque se tienen n procesa-
dores. Desafortunadamente, este no es el caso, ya que existen diferentes conflictos, como el acceso
a la memoria, el conflicto sobre la comunicación entre los trayectos de procesadores y procesadores
a memoria, así como la ineficiencia por la implementación de la concurrencia de los algoritmos. Por
eso, la estimación de la velocidad es mucho menor a n.
Una cota inferior estimada es la conjetura de Minsky, conocida como log (n). Para la cota superior,
2
depende de si el programa incluye la porción de entrada/salida (usualmente código secuencial). Si
es así, se considera la cota superior como n/ln(n).

8