EVALUACION DE ALGORTIMOS

Análisis de AlgoritmosTiempo de ejecución de un algoritmo

Prof.: Ricardo Botero Tabares

Ingeniería en Software

Facultad de Ingeniería

2014

Tiempo de ejecución de un algoritmo

Al evaluar un algoritmo se debe tener en cuenta su eficiencia en cuanto a:

– consumo de memoria y

– tiempo de ejecución,

teniendo en cuenta el tamaño de la entrada de datos.

2

La eficiencia en cuanto al consumo de memoria:

hoy es irrelevante.

La eficiencia en cuanto al tiempo de ejecución es relevante (a pesar de las altas velocidades del procesador), sobre todo en algoritmos relacionados con el control de

procesos en tiempo real y en aquellos cuya frecuencia de ejecución es alta.

Tiempo de ejecución de un algoritmo

3

¿Cómo medir el tiempo de ejecución de un algoritmo?

Existen dos formas: a posteriori y a priori .

– A posterioriSolución del problema (Identificación de requisitos, abstracción de clases, definición de las responsabilidades de las clases, escritura de seudocódigo OO), edición/compilación/ejecución del programa en una máquina y lenguaje determinado (aplicando pruebas continuas o paralelas).

Se depende de la calidad del compilador y de la máquina, por tanto es subjetiva la evaluación del algoritmo.

Tiempo de ejecución de un algoritmo

4

– A prioriLa evaluación del algoritmo se realiza con independencia del lenguaje de programación en el cual se codifique y de la máquina en la cual se ejecute. Para ello se deben definir dos conceptos básicos:

Contador de frecuencias y orden de magnitud.

Contador de Frecuencias:

es una expresión algebraica que indica el número de veces que se ejecutan las instrucciones de un algoritmo.

Tiempo de ejecución de un algoritmo

5

Algoritmo 1:void metodo1(){

int a, b, c;

double d;

Consola.imprimir(“Ingrese dos números enteros:”);

a = Consola.leerEntero();

b = Consola.leerEntero();

c = a + b;

d = (c % a) / 7;

Consola.imprimir (“Suma de ambos números: ” + c);

Consola.imprimir (“(” + c + “ % ” + a + “) / 7 = ” + d);

}

-------------- 1

---------------------------------------------------- 1

---------------------------------------------------- 1

----------------------------------------------------------------------- 1

------------------------------------------------------------------- 1

------------ 1

----------- 1_____CF = 7

Tmetodo1( ) es O(1)

Tiempo de ejecución de un algoritmo

6

Algoritmo 2:void metodo2(){

int acum, cont, n;

Consola.imprimir(“Ingrese un número entero:”);

n = Consola.leerEntero();

suma = 0;

cont = 1;

while (cont <= n){

suma = suma + cont;

cont = cont + 1;

}

Consola.imprimir(“Contador = ” + cont + “\nAcumulador = ” + suma);

}

--------------------------- 1

---------------------------------------------------------- 1

------------------------------------------------------------------------- 1

------------------------------------------------------------------------- 1

-------------------------------------------------------------- n + 1

--------------------------------------------------- n

---------------------------------------------------------- n------------------------------------------------------------------------ n

1_____

CF = 4n + 6Tmetodo2(n) es O(n)

Tiempo de ejecución de un algoritmo

7

Algoritmo 3:void metodo3(int n, int m){

int acum = 0, i = 1, j, cont;

while (i <= n){

cont = 0;

j = 1;

while (j <= m){

cont = cont + 1;

j = j + 1;

}

acum = acum + cont;

i = i + 1;

}

Consola.imprimir(n + “\n” + m + “\n” + acum);

}

--------------------------------------------- 2-------------------------------------------------------------- n + 1

--------------------------------------------------------- n------------------------------------------------------------- n

------------------------------------------------- (m +1) * n

----------------------------------m * n

--------------------------------------------m * n-------------------------------------------------------------- m * n

--------------------------------------- n

--------------------------------------------------------- n --------------------------------------------------------------- n

--------------------- 1______________

CF = 4 (n * m) + 7n + 4Tmetodo3(n, m) es O(n * m)

Tiempo de ejecución de un algoritmo

8

Algoritmo 4:void metodo4(int n){

int sum = 0, i = 1, tot, j;

while (i <= n){

tot = 0;

j = 1;

while (j <= n){

tot = tot + 1;

j = j + 1;

}

sum = sum + tot;

i = i + 1;

}

Consola.imprimir(n + “\n” + sum);

}

--------------------------------------------- 2--------------------------------------------------------- n + 1

----------------------------------------------------- n-------------------------------------------------------- n

-------------------------------------------- (n +1) * n

--------------------------------- n2

--------------------------------------- n2

------------------------------------------------------------ n2

--------------------------------------- n

--------------------------------------------------- n -------------------------------------------------------------- n

------------------------------ 1

________________

CF = 4n2 + 7n + 4

Tmetodo4(n) es O(n2)

Tiempo de ejecución de un algoritmo

9

Orden de magnitud:

El orden de magnitud define la eficiencia de un algoritmo en cuanto al tiempo de ejecución. Se obtiene a partir del contador de frecuencias, así:

De los términos resultantes, se eliminan los coeficientes, las constantes y los términos negativos; si los términos son dependientes entre sí, se elije el mayor de ellos. Si el contador de frecuencias es una constante, el orden de magnitud es O(1), es decir, constante.

Tiempo de ejecución de un algoritmo

10

Teniendo en cuenta lo anterior, los órdenes de magnitud de los algoritmos dados son:

– Algoritmo 1: O(1)

– Algoritmo 2: O(n)

– Algoritmo 3: O(n * m)

– Algoritmo 4: O(n2)

Tiempo de ejecución de un algoritmo

11

Órdenes de magnitud comunes

Orden de magnitud Representación

Constante O(1)

Logarítmico O(log2(n))

Lineal O(n)

Semilogarítmico O(nlog2(n))

Cuadrático O(n2)

Cúbico O(n3)

Exponencial O(2n)

Tiempo de ejecución de un algoritmo

12

Análisis de AlgoritmosTiempo de ejecución de un algoritmo

Prof.: Ricardo Botero Tabares

Ingeniería en Software

Facultad de Ingeniería

2014