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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

El debugging (depuración) solo indica la presencia de errores, no la ausencia de ellos. Al analizar un
algoritmo se debe tomar en cuenta tanto el aspecto temporal como el espacial, pues debe proce-
sar la información de forma rápida y correcta. Pero ¿cómo se puede determinar si un algoritmo es
eficiente o no?

Para responder esta interrogante se deben tomar en cuenta los conceptos tiempo de ejecución y
complejidad del algoritmo, los cuales se vinculan con la cantidad de pasos que realiza un algoritmo
para generar un conjunto de datos como salida a partir de un conjunto de datos de entrada.

Así, para analizar un algoritmo, lo primero que se debe hacer es verificar cuáles operaciones son
empleadas y su costo.

Estas operaciones se pueden acotar en un tiempo constante (p. ej., la comparación entre caracteres
se puede hacer en un tiempo fijo), mientras que la comparación de las cadenas depende del tamaño
de estas (no se puede acotar en tiempo).

Para cada problema se determina una medida N de su tamaño (por número de datos) y se intentan
hallar respuestas en función de dicha N. El concepto exacto que mide N depende de la naturaleza
del problema. Así, para un vector se suele utilizar como N su longitud: por ejemplo, para una matriz,
el número de elementos que la componen; para un grafo puede ser el número de nodos (aunque a
veces es más importante considerar el número de arcos, según el tipo de problema que se intenta
resolver), mientras que en un archivo se suele usar el número de registros, etc. En estos casos, es
imposible ofrecer una regla general, pues cada problema tiene su propia lógica de coste.
Una medida que suele ser útil es conocer el tiempo de ejecución de un programa en función de N,
lo cual se denomina T(N). Esta función se puede medir físicamente (ejecutando el programa con reloj
en mano) o se puede calcular sobre el código contando las instrucciones que se deben ejecutar y
multiplicando el tiempo requerido por cada instrucción.

7