Tema 2 de ADA – Análisis y Diseño de Algoritmo
Reglas practicas para el calculo de la eficiencia.
- Programas iterativos. No realizan llamadas a si mismos(recursivas).
- En un programa iterativo puede haber:
- de orden 1: asignaciones, entrada/salida, expresiones de orden 1 –> tiempo constante.
- Sentecias secuenciales. Se aplica la regla de suma con las sentencias. El orden seria el maximo de cada uno de los ordenes de las sentencias.
- sentencias secuenciales. hay que tener en cuenta el caso mejor, peor y medio.
- Ejemplo:
- if (c) sentencia1: orden n2 else sentencia2: orden n
- El caso mejor sera cuandoi c = falso, (c NO es el tamaño del problema). Entonces el orden sera n.
- El caso peor sera cuando c sea verdadero. En esta caso el orden será n2.
- El caso medio debe estar entre el caso mejor y el peor.
- bucles. El orden será el orden máximo de las sentencias internas del bucle por el numero de veces que se ejecutara.
- Ejemplo:
- mientras c (orden 1) Sentencias (orden n) finmientras
- En este caso, la condicion del mientras, es de orden constante, luego siempre se ejecutara las sentencias de dentro un numero determinado de veces. El orden será 1·n o lo que es lo mismo n.
- Ejemplo2:
- mientras i
- En este caso, es de orden n·n, orden cuadratico. Siendo f el tamaño del problema. la condicion se ejecutara n veces, y las sentencias del buqcle, que son de orden n, se ejecutaran n veces.
- llamadas a funciones. La llamada en sí, es constante, habiendole que sumar el coste ed los parametros, mas el coste de las sentencias que tiene la funcion o método.
Instrucción crítica
Es una instrucción que se ejecutará igual o tantas veces mcomo cualquier otra del programa.
Es la instrucción que mas veces se puede ejecutar.
Ejermplo.(n es el tamaño del array)
desde i:=1 hasta n-1 j:=1 mientras j<=n-1 si a[j]>a[j+1]: sentecias de orden 1 fsi j:=j+1 fmientrasfdesde
Del bucle interior, hacemos el sumatorio desde j =1 hasta n-1 de 1 (sp=sum(1) desde 1 hasta n-1)
Del bucle exterior hacemos el sumatorio desde i = 1 hasta n-1 del sumatorio interior. (sum (sp) desde 1 hasta n-1).
Resolviendo, obtenemos que es de orden cuadrado.
sum (sum(1) desde 1 hasta n-1) desde 1 hasta n-1
*sum quiere decir sumatorio
