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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Por ejemplo, un algoritmo que busca el máximo en n elementos desordenados siempre realizará n-1
iteraciones, por lo tanto:

(n).

Ahora bien, un algoritmo que busque en un arreglo un valor determinado.
O(n) (1)

Aunque no existe una receta que funcione siempre para calcular la complejidad de un algoritmo, sí es
posible tratar sistemáticamente una gran cantidad de ellos, ya que suelen estar bien estructurados
y seguir pautas uniformes.

Los algoritmos bien estructurados combinan las sentencias según alguna de las siguientes formas:

• Sentencias sencillas

Son las sentencias de asignación, entrada/salida, etc., siempre y cuando no tra-
bajen sobre variables estructuradas cuyo tamaño esté relacionado con el tamaño
N del problema. La mayoría de las sentencias de un algoritmo requiere un tiempo
constante de ejecución, siendo su complejidad O (1).
• Secuencia

La complejidad de una serie de elementos de un programa es del orden de la suma
de las complejidades individuales, aplicándose las operaciones arriba expuestas.
• Decisión

La condición suele ser de O (1), complejidad a sumar con la peor posible, bien en
la rama THEN, o bien en la rama ELSE. En decisiones múltiples (ELSIF, CASE) se
tomará la peor de las ramas.
• Bucle

En los bucles con contador explícito se pueden distinguir dos casos: el tamaño N
forma o no forma parte de los límites.
Si el bucle se realiza un número fijo de veces, independiente de N, entonces la
repetición solo introduce una constante multiplicativa que puede absorberse.

for (int i= 0; i < K; i++)
algo_de_ O (1);

K * O (1) = O (1)

19