Analisis de algoritmos

Curso: Lógica y Representación II
ANÁLISIS DE ALGORITMOS
Cuando se dice que un problema tiene solución, significa que existe un algoritmo
susceptible de implantarse en una computadora, capaz de producir la respuesta correcta
para cualquier instancia del problema en cuestión. Para ciertos problemas es posible
encontrar más de un algoritmo para resolverlos, lo que conlleva a tener queseleccionar
el mejor de ellos, de acuerdo a ciertos criterios.
Entre los principales criterios que se deben de tener en cuenta cuando se evalúa una
solución algorítmica, se encuentran los siguientes:
1. Que sea fácil de entender, implementar, depurar y mantener
2. Que se encuentre bien documentado
3. Que pueda ser usado por otros algoritmos
4. Que sea eficiente con respecto a los recursos queutiliza. La eficiencia
computacional de un algoritmo está relacionada principalmente con el tiempo
que demora su ejecución y el espacio que gasta en memoria, siendo el primero,
por lo general, el más importante.
Cuando se diseña una solución algorítmica para un programa que se va a usar con poca
frecuencia, no se justifica escoger entre varias soluciones, la más eficiente con respecto
a losrecursos, sólo se tendrían en cuenta los primeros tres criterios. En caso contrario,
si el programa se va a utilizar con periodicidad, se justifica escoger entre varias
soluciones encontradas la que sea más eficiente con respecto al uso de los recursos. De
todos modos, ninguno de los criterios de evaluación debe eliminarse por completo. Por
ejemplo, si se selecciona una solución muy eficiente peromuy difícil de entender, puede
suceder que después no sea posible darle el mantenimiento adecuado.
Se han definido tres enfoques para seleccionar la mejor solución algorítmica para un
mismo problema:
- El enfoque empírico (a posteriori): consiste en implementar cada una de las
soluciones algorítmicas y medir los tiempos reales obtenidos de cada una de
ellas.
- El enfoque teórico (a priori):consiste en encontrar en forma matemática la
cantidad de recursos necesarios para cada una de las soluciones algorítmicas
como una función del tamaño de los casos considerados.
- El enfoque híbrido: consiste en determinar en forma teórica las funciones que
describen la eficiencia de las diferentes soluciones algorítmicas para luego
encontrar en forma empírica aquellos parámetros numéricosque sean
específicos a cada una soluciones.
Medición del tiempo de ejecución de un Programa:
La eficiencia, o lo que se denomina la complejidad de una solución algorítmica se
define como el número de operaciones básicas requeridas por el algoritmo para procesar
una entrada de cierto tamaño. La complejidad de una solución algorítmica, se determina
a partir de los recursos que dicha soluciónnecesita para su ejecución, y se denota por
T(n).

Se han definido dos tipos de complejidad:
-

-

Complejidad temporal: Indica la cantidad de tiempo que requiere un algoritmo
para resolver un problema de tamaño n; ya que un algoritmo no se puede
ejecutar para medir la cantidad de tiempo que consume, la complejidad
temporal no se expresará en unidades de tiempo, sino en términos de lacantidad de operaciones que realiza.
Complejidad espacial: Indica la cantidad de espacio que requiere un algoritmo
para resolver un problema de tamaño n.

El tiempo de ejecución de un programa en función de n, no sólo depende de los datos
de entrada, sino del tamaño del problema, independientemente de la calidad del código
generado, de la máquina, etc. en que se vaya a implementar la soluciónalgorítmica.
Para cada problema se determina una medida n de su tamaño. El concepto exacto de lo
que mide n depende de la naturaleza del problema. Por ejemplo, en un método de
ordenamiento se tiene como entrada una lista de elementos para ordenar con el fin de
retornar la lista de elementos ordenados. El tamaño de entrada para este problema es el
número de elementos a ordenar. En algunos...