Introducción al análisis de algoritmos

Factores

• Consumo de memoria

• Tiempo de ejecución

• Independiente de la máquina

• Independiente del lenguaje de programación

Conceptos Básicos

Contador de frecuencias:

Expresión algebraica que indica el

número de veces que se ejecutan

las instrucciones de un algoritmo

Ejemplos: Algoritmo 1

Lea a,b,c 1 x=a+b 1 y=a+c 1 z=b*c 1 w=x/y-z 1 Escriba a,b,c,w 1

-----------------Contador de frecuencias 6

Algoritmo 2

Lea n 1 s=0 1 i=1 1 While i<=n n+1 s=s+1 n i=i+1 n End While n Escriba n,s 1

-------------Contador de frecuencias 4n + 5

Algoritmo 3 Lea n,m 1 s=0 1 i=1 1 While i<=n n+1 t=0 n j=1 n While j<=m (n*m)+n t=t+1 n*m j=j+1 n*m End While n*m s=s+t n i=i+1 n End While n Escriba n,m,s 1

-----------------Contador de frecuencias: 4(n*m) + 7n + 5

Algoritmo 4Lea n 1 s=0 1 i=1 1 While i<=n n+1 t=0 n j=1 n While j<= n n2+n t=t+1 n2

j=j+1 n2

End While n2

s=s+t n i=i+1 n End While n Escriba n,s 1

-----------------Contador de frecuencias: 4n2 + 7n + 5

Algoritmo 5 Lea n,m 1 s=0 1 i=1 1 While i<=n n+1 s=s+1 n i=i+1 n End While n Escriba n,s 1 s=0 1 i=1 1 While i<=m m+1 t=t+1 m i=i+1 m End While m Escriba n,s 1

-----------------Contador de frecuencias: 4n + 4m + 9

Conceptos Básicos (cont.)

Orden de Magnitud:- Indica como crece el tiempo de ejecución de un

algoritmo cuando crece el tamaño del problema resuelto por el algoritmo, es decir, se mide en base a un tamaño de entrada el cual puede ser el número de elementos a imprimir, a sumar a ordenar etc.

- Se puede obtener a partir del contador de frecuencias así:

• Se eliminan del contador de frecuencias los coeficientes, constantes y términos negativos

• De cada conjunto de términos dependientes (de una misma variable) se selecciona el término dominante (mayor)

• El orden de magnitud será la suma de los términos seleccionados (normalmente es uno solo…)

Para los algoritmos anteriores se tienen los siguientes órdenes de magnitud:

Algoritmo Orden1 O(1)2 O(n)3 O(nxm)4 O(n2)5 O(n+m)

Órdenes de magnitud más frecuentes ordenados en forma ascendente desde el más eficiente:

O(1) Constante O(log2n) Logarítmico O(n) Lineal O(nlog2n) Semilogarítmico n2 Cuadrático n3 Cúbico 2n Exponencial

Ejemplo: Suma de los n números enteros:

Algoritmo a:Lea n

s=1 suma=0 While s<=n suma=suma + s s=s+1 End While Escriba suma

Algoritmo b Lea n

suma=n*(n+1)/2

Escriba suma

El algoritmo a es O(n) mientras que el algoritmo b es O(1)

Más ejemplos

Lea n 1 s=0 1 i=n 1

While i>1 Log2n + 1

s=s+1 Log2n

i=i/2 Log2n

End While Log2n Escriba n,s 1

----------------

Contador de frecuencias= 4 Log2n + 5

O(Log2n)

Lea n 1 s=0 1 For i=1 to n n+1 t=0 n For j=1 to i n*(n+1)/2 + n t=t+1 n*(n+1)/2 End For n*(n+1)/2 s=s+t n End For nEscriba n,s 1

---------------------------Contador de frecuencias: 3n*(n+1)/2 + 5n + 4

= (3n2 + 3n)/2 + 5n + 4 O(n2)

Lea n 1 s=0 1 i=1 1 while i<= n n+1 t=0 n j=n n while j>1 n*Log2n + n t=t+1 n*Log2n j=j/2 n*Log2n End while n*Log2n Escriba t n s=s+t n i=i+1 n End while n Escriba n,s 1

-------------------------Contador de frecuencias: 8n + 4n*Log2n + 5 O(n*Log2n)

Lea n 1 s=0 1 For i=1 to n n+1 t=0 n For j=1 to i n*(n+1)/2 + n

For k=1 to j z+ n*(n+1)/2 s=s+1 z

End For z End For n*(n+1)/2

End For n---------------------------

Contador de frecuencias: 3 + 4n + (3/2)n*(n+1) + 3z

Donde z = , desarrollando se obtiene:n

w(w+1)/2w=1

n n n

w(w+1)/2 = ½ w2 + ½ w w=1 w=1 w=1

Y como:

Al simplificar se obtiene:z=(n3 + 3n2 + 2n) /6

Por lo tanto el contador de frecuencias es un polinomio de grado 3, entonces el algoritmo es O(n3)

n w2 = n(n+1)(2n+1)/6w=1

n w = n(n+1)/2w=1

y

void ejemplo(int *T, int n){ contador

int k=0; 1for(int i=0; i<n; i++) n+1{

for(int j=0; j<T[i]; j++) s+n{

k=k+T[j]; s} s

} n} -----------------Contador de frecuencias: 3n + 3s + 2 Orden: O(n+s) O(Max(n,s))¿Qué es s?