PDF de programación - Análisis de Algoritmos

Parte de Algoritmos

de la asignatura de Programación

Master de Bioinformática

Análisis de Algoritmos

Web asignatura: http://dis.um.es/~domingo/algbio.html
E-mail profesor: [email protected]

Transparencias preparadas a partir de las del curso de
Algoritmos y Estructuras de Datos II, del Grado de Ingeniería Informática

BIBLIOGRAFÍA

• Texto guía de Algoritmos y Estructuras de Datos, volumen 2

• Brassard, Bratley: Fundamentos de algoritmos.

• Cormen, Leiserson, Rivest: Introduction to Algorithms. The
MIT Press. 1990.

ALGORÍTMICA o

ALGORITMIA

• Estudia:

› Diseño de algoritmos: esquemas para resolver problemas.
Divide y vencerás, avance rápido, programación dinámica,
Backtracking, Branch & Bound...

› Análisis de algoritmos: recursos necesarios para resolver el
problema con el algoritmo elegido. Ocupación de memoria,
tiempo de ejecución.
De manera que se pueda decidir qué algoritmo es mejor para
nuestro problema y entrada.


ALGORITMO

• Conjunto de reglas para resolver un problema. Propiedades:

› Definibilidad. El conjunto debe estar bien definido, sin
dejar dudas en su interpretación.
› Finitud. Tener número finito de pasos, que se ejecute en
un tiempo finito.
› Eficiencia. Debemos diseñar algoritmos eficientes: que el
tiempo para acabar sea “razonable” (análisis de algoritmos).
› Determinista si para la misma entrada produce siempre la
misma salida. No determinista en caso contrario (redondeos,
probabilistas, paralelos…)

PROGRAMACIÓN

• Los algoritmos no son los únicos componentes en la
resolución de un problema:

Algoritmos + Estructuras de Datos = Programas

› Estructura de datos: parte estática,
almacenada
› Algoritmo: parte dinámica, manipulador de
los datos

PROCESO DE

PROGRAMACIÓN

modelado

Problema
real

Estructura de
datos
Modelo
matemático
Algoritmo
en lenguaje
natural

algorítmica

programación

Tipo
abstracto de
datos
Programa en
seudolenguaje

Estructura
de datos
Programa
ejecutable

Estudio de algoritmos

• Se trata de diseñar algoritmos eficientes: que usan pocos
recursos:

tiempo de ejecución

› memoria principal
›
› otros (memoria secundaria, entradas/salidas, tiempo de
programación, comunicaciones, procesadores…)

• Para decidir:

qué algoritmo programar
qué algoritmo utilizar en resolver un problema para una

›
›
cierta entrada
› detectar fallo en programa que no funciona bien

Tiempo de ejecución

• Se intenta estimar el tiempo de ejecución para un cierto
tamaño de entrada, t(n)
• Se pueden considerar tamaños de entrada distintos:

• Cálculo del factorial de un número n. Aunque es un

único número, el tamaño es el valor n

• Ordenación de n datos. El tamaño puede ser el
número de datos n, aunque el valor que tienen
también influye en el tiempo

• Multiplicación de matrices rectangulares nxm y

mxr. El tamaño viene dado por tres valores: t(n,m,r)
• Multiplicación de matrices con programa paralelo

usando p procesadores. Influye el tamaño del
problema (n,m,r) y el del sistema (p): t(m,n,r,p)

Tiempo de ejecución

• Influyen factores externos al algoritmo:

• Compilador y opciones de compilación
• Máquina
• Programador (uso de registros, gestión de accesos a

memoria…)

• por lo que normalmente se estudia la forma en que crece t(n), y
se utilizan notaciones asintóticas:

, forma exacta en que crece

• W
, cota inferior de la forma en que crece
• O, cota superior de la forma en que crece
• q
• o, forma exacta en que crece afectada de la constante del
término de mayor orden (para comparar algoritmos cuyo
tiempo crece de la misma forma)

Tiempo de ejecución

Pueden estudiarse:

•
Caso más favorable tm(n), tiempo para la entrada de

datos que produce el menor tiempo

Caso más desfavorable tM(n), para la que da el mayor

Tiempo promedio tp(n), media de tiempos de todas

las entradas posibles

Para cada uno de ellos se pueden usar las notaciones

tiempo

asintóticas

Lo mismo para el estudio del uso de memoria

Tiempo de ejecución

• Conteo de instrucciones: Se cuenta el número de

operaciones, o las de un cierto tipo, o cada operación
afectada de un coste diferente

• Todo lo dicho para tiempo de ejecución es válido para

ocupación de memoria: mm(n), mM(n), mp(n) y
notaciones asintóticas
• Se cuenta la máxima cantidad de memoria ocupada
durante la ejecución del programa: memoria mínima
que necesitaremos para poder ejecutarlo

Conteo de instrucciones

Reglas básicas:

Número de instrucciones t(n)  sumar 1 por cada instrucción o

línea de código de ejecución constante.

Tiempo de ejecución t(n)  sumar una constante (c1, c2...) por

cada tipo de instrucción o grupo de instrucciones.

Bucles FOR: Se pueden expresar como un sumatorio, con los

límites del FOR como límites del sumatorio.

nS

i=1

k =

ri =

bS
i=a


k n

rb+1 – ra
r – 1

bS

i=a

k =

k(b-a+1)

nS

i=1

i =

n(n+1)/2

nS

i=1

i2 ≈



i2 di =

n

0

n
(i3)/3 ] =
0

(n3)/3

Ej: Cálculo del factorial


fact(n):

si n=1

devolver 1

en otro caso

devolver (fact(n-1)*n)

• Tamaño de la entrada: n
• Tiempo:
t(n)=t(n-1)+a=t(n-2)+2*a= ... =t(1)+(n-1)*a
• Memoria:
m(n)=m(n-1)+c=m(n-2)+2*c= ... =m(1)+(n-1)*c

Usamos expansión de recurrencia

Ejecutar el programa de cálculo de factorial. Ver las funciones de toma

de tiempo, buscar si hay otras alternativas para la toma de tiempos.

fi
Ej. Números de Fibonacci

Funcion Fib(N: int): int;
if N<0 then
error(‘No válido’)
case N of
0, 1: return N
else
fnm2= 0
fnm1= 1
for i= 2 to N
fn= fnm1 + fnm2
fnm2= fnm1
fnm1= fn
end
return fn
end



Funcion Fib(N: int): int;
if N<0 then
error(‘No válido’)
case N of
0, 1: return N
else
return Fib(N-1)+Fib(N-2)
End

fi Estudiar teóricamente el

coste de tiempo y memoria
de las dos versiones
fi Programarlas y comparar su

tiempo experimentalmente

Ej: Torres de Hanoi

Hanoi(origen,destino,pivote,discos):

moveruno(origen,destino)

si discos=1

en otro caso

Hanoi(origen,pivote,destino,discos-1)
moveruno(origen,destino)
Hanoi(pivote,destino,origen,discos-1)

Ej: Torres de Hanoi

Tamaño del problema: número de discos

Tiempo a estudiar: número de movimientos de discos
t(1)=1
t(n)=2t(n-1)+1, si n>1

caso base de la recurrencia
ecuación de recurrencia

Expandiendo la recurrencia:
t(n) = 2 t(n-1) +1 =
2 (2t(n-2)+1) +1 = 22 t(n-2) +1+2 =
22 (2t(n-3)+1) +1+2 = 23 t(n-3)+1+2+22

….

2n-1 t(1)+1+2+…+ 2n-2 = 2n-1

¿ocupación de memoria?
Normalmente la ocupación de memoria es más simple de estudiar y de menor
orden de complejidad

NOTACIONES ASINTÓTICAS
• Se utilizan para estudiar tiempos de ejecución u ocupaciones
de memoria.

• Representan la forma en que crece una función.

• En general no consideran constantes, que no son valores
propios de los algoritmos.

• Son asintóticas pues representan el comportamiento cuando
el tamaño de la entrada tiende a infinito, pues para valores
grandes es cuando puede haber problemas de tiempo o
memoria.

NOTACIÓN O

• Da una cota superior de la forma en que crece el tiempo de
ejecución. Pero es aplicable a cualquier función, no solo de
tiempos de ejecución

• DEFINICIÓN:
Dada una función f:N→R+, llamamos orden de f al conjunto
de todas las funciones de N en R+ acotadas superiormente por
un múltiplo real positivo de f para valores de n
suficientemente grandes.
Se denota O(f), y será:

O(f)={t: N→R+ / $ c˛ R+, $ n0

˛ N, " n>=n0 : t(n)<=cf(n)}

Es un conjunto de funciones, no una función

NOTACIÓN Ω

• Da una cota inferior de la forma en que crece el tiempo
de ejecución.

• DEFINICIÓN:
Dada una función f:N→R+, llamamos omega de f al
conjunto de todas las funciones de N en R+ acotadas
inferiormente por un múltiplo real positivo de f para
valores de n suficientemente grandes.
Se denota Ω(f), y será:

Ω(f)={t: N→R+ / $ c˛ R+, $ n0

˛ N, " n>=n0 : t(n)>=cf(n)}

NOTACIÓN q (orden exacto)

• Da la forma en que crece el tiempo de ejecución.

• Son las funciones a las que f acota superior e inferiormente:
q (f)= Ω(f)˙ O(f)
Es equivalente a:
q (f)={t: N→R+ / $ c,d˛ R+, $ n0

˛ N, " n>=n0 : cf(n)<=t(n)<=df(n)}

• No hay relaciones de inclusión.

• Si t˛ O(f) y t˛W

(f) entonces t˛q

(f)

NOTACIÓN o (o pequeña)
• Se utiliza para comparar tiempos con el mismo orden.
Considera la constante que afecta al término de mayor orden.

• Aparecen constantes, por lo que es necesario hacer
suposiciones sobre: coste de las operaciones, conteo de
instrucciones, …

• Se define: o(f)={t: N→R+ / limn→¥ t(n)/f(n)=1}

• No hay relaciones de inclusión.

COMPARACIÓN DE ÓRDENES



• limn→¥ f(n)/g(n)˛ R+ O(f)=O(g), Ω(f)=Ω(g),

q (f)=q (g)

• limn→¥ f(n)/g(n)=0 O(f)˝ O(g), Ω(g) ˝ Ω(f)

• limn→¥ f(n)/g(n)=+¥ O(g)˝ O(f), Ω(f)˝ Ω(g)

COMPARACIÓN DE ÓRDENES



O(1) O(log n) O(n1/2) O(n) O(n log n)
O(n log n log n) O(n2) O(n3) O(2n) O(n!)

O(nn)

O((log n)p) O(n1/q)

• Con Ω cambia el sentido de las inclusiones

Ecuaciones de recurrencia

• Es normal que un algoritmo se base en procedimientos auxiliares,

haga llamadas recursivas para tamaños menores o reduzca el
tamaño del problema progresivamente.

• En el análisis, el tiempo T(n) se expresa en función del tiempo

para T(n-1), T(n-2)...fi

Ecuaciones de recurrencia.

• Ejemplo. Torres de Hanoi

Hanoi (origen,pivote,destino,discos)

si discos=1

mover(origen,destino)

en otro caso

Hanoi (origen,destino,pivote,discos-1)
mover (origen,destino)
Hanoi (pivote,origen,destino,discos-1)



Ecuaciones de recurrencia

• En general, las ecuaciones de recurrencia tienen la forma:

t(n) = b
t(n) = f (t(n), t(n-1), ..., t(n-k), n)

Para 0 £ n £ n0 Casos base

En otro caso

• Tipos de ecuaciones de recurrencia:

Lineales homegéneas:

a0t(n) + a1t(n-1) + ... + akt(n-k) = 0

Line