Las matemticas como
medio para medir la
eficiencia de los Algoritmos
Computacionales
Qu es un algoritmo?
(del rabe al-Khowrizm, sobrenombre
del clebre matemtico rabe Mohmed
ben Musa). Conjunto ordenado y finito de
operaciones que permite encontrar la
solucin a un problema
Un algoritmo, puede expresarse en
trminos de un lenguaje de programacin,
para obtener un programa que resuelve el
problema por medio de la computadora.
Cita...
No hay un incremento concebible en el poder de las
computadoras que pueda saturar la demanda cientfica: an
pensando que una computadora posea un ciclo de tiempo
subnuclear (10-23 seg.) y densidades de almacenamiento
subnucleares (1039 bits/cm3), sta no podra manejar la mayora
de los problemas que son importantes en la investigacin
cientfica bsica y aplicada. Por lo tanto, existir siempre una
fuerte presin para incrementar la eficiencia de los programas,
para poder incrementar tambin la cantidad de informacin
ltil generada por un programa.
Ken Wilson, Nbel de Fsica 1982
reas de estudio
Cmo construir algoritmos?
Tcnicas de diseo
Cmo expresar algoritmos?
Enfoques de los lenguajes de programacin
Cmo validar algoritmos?
Verificacin formal
Cmo analizar algoritmos?
Complejidad computacional, eficiencia, legibilidad,
usabilidad, etc...
Anlisis de algoritmos
Si se tuvieran 2 programas que hacen lo
mismo, cmo se podran comparar?
1. Eficiencia:
Tiempo de ejecucin
Uso de espacios de memoria
2. Facilidad de lectura, mantenimiento,
rapidez para codificarlo.
Medicin del tiempo de
ejecucin
El tiempo de ejecucin depende de:
1. La entrada al programa:
Su tamao
Sus caractersticas
2. La calidad del cdigo generado para el
programa por el compilador .
3. La rapidez de las instrucciones de
mquina.
4. La complejidad de tiempo del
algoritmo.
Cmo medir?
Cantidad de instrucciones bsicas (o
elementales) que se ejecutan.
Ejemplos de instrucciones bsicas:
asignacin de escalares
lectura o escritura de escalares
saltos (gotos) implcitos o explcitos.
evaluacin de condiciones
llamada a funciones
etc.
Ejemplo
cont = 1;
while (cont <= n) do {
x = x + a[cont];
x = x + b[cont];
cont = cont + 1;
}
1
n+1
n
n
n
n (goto implcito)
1 goto en falso.
Funcin: 5n + 3
Ejemplo
z = 0;
for (int x=1; x<=n; x++)
for (int y=1; y<=n; y++)
z = z + a[x,y];
1
1 asignacin + (n+1) comparaciones
(n+2)*n = n2 +2n
n*n
= n2
??? (goto implcito)
n (goto en falso for y)
n (goto implcito)
1 (goto en falso for x)
Funcin:
Consecuencia
Se requiere contar con una notacin que permita
comparar la eficiencia entre los algoritmos
La NOTACIN ASINTTICA es la propuesta de notacin
aceptada por la comunidad cientfica para describir el
comportamiento en eficiencia (o complejidad) de un
algoritmo.
Describe en forma sinttica el comportamiento de la
funcin que con la variable de entrada, determina el
nmero de operaciones que realiza el algoritmo.
NOTACIN ASINTTICA
COMPLEJIDAD TEMPORAL (y ESPACIAL).
Tiempo (o espacio) requerido por un algoritmo,
expresado en base a una funcin que depende
del tamao del problema.
COMPLEJIDAD TEMPORAL ASINTTICA (y
ESPACIAL). Comportamiento lmite conforme el
tamao del problema se incrementa. Determina
el tamao del problema que puede ser resuelto
por un algoritmo.
Definicin
Se dice que la funcin f(n) es de orden g(n)
[O(g(n))], si existen constantes positivas c y n0
tales que f(n) <= c g(n) cuando n >= n0
Ejemplos:
n+5 es O(n) pues n+5 <= 2n para toda n >= 5
(n+1)2 es O(n2) pues (n+1)2 <= 4n2 para n>= 1
(n+1)2 NO es O(n) pues para cualquier c > 1
no se cumple que (n+1)2 <= c*n
Ordenes ms comunes de los
algoritmos
O(1)
O(n)
O(n2 )
O(n3 )
O (nm )
O(log(n))
O(nlog(n))
O(mn )
O(n!)
Constante
Lineal
Cuadrtico
Cbico
Polinomial
Logartmico
nlog (n)
exponencial
factorial
Comportamiento
de las funciones
n2
n sqrt(n
n log n
n
log n
Otro mtodo para calcular el orden
de un problema
Consiste en aplicar reglas a los estatutos
estructurados:
[Link] de instrucciones
[Link] (ejemplo: if)
[Link] (ejemplo: while)
[Link]
Regla 1: Secuencia de
instrucciones
O(g
O(g11(n))
(n))
O(g
O(g22(n))
(n))
O( mayor(g1(n), g2(n), , gm(n) )
O(g
O(g33(n))
(n))
Ejemplo:
Una secuencia de 3 ciclos:
O(g
O(gmm(n))
(n))
Tendr como orden total
Ciclo 1 = O(n)
Ciclo 2 = O(log n)
Ciclo 3 = O(n2)
O(n2).
Regla 2: Decisiones
O( mayor(g1(n), g2(n)) )
O(g
O(g11(n))
(n))
O(g
O(g22(n))
(n))
Ejemplo:
Una decisin con:
Rama then = O(n log n)
Rama else = O(log n)
Tendr como orden total
O(n log n).
Regla 3: Ciclos
O( m * g(n) )
O(g(n))
O(g(n))
Se repite
m veces
Ejemplo:
Un ciclo cuya instruccin:
Tiene un O(log n)
Se repite n/2 veces
Tendr como orden total
O( n log n) = O(n log n).
Consideraciones especiales
En decisiones y ciclos anidados:
Analizar el cdigo desde la instruccin ms
interna hacia el ms externa.
Tip para los ciclos:
Normalmente cul es el orden de la
instruccin interna?
Si la variable de control se incrementa o
decrementa con un valor constante: Orden
LINEAL.
Si la variable de control se multiplica o divide por
un valor constante: Orden LOGARTIMICO.
Ejemplo: Sort por intercambio
for (int i=1; i<n; i++)
for (int j=i+1; j<=n;j++)
if (a[ j ] < a[ i ] )
intercambia(a[ i ], a[ j ]); O( 1 )
O( 1 )
Regla 2: Decisiones = mayor de las 2 ramas
Ejemplo: Sort por intercambio
Peor caso: se repite n-1 veces
for (int i=1; i<n; i++)
for (int j=i+1; j<=n;j++)
if (a[ j ] < a[ i ])
O( n )
O( 1 )
intercambia(a[ i ], a[ j ]);
Regla 3: Ciclos = # veces * orden de la instruccin interna
Ejemplo: Sort por intercambio
Se repite n-1 veces
for (int i=1; i<n; i++)
for (int j=i+1; j<=n;j++)
if (a[ j ] < a[ i ] )
O( n )
intercambia(a[ i ], a[ j ]);
O( n2 )
Regla 3: Ciclos = # veces * orden de la instruccin interna
Ejemplo: Multiplicacin de
matrices
a11 a12 a1n
a21 a22 a2n
b11 b12 b1m
b21 b22 b2m
am1 am2 amn
c11 c12 c1m
c21 c22 c2m
cm1 cm2 cmm
bn1 bn2 bnm
c11 = a11*b11+a12 *b21 ++ a1n *bn1
c12 = a11*b12+a12 *b22 ++ a1n *bn2
c21 = a21*b11+a22 *b21 ++ a2n *bn1
cmm = am1*b1m+am2 *b2m ++ amn *bnm
cij =
aikbkj
k=1
Ejemplo: Multiplicacin de
matrices
O( n3 ) for i = 1 to n do
O( n2 ) for j = 1 to n do
O( 1 ) C[i,j] = 0;
O( n ) for k = 1 to n do
O( 1 ) C[i,j] = C[i,j] +
A[i,k]*B[k,j];
Regla 4: Recursividad
La complejidad de tiempo se obtiene contando la cantidad
de veces que se hace la llamada recursiva.
Casos que normalmente se dan:
Orden LINEAL si slo se tiene una llamada recursiva,
con incrementos o decrementos en el parmetro de
control.
Orden LOGARITMICO si slo se tiene una llamada
recursiva, con multiplicaciones o divisiones en el
parmetro de control.
Si hay ms de una llamada recursiva, el orden puede
tender a ser EXPONENCIAL.
Ejemplo: Fibonacci (Iterativo)
ant = 1;
--> 1
act = 1;
--> 1
while (n>2){ --> n-2 + 1
aux = ant + act;
--> n-2
ant = act;
--> n-2
act = aux;
--> n-2
n = n - 1;
--> n-2
}
--> n-2+1
write (act);
--> 1
T(n) = 6n-7
Por lo tanto el orden
del algoritmo es
O(n)
Ejemplo: Fibonacci (recursivo)
Function fibonacci (n:int): int;
if (n < 3) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
Cmo obtener la complejidad de tiempo
del algoritmo?
Cantidad de llamadas recursivas: 2 en
cada llamada.
Algoritmo de orden: O(2n/2)
Anlisis de Fibonacci
(recursivo)
f(5)
f(3)
f(1)
f(4)
f(2)
f(2)
f(3)
f(1)
Relacin:
El trmino T(n) requiere
T(n-1)+T(n-2)+1 trminos
para calcularse.
f(2)
Cuntos trminos
se requieren para
calcular:
f(5)?--> 9
f(4)?--> 5
f(3)?--> 3
--> 1
f(2)?
--> 15
f(6)?
Anlisis de Fibonacci
Si el trmino T(n) requiere T(n-1)+T(n
2)+1 trminos para calcularse
se puede decir que T(n) > 2 * T(n-2)
y por lo tanto: T(n) > 2 * 2 * T(n-4)
Por lo tanto:
y T(n) > 2 * 2 * 2 * T(n-6)
T(n) > 2n/2
y as sucesivamente hasta:
y podemos decir
que el orden del
T(n) > 2 * 2 * 2 * . * 2 * T(1)
algoritmo es
n/2
n/2 veces
O(2 )
