Notacion sintotica

Algorítmica y Lenguajes de Programación Eficiencia y notación asintótica (ii)

Eficiencia y notación asintótica. Análisis de
algoritmos
n

n

n

En la lección anterior el concepto de eficiencia asintótica. En ésta se verá cómo se aplican estos conceptos a la hora de analizar algoritmos y determinar la eficiencia de los mismos. Presentaremos técnicas básicas para el análisis dealgoritmos iterativos y recursivos.

2

1

Eficiencia y notación asintótica. Reglas básicas (i)
n

Si el tiempo de ejecución T1(n) es de orden O(f1(n)) y T2(n) es de orden O(f2(n)) se cumple:
n n

n

n

T1(C · n) sigue siendo de orden O(f1(n)) T1(n) + T2(n) es de orden O(f1(n)) + O(f2(n)) = O(f1(n) + f2(n))= O(max(f1(n), f2(n))), max es la función dominante. T1(n) · T2(n) es de ordenO(f1(n)) · O(f2(n)) = O(f1(n) · f2(n)) T1(n) / T2(n) es de orden O(f1(n)) / O(f2(n)) = O(f1(n) / f2(n))
3

Eficiencia y notación asintótica. Reglas básicas (ii)
n

Por ejemplo:
n n n

O(2456·n) = O(n) O(20n)·O(n) = O(20n2) = O(n2) O(n2) + O(210n) = O(n2) + O(n) = O(n2 + n) = O(max(n2, n)) = O(n2) max(n·logan, logan)=n·logan max(bn, cn)=bn si b≥c max(nk, nm)=nk si k≥m max(logan, logbn)=logan sib≥a≥1 max(n!, bn)=n! max(bn, na)=bn si a≥0 max(n, logan)=n si a≥1 max (logan, 1)=logan si a≥1

n

Relaciones de dominación más comunes:
n n n n n n n n

4

2

Eficiencia y notación asintótica. Complejidad
instrucciones y estructuras de control (i)
n

Asignación:
n n

variable ß expresión Si la expresión es sencilla, por ejemplo:
n n n

variable ß 3.141592 variable ß a +betc.

n

Entonces el tiempo de ejecución sería del orden O(1); en caso contrario habría determinar el orden de la expresión, siendo de ese orden la asignación.
5

Eficiencia y notación asintótica. Complejidad
instrucciones y estructuras de control (ii)
n

Estructura secuencial:
sentencia 1 sentencia 2 ... sentencia s n El tiempo total de ejecución sería la suma de los tiempos de ejecuciónde cada sentencia; por tanto, sería del orden de O(f1(n)+f2(n)+ ... +fs(n)) o lo que es lo mismo O(max(f1(n), f2(n), ..., fs(n)), es decir la dominante de todas las funciones.
6

3

Eficiencia y notación asintótica. Complejidad
instrucciones y estructuras de control (iii)
n

Estructura alternativa
si expresión entonces bloque de sentencias si no otro bloque de sentencias fin si n Laexpresión, el primer bloque de sentencias y el segundo bloque de sentencias tendrán unos tiempos de ejecución determinados T1(n), T2(n), T3(n) con unos órdenes O(f1(n)), O(f2(n)) y O(f3(n)). El tiempo de ejecución de la estructura será la dominante de dichas funciones.
7

Eficiencia y notación asintótica. Complejidad
instrucciones y estructuras de control (iv)
n

Estructura repetitiva:
desdeißa hasta f(n) hacer ß bloque de sentencias fin desde
n

n

El bucle anterior se ejecuta un número de veces que es función del tamaño del problema (n); si el tiempo de ejecución del cuerpo del bucle es de orden O(g(n)) entonces el tiempo de ejecución del bucle compleo será del orden O(f(n)·g(n)). Si el bucle fuera un mientras o un repetir..hasta, entonces se debería tener en cuenta el ordende la expresión lógica, determinar la dominante entre dicha expresión y el cuerpo del bucle y aplicar la regla anterior.
8

4

Eficiencia y notación asintótica. Análisis de
algoritmos iterativos (i)
n

Ejemplo 1:
1.

desde iß1 a n ß desde jß1 a n ß escribir i+j fin desde fin desde
Asíntota para el tiempo de ejecución

2. 3.

El tamaño del problema viene definido en este caso porla variable n. Se va a la zona más interna del bucle (escribir i+j). Se trata de una sentencia elemental, por tanto, su tiempo de ejecución será de orden O(1). El bucle más interno (desde jß1 a n) se ejecuta n veces y su ß cuerpo tiene complejidad O(1), por tanto, este bucle tiene complejidad O(n·1)=O(n). El bucle más externo (desde iß1 a n) se ejecuta n veces y ß su cuerpo (el bucle anterior)...