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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En estos casos, interesa conocer cuál es la cantidad de pasos que realiza un algoritmo para procesar
una entrada de tamaño n, y no necesariamente cuál corre más rápido. Es decir, lo importante no es
saber si un mismo algoritmo corre más rápido en C/C++, en Java, en algún lenguaje especial o en
algún hardware específico, sino la cantidad de operaciones que realiza el algoritmo.

Esta tarea, por supuesto, no es sencilla, pues lo que se busca obtener es la complejidad, es decir,
establecer funciones que representen el orden de crecimiento de las operaciones en función del
tamaño de la entrada. Por ejemplo, en el caso del algoritmo 1.1, el orden de crecimiento es el de
una función lineal o de primer orden, mientras que el orden de crecimiento del algoritmo 1.2 y del
algoritmo 1.3 es el de una función cuadrática o de segundo orden. Como se verá en los siguientes
capítulos —en términos de análisis de algoritmos—, aunque los polinomios son distintos, se dice que
ambos algoritmos tienen la misma complejidad.

Informalmente, un algoritmo se define como un procedimiento computacional que toma un conjunto
de datos como entrada y genera otro conjunto de datos como salida. Por ende, un algoritmo es una
secuencia de pasos computacionales que transforma la entrada en salida. El algoritmo describe un
procedimiento computacional específico para encontrar la relación entrada-salida. Un ejemplo tradi-
cional para presentar el tema del diseño de los algoritmos se basa en ordenar una lista de números
de forma no creciente.

Entrada: Una lista de número
Salida: Reordenamiento de la secuencia de numero tal que

Metodología

Para enfocar la comparación de algoritmos se seguirán los siguientes pasos:

1. Averiguar la función f(n) que caracteriza los recursos requeridos por un algorit-
mo en función de tamaño n de los datos a procesar.
2. Dadas dos funciones f(n) y g(n), se define una relación de orden entre ellas, que
llamaremos complejidad, lo cual determinará cuándo una función es más compleja
que otra o cuándo son equivalentes.
3. Seleccionar una serie de funciones de referencia para situaciones típicas.
4. Definir conjuntos de funciones que llamaremos órdenes de complejidad.

12