|
|
LLAMADAS A PROCEDIMIENTOS El tiempo de ejecución para un procedimiento está dado por el tiempo requerido para ejecutar el cuerpo del procedimiento llamado. Si un procedimiento hace llamadas a otros procedimientos "no recursivos", es posible calcular el tiempo de ejecución de cada procedimiento llamado, uno a la vez, partiendo de aquellos que no llaman a ninguno. Ejemplo 1: Función no recursiva que halla el factorial de un número n cualquiera, un sólo bucle.
Su complejidad es lineal O(n) debido a que se tiene un bucle FOR cuyo número de iteraciones es n. Ejemplo 2: Dos bucles anidados dependientes de n.
Tenemos O(n) * O(n) * O(1) = O(n^2), complejidad cuadrática. Ejemplo 3: Bucles donde la evolución de la variable de control es ascendente no lineal.
Para este ejemplo, al principio el valor de c es 1, al cabo de x iteraciones será 2^x, el número de iteraciones es tal que n= 2^x donde x es el entero inmediato superior de n y de esta manera, x = log2 n iteraciones. La eficiencia para este caso es: O(1) * O(log n) * O(1) = O(log n), complejidad logarítmica. Ejemplo 4: Bucles donde la evolución de la variable de control no es lineal, junto a bucles con evolución de variable lineal.
Tenemos un bucle interno de orden O(log n) que se ejecuta O(log n) veces, luego el conjunto de ordenes es de orden: O(1) * O(n) * O(log n) = O(n log n), complejidad cuasi-lineal. ¿Qué calculan estos algoritmos? Ejercicio: Dados los siguientes pares de funciones, ¿cuál es el menor valor de n de modo que la primera función sea mayor que la segunda? |
