Introducción al análisis de algoritmos
-
Upload
germane-meyer -
Category
Documents
-
view
37 -
download
13
description
Transcript of Introducción al análisis de algoritmos
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?