AnalisisDeAlgoritmos

Estructuras De Datos y
Algoritmos I
Análisis de Algoritmos
Docente:
Oscar Hernando Arenas Arenas

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
Orden de magnitud:
Esel concepto que define la eficiencia del
algoritmo en cuanto a tiempo de ejecución.

Algoritmo 1
lea(a, b, c)
x=a+b
y=a+c
z=b*c
w=x/y-z
escriba(a, b, c, w)

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

Algoritmo 2
lea(n)
s=0
i=1
mientras i<=n
s=s+1
i=i+1
fin_mientras
escriba(n, s)
Contador de frecuencias

1
1
1
n+1
n
n
n
1
------------4n + 5

Algoritmo 3
lea(n,m)
s=0
i=1
mientrasi<=n
t=0
j=1
mientras j<=m
t=t+1
j=j+1
fin_mientras
s=s+t
i=i+1

fin_mientras
escriba(n, m, s)
Contador de frecuencias:

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

n
1
----------------4(n*m) + 7n + 5

Algoritmo 4
Lea(n)
s=0
i=1
mientras i<=n
t=0
j=1
mientras j<= n
t=t+1
n +j=j+1
fin_mientras
s=s+t
i=i+1

fin_mientras
Escriba(n, s)
Contador de frecuencias:

1
1
1
n+1
n
n
n²+n
n²
n²
n²
n
n

n
1----------------4n² + 7n + 5

Algoritmo 5
lea(n, m )
s=0
i=1
mientras i<=n

1
1
1
n+1

s=s+1
i=i+1

n
n

fin_mientras
escriba(n, s)
s=0
i=1
mientras i<=m
t=t+1
i=i+1

Fin_mientras
escriba(n, s)
Contador de frecuencias:

n
1
1
1
m+1
m
m

m
1
----------------4n + 4m + 9 = 4(n + m) + 9

Conceptos Básicos (Cont.)
Orden de Magnitud:
• Indica como crece el tiempo de ejecución de
un algoritmo cuando crece eltamañ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.

Calculo del Orden de Magnitud
El orden de magnitud 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 deté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

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

ORDEN DE MAGNITUD
Constante
Logarítmico
Lineal
Semilogarítmico
Cuadrático
Cúbico
Exponencial

REPRESENTACIÓN
O(1)
n)
O(
O(n)
O(n
n)
n²
n³
2

Orden de magnitudde los anteriores
algoritmos
Algoritmo
1
2
3
4
5

Orden
O(1)
O(n)
O(n*m)
O(n²)
O(n+m)

Suma de los n primeros
números enteros positivos
Algoritmo a:
lea(n)
s=1
suma=0
mientras s<=n
suma=suma + s
s=s+1
fin_mientras
escriba(suma)

Algoritmo b:
leer(n)
suma=n*(n+1)/2
escriba(suma)

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

Eficiencia búsqueda lineal en arreglo
ordenado

Mejorcaso: Buscar el número 2
Peor caso: Buscar un número que no esta en el arreglo

Orden del método búsqueda lineal
public static int busquedaLineal(int[] datos, int k) {
int i = 0;
int n = datos.length;
int posicion = -1;
while (i < n && datos[i] != k) {
i++;
}
if (i < n) {
posicion = i;
}
return posicion;
}

1
1
1
n+1
n
n
1
1

1
______________
3n + 7 → O(n)

Búsqueda Binaria

Cantidad de veces quese divide n para
llegar a 1

2

= 1 → 2 = → =

Orden del método Búsqueda Binaria
public static boolean binarySearch(int[] data, int target) {
int bottom = 0;
int top = data.length - 1;
while (bottom <= top) {
int midpoint = (top + bottom) / 2;

1
1
n+1
n

if (target < data[midpoint]) {
top = midpoint - 1;
} else if (target == data[midpoint]) {
return true;
} else {
bottom = midpoint + 1;
}

nn

}
return false;

n
1

}
____________
5

n + 4 → O(

n)

Algoritmo 6
lea(n)
s=0
i=n
mientras i>=1
s=s+1
i=i/2
fin_mientras
escriba(n, s)
Contador de frecuencias:

1
1
1
n+1
n
n
n
1
---------------4
n + 5 → O(

n)

Algoritmo 7
lea(n)
s=0
para i=1 hasta n
t=0
para j=1 hasta i
t=t+1
fin_para
s=s+t

fin_para
escriba(n, s)
Contador de frecuencias:

1
1
n+1
n
n*(n+1)/2 + n
n*(n+1)/2
n*(n+1)/2
n...