UAM _ Grado en Ingeniería Informática _ Analisis de Algoritmos _ ANALISIS D

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

2011_Tema_3_Algoritmos_de_Busqueda.pdf
Tema 3: Algoritmos 
de Búsqueda
3.1 Algoritmos básicos de 
búsqueda
Resultados conocidos
 Búsqueda lineal


 Búsqueda binaria

 Tenemos que calcular 
N
N
N
i
BLin
e
C
S
iTkpiTknNA
BLin

1
])[(])[()(
cdc OBcon )( NNW
BLin

)()1()lg()lg()( NAONNNW fBBinBBin 
)(NAeBBin
3
Coste medio de BBin con éxito.
 Veamos un ejemplo:
T=[1 2 3 4 5 6 7] N=7=23-1
 Para N=2k-1 se tiene 
)3333221(
7
1
])[(
7
1
)(
7
1
 
i
BBin
e iTknNA
BBin
4 2 6 1 3 5 7
)2·32·22·1(
7
1
)4·32·21(
7
1
)( 210  NAe
BBin
 

]1)lg([
1
)(]122[
1
2
1
)(
1
NNN
N
NAk
N
i
N
NA ekk
k
i
ie
BBinBBin
Obs: N=2k-1klog(N)
)()lg()(
1
1)lg()( NONNA
N
NNA ee
BBinBBin

4
Árbol de decisión para algoritmos de 
búsqueda por CDC: Definición
 Si A es un algoritmo de búsqueda por comparación de 
clave y N es un tamaño de tabla, se puede construir su 
árbol de decisión TA
N para N tal que cumple las 
siguientes 5 condiciones:
1. Contiene nodos de la forma i que indica la cdc entre el 
elemento i-ésimo de la tabla y la clave k. 
2. Si k coincide con el elemento i-ésimo (T[i]==k) entonces la 
búsqueda de la clave k termina en el modo i
3. El subárbol izquierdo del nodo i en TA
N contiene el trabajo 
(cdcs) que realiza el algoritmo A si k < i.
4. El subárbol derecho del nodo i en TA
N contiene el trabajo (cdcs) 
que realiza el algoritmo A si k > i.
5. Las hojas H en TA
N recogen la evolución de las búsquedas 
fallidas.
5
Árbol de decisión: Ejemplos
5
BBinT
3
41
2 5F F
F F F F
<
<
< <
< >
>
>>
>
=
=
==
=
3
BLordT
1
2
3F
F
F F
<
<
< >
>
>
=
=
=
Tabla ordenada
3
BLT
3
4
5
F F
<
<
< >
>
>
=
=
=
5
F F
< >=
4
5
F F
<
< >
>
=
=
5
F F
< >=
Tabla no ordenada
Obs: TA
N es un árbol binario con al menos N nodos internos. Esto da la cota inferior:
WA(N)≥profmin(N)
Profundidad mínima de un
árbol con al menos N nodos internos
6
Árbol de decisión: Cotas inf. Caso Peor
 Estimamos profmin(N)
N T Profmin(N)
1 1
2 2
3 2
4 3
7 3
7
Cotas inferiores en búsqueda por cdcs
 Tenemos que
WA(N)≥profmin(N) =lg(N)+1
WA(N)=(lg(N))  AB con 
B={A: algoritmo de búsqueda por cdc}
 BBin es óptimo para el caso peor. 
 Se puede demostrar también
AA(N)=(lg(N))  AB
 BBin es óptimo para el caso medio.
8
¿Ya hemos acabado?
 Observación: la búsqueda no es una 
operación aislada
 Los elementos no sólo se buscan sino que 
también se insertan o se borran
 No sólo importa cómo se busca sino también 
dónde se busca
 Contexto: TAD Diccionario
9
En esta sección hemos …
 Recordado los costes peor y medio de 
búsqueda lineal y binaria
 Aprendido el concepto de árbol de 
decisión en búsqueda por cdcs
 Aprendido a construir árboles de decisión 
en búsqueda por cdcs
 Visto que la búsqueda binaria es óptima 
en los casos peor y medio dentro de los 
algoritmos de búsqueda por cdcs
10
3.2 Búsqueda sobre 
diccionarios
TAD Diccionario
 Diccionario: conjunto ordenado de datos con 
las primitivas. 
 pos Buscar(clave k, dicc D) 
 Devuelve la posición de la clave k en el diccionario D o un 
código de error ERR si k no está en D.
 status Insertar (clave k, dicc D) 
 Inserta la clave k en el diccionario D, devuelve OK o ERR si 
k no se pudo incorporar a D.
 void Borrar (clave k, dicc D) 
 Elimina la clave k en el diccionario D
12
EdEs para Diccionarios I
 ¿Qué EdE es la más adecuada para un 
diccionario?
 Opción 1: Tabla ordenada (|D|=N)
 Buscar: Usamos BBin => nBuscar(k,D)=O(log(N)) => óptimo.
 Insertar: Hay que mantener la tabla ordenada => la 
inserción es costosa
 Ejemplo:
 Si se inserta en la posición 1, hay que desplazar N 
elementos 
 En el caso medio se desplazan N/2 elementos
 Por tanto nInsertar(k,D)=(N): malo!!
24 25 27 29
Insertar 26
Hay que desplazar a la
derecha estos elementos
13
EdEs para Diccionarios II
 Opción 2: Árbol binario de búsqueda (ABdB)
 Definición: Un ABdB es un árbol binario T que para 
todo nodo T’T se cumple:
Info(T’’)<Info(T’)<Info(T’’’)
para cualquier nodo T’’ a la izq de T’ y T’’’ a la derecha 
de T’
 Es decir, todos los nodos a la izquierda de T’ tienen un 
valor menor que info(T’) y todos los nodos a la derecha 
de T’ tienen un valor mayor que info(T’)
Ejemplo:
5
2 7
1 4 6 9
8 11 14
Buscar sobre ABdBs I
 Ejemplo
5
2 7
1 4 6 9
8 11
B(k=8)
8>5
8>7
8<9
k==8
15
Buscar sobre ABdBs II
 Pseudocódigo:
 Observación:
AB Buscar (clave k, AB T)
si T==NULL : return NULL;
si info(T)==k : return T;
si k<info(T) :
return Buscar(k,izq(T));
si k>info(T) :
return Buscar(k,der(T));
nBuscar(k,T)=prof(T)
16
Insertar en ABDBs I
 Ejemplo
5
2 7
1 4 6 9
8 11
I(k=3)
3<5
3>2
NULL
3<4
BuscarUltimo
5
2
7
1 4 6 9
8 11
3
Último, 3<4 y izq(4)==NULL
izq(4)==3
17
Insertar en ABDBs II
 Pseudocódigo
 Observación
status Insertar (clave k, AB T)
T’=BuscarUltimo(k,T);
T’’=GetNodo();
si T’’==NULL : return ERR;
info(T’’)=k;
si k<info(T’) :
izq(T’)=T’’
else :
der(T’)=T’’;
return OK; 
AB BuscarUltimo(clave k, AB T)
si k == info(T): return NULL;
si (k<info(T) y izq(T) ==NULL) o
(k>info(T) y der(T) ==NULL):
return T; 
si k<info(T) y izq(T) !=NULL :
return BuscarUltimo(k,izq(T));
si k>info(T) y der(T) !=NULL :
return BuscarUltimo(k,der(T));
return T ;
nInsertar(k,T)=nBuscarUltimo(k,T)+1 nInsertar(k,T)=O(prof(T))
18
Borrar en ABdBs
 Pseudocódigo:
void Borrar (clave k, AB T)
T’=Buscar(k,T);
si T’!=NULL :
EliminaryReajustar(T’,T);
 En EliminaryReajustar hay tres posibles 
casos, dependiendo del número de hijos que 
tenga el nodo T’ a eliminar
19
Eliminar y Reajustar I
 Caso 1: El nodo a eliminar no tiene hijos
 se libera el nodo T’ (free(T’)), y 
 el puntero del padre de T’ que apuntaba a T’ se 
reasigna a NULL.
 Coste EliminaryReajustar = O(1)
T
T’
NULL NULL
T
NULL
EliminaryReajustar(T’)
20
Eliminar y Reajustar II
 Caso 2: El nodo a eliminar tiene sólo un hijo
 el puntero del padre de T’ que apuntaba a T’ se 
hace apuntar al único hijo de T’ y
 se libera T’
 Coste EliminaryReajustar = O(1)
T
T’
NULL
T
EliminaryReajustar(T’)
T’’
T’’
21
Eliminar y Reajustar III
 Caso 3: El nodo a eliminar tiene dos hijos
 T’ se sustituye por el nodo que contiene al sucesor 
(el elemento siguiente en la tabla ordenada), y 
 se elimina el nodo T’ según el caso 1 o 2. 
 Coste EliminaryReajustar ≤ prof(T)
T
T’
T’’’ T’’
T’Sucesor’
T’’’’
T
T’
T’’’ T’’
T’Sucesor’
T’’’’
T
T’’’’
T’’’ T’’
T’Sucesor’
22
Eliminar y Reajustar III
 Ejemplo
17
5
3
1 4
14
11 15
6 12
7
Sucesor
B(5) 17
6
3
1 4
14
11 15
5 12
7
17
6
3
1 4
14
11 15
12
7
Caso 1
23
Búsqueda del Sucesor
 Pseudocódigo
AB BuscarSucesor(AB T’)
T’’=der(T’);
mientras izq(T’’)!=NULL :
T’’=izq(T’’);
return T’’ ;
 Obs: Si k’ es el sucesor en un ABdB de k, 
entonces izq(k’)==NULL:
 Si izq(k’)==k’’ se tendria que k’’<k’
 Pero k’’>k, pues k’’ está a la derecha de k
 Luego se tiene que k<k’’<k’ y 
 Por tanto, k’ no puede ser el sucesor de k.
24
Primitivas de diccionarios con TAD ABdB
 nEyR(T’,T)=nBuscarSucesor+nReajustarPunteros= 
O(prof(T))+O(1)
 Por tanto 
nBorrar(k,T)=O(prof(T))+ O(prof(T))= O(prof(T))
 ABdB es eficaz siempre que prof(T)= (lg(N))
 Pero WBuscar(N)=N: ¡¡malo!!
Buscar EyR
1
2
3
N
25
Coste medio de búsqueda en ABdBs I
 AeBuscar(N)= coste medio de (1) la búsqueda de 
todos los elementos (2) para todos los T
  
 
)),((
1
!
1
)(
!
1
)(
1


  Tin
NN
TA
N
NA
NN
N
i
Buscar
e
Buscar
e
Buscar
   
  
]))((
1
1[
!
1
]1))(([
1
!
1
11 NN
N
i
N
i
iprof
NN
iprof
NN 









 
 N
Tn
NN
Crear

 )(
!
11
1
)(
1
1)( NA
N
NA eCrear
e
Buscar Por tanto
26
Coste medio de búsqueda en ABdBs II
 Vemos a un pseudocódigo
alternativo 
para Crear
AB Crear (tabla )
T=IniAB();
InsAB((1),T);
Repartir(, i, d);
Ti=Crear(i);
Td=Crear(d);
izq(T)=Ti;
der(T)=Td;
return T;
=[3 5 2 6 4 1]
Crear
3
[2 1] [5 6 4]
Caso similar a QS:
nC ()=N-1+ nC(i)+ nC(d)
  ))(log()()log(2
1
1)(
1
1)( NNONN
N
NA
N
NA eCrear
e
Buscar 
Por tanto:
)()log(2)( NONNNACrear 
27
Resumen de primitivas sobre ABdBs
 Si B es algoritmo de Búsqueda por cdc
WB(N)=(N)
 Si la EdD es un ABdB las primitivas son 
eficaces en promedio
 Si aseguramos que para todo N se tiene un 
ABdB tal que 
prof(T)=(lg(N)), 
tendriamos que
WBuscar(N)= (lg(N))
28
En esta sección hemos …
 Introducido el concepto de diccionario y 
sus primitivas
 Estudiado su implementación sobre 
ABdBs
 Comprobado que su coste viene 
determinado por la profundidad del ABdB
 Comprobado que dicha implementación 
es óptima en el caso medio
 Comprobado que en el caso peor dicha 
implementación tiene un coste (lg(N))
29
 La construcción y uso de Árboles Binarios 
de Búsqueda
 Eliminación de nodos en ABdBs
 Problemas a resolver (al menos)
110, 112, 114, 115
Herramientas y técnicas a trabajar
3.3 Árboles AVL
Árboles AVL (Adelson-Velskii-Landis)
 Definición: El factor de equilibrio de un 
nodo T en un ABdB se define
FE(T)=prof(Ti)-prof(Td)
 Ejemplo:
0
0
0
0 0
0
0-2=-2
4-3=1
3-1=2
0
2-0=2
 Definición: Un AVL T es un ABdB tal que 
 subárbol T’de T se verifica
FE(T’)={-1,0,1}
32
Construcción de AVLs
 Para construir un AVL se procede en 2 
pasos.
 Paso 1: Se realiza la inserción normal de un 
nodo en un ABdB
 Paso 2: Si es necesario se corrigen 
desequilibrios y una vez corregidos, se vuelve al 
paso 1
Ejemplo: T=[1 2 3 4 5 6 7 15 14 13 12 11 10 9 8]
I(1)+I(2) 1
-1
2
0
I(3)
1
-2
2
-1
3
0
RI(2)
1
0
2
0
3
0
33
Construcción de AVLs
 La operación que acabamos de hacer se 
denomina Rotación a la Izquierda en el -1, en 
este caso en el elemento 2.
 En realidad la rotación a la izquierda en el -1 
corresponde a la siguiente reasignación de 
punteros
x1
x2
x3
T1
T2
T4T3
RI(x2)
x1
x2
x3
T1 T2 T4T3
y
y
tmp=izq(x2),
izq(x2)=x1, der(x1)=tmp,
izq(y)= x2 o bien der(y)= x2 
34
Construcción de AVLs
 Seguimos el proceso
1
0
2
0
3
0
I(4)
1
0
2
-1
3
-1
4
0
I(5)
1
0
2
-2
3
-2
4
-1
5
0
RI(4)
1
0
2
-1
3
0
4
0
5
0
1
0
2
-2
3
0
4
-1
5
-1
6
0
I(5)
RI(4)
1
0
2
0
3
0
4
0
5
-1
6
0
35
1
0
2
0
3
0
4
0
5
-1
6
0
I(7)
1
0
2
0
3
0
4
-1
5
-2
6
-1
7
0
RI(6)
1
0
2 0
3
0
4
0
6
0
7
0
5
0
I(15)+I(14)
1
0
2 0
3
0
4
-2
6
-2
7
-2
5
0
15
1
14 0
RD(14)
1
0
2
0
3
0
6
-2
7
-2
5
0
15
0
14 -1
RI(14)
1
0
2 0
3
0
6
-1
7
0
5
0
15
0
14 0
4
-2
4
-1
RDI(izq(1))=RDI(14)
I(13)
36
1
0
2 0
3
0
6
-2
7
-1
5
0
15
0
14 1
4
-2
RD(7)
13
0
1
0
2
0
3
0
6
-2
7
-2
5
0
15
0
14
0
4
-2
RI(7)
13
0
1
0
2
0
3
0
7
5
0
1
15
0
14
0
4
-1
I(12)
13
0
6
0
RDI(7)
1
0
2
0
3
0
7
5
0
1
15
0
14
1
4
-2
RI(7)
13
1
6
-1
12
0
1
0
2
0
3
0
7
5
0
1
15
0
14
1
4
0
13
16
0
12
0
I(11)
37
1
0
2
0
3
0
7
5
0
1
15
0
14
1
4
0
13
16
0
12
0
RD(12)
1
0
2
0
3
0
7
5
0
1
15
0
14
2
4
0
13
26
-1
12
1
11
0
I(11)
1
0
2
0
3
0
7
5
0
1
15
0
14
1
4
0
12
06
0
11
0
13
0
I(10)
1
0
2
0
3
0
7
5
0
1
15
0
14
2
4
0
12
16
-1
11
1
13
0
10
0
RD(12)
38
1
0
2
0
3
0
7
5
0
1
15
0
14
0
4
0
12
0
6
0
11
1
13
0
10
0
I(9)
1
0
2
0
3
0
7
5
0
1
15
0
14
0
4
0
12
1
6
-1
11
2
13
0
10
1
9
0
RD(10)
1
0
2
0
3
0
7
5
0
1
15
0
14 0
4
0
12
0
6
0
10 0
13
0
9
0
11
0
1
0
2
0
3
0
7
5
0
1
15
0
14 0
4
0
12
1
6
-1
10 1
13
0
9
1
11
0
I(8)
8
0
Hemos construido el AVL
39
Resumen de rotaciones
Tipo de 
desequilibrio
Rotación
(-2,-1) Rot Izquierda en -1
(hijo izq de -1 pasa a hijo der de -2)
(2,1) Rot Derecha en 1
(hijo der de 1 pasa a hijo izq de 2)
(-2,1) Rot Derecha Izquierda en izquierda de 1
RotIzq(izq(1))+ RotDer(izq(1))
(2,-1) Rot Izquierda Derecha en derecha en -1
RotDer(der(-1))+ RotIzq(der(-1))
40
Funcionamiento de las rotaciones
 Para ver que efectivamente las rotaciones solucionan 
los desequilibrios es necesario ver cada uno de los 
casos.
x
y
1
2
T1 T2
T3
p p-1
p-1
prof =p+1
RD(y) x
y
0
0
T1
T2 T3
p
p-1 p-1
prof =p
(2,1)→RD(1)
x
y
-1
2
T1
T3
T4
p
p RID(z)
(2,-1)→RID(der(-1))
z
T2
p p
p p-1
p-1 p3 posibles
casos
z
y
T1 T4T2
p
x
T3
p
p p
p p-1
p-1 p
0
-1
0
0
0
1
0
-1
1
0
1
-1
41
Funcionamiento de las rotaciones
 Observación: Las rotaciones resuelven desequilibrios 
de tipo  2, situados mas arriba del desequilibrio 
(2, 1)
x
y-1
2
T1
T3
T4
p
p RID(z)
z
T2
p p
p p-1
p-1 p
z
y
T1 T4T2
p
x
T3
p
p p
p p-1
p-1 p
0
-1
0
0
0
1
0
-1
1
0
1
-1
w
2
T5
p+1
prof
p+2
prof
p+3
w
1
T5
p+1
prof
p+2
42
Funcionamiento de las rotaciones
 Observación: Si se tiene un AVL, tras la inserción de 
un elemento no pueden darse desequilibrios de la 
forma (2, 0).
x
y0
2
T1
T3
p
p-1
Con lo cual la situación 
Antes de insertar el nodo era
T2
Supongamos que tras una inserción tenemos
p
El nodo debió insertarse
en uno de estos dos subárboles
x
y
2
T1
T3
p-1
T2
p
p-1
p
p-1
p
p
1
-1
0prof
p+1 prof
p+1
¡ No era AVL !
43
Profundidad de Árboles AVL
 Proposición: Si T es un AVL con N 
nodos entonces
prof(T)=O(log(N))
 Dado que para cualquier árbol binario con 
n nodos se tiene que prof(T)=(log(N)), 
tenemos que si T es AVL entonces
prof(T)=(log(N))
 Para ver lo anterior vamos a estimar el 
número mínimo de nodos np de un AVL 
Tp de profundidad p.
44
AVLs mínimos
p AVL np np+1 Fp+2
0 1 2 F2
1 2 3 F3
2 4 5 F4
3 7 8 F5
4 12 13 F6
… …. ….
45
AVL de Fibonacci I
 Fp es el p-ésimo número de Fibonacci.
 Los números de Fibonacci verifican:
 Fn=Fn-1+Fn-2 , con F0=F1=1
 Los AVL Tp se construyen
 np =1+ np-1+ np-2, por tanto se tiene
1+np =1+ np-1+1+ np-2 
 Por tanto np+1= Hp= Fp+2
Tp
Tp-1 Tp-2
Tp
Tp-2 Tp-1
o bien
Hp Hp-1 Hp-2
Obs: 
H0=1+n0=2=F2, 
H1=1+n0=3=F3
46
AVL de Fibonacci II
 Se puede demostrar que en N-simo número de 
Fibonacci es
 
2
51
y 
2
51
 donde 
5
1 11 

  NNNF

N→ N→
0 ya que >1 y ||<1
 Con lo cual se tiene FN(1/5)
N y como np= Fp+2-
1 obtenemos
donde p es la profundidad y C una constante
 ,
5
3
pp
p Cn 


47
Profundidad de un AVL II
 Entonces si T es un AVL con N nodos y profundidad p, 
se sigue que 
Nnp C
p
 Esto es, se tiene que 
lg(N) p·lg()+lg(C), 
es decir log(N)=(prof(T)), y por lo tanto 
prof(T)=O(lg(N))
 Es decir, el coste de Buscar sobre un AVL es
O(lg(N)) en el caso peor
48
Conclusión
 Si usamos un AVL como EdD para un diccionario, tanto 
Buscar como Insertar tienen un coste O(log(N)) en el 
caso peor.
 ¿Qué ocurre con Borrar?
 No es fácil reajustar los nodos de un AVL después de haber 
eliminado un nodo.
 La solución habitual es realizar un Borrado Perezoso: en lugar 
de eliminar el nodo, se marca como libre, además si el 
elemento se reinserta, la inserción es muy fácil y rápida.
Ejemplo:
 El inconveniente de este método es que se pierden posiciones 
de almacenamiento
1
2
3
4
5
Eliminar (2)
1
3
4
5
49
En esta sección hemos aprendido…
 El concepto de árbol AVL.
 A construir un árbol AVL insertando como en ABdBs
y corrigiendo desequilibrios mediante rotaciones
 A estimar el número mínimo de nodos de un AVL de 
profundidad P
 La relación de lo anterior con los números de 
Fibonacci y algunas propiedades de estos
 Que la profundidad de un AVL con N nodos es 
O(lg(N))
 Que el caso peor de búsqueda en un AVL es 
O(lg(N))
50
 Construcción y propiedades de árboles 
AVL
 Construcción y propiedades de árboles de 
Fibonacci
 Problemas a resolver (al menos)
119, 120, 125, 126
Herramientas y técnicas
a trabajar
3.4 Hashing
Ordenación y búsqueda
Ordenación Búsqueda
Métod. malos O(N2) O(N)
Métod. Buenos O(N lg N) O(lgN)
Límite O(N) O(1)
53
 A grandes rasgos, los costes de 
búsqueda son 1/N veces los de 
ordenación
Ordenación y búsqueda II
 ¿Es posible hacer búsquedas en tiempo 
inferior a O(log(N))?
1. Imposible mediante comparaciones de clave 
2. Pero muy fácil cambiando el punto de vista!!
 Escenario:
1. TAD diccionario con D={datos D}.
2. Cada dato D tiene una clave única k=k(D). 
3. Buscamos por claves pero no mediante 
claves (no cdcs).
Idea 1
1. Calculamos k*=max{k(D): DD}
2. Guardamos cada D en una tabla T de tamaño k* 
(suponiendo que no hay claves repetidas).
Pseudocódigo:
 Consecuencia: nBuscar(k,D)=O(1) !!!
 Problema: si k* es muy grande (aunque |D| sea 
pequeño), la cantidad de memoria necesaria para la 
tabla T es exagerada. 
ind Buscar(dato D, tabla T)
si T[k(D)]==D
return k(D);
else 
devolver NULL 
)
Idea 2
1. Fijamos M > |D| y se define una función inyectiva (si, 
kk’  k(k)  k(k’) ) k : {k(D)/DD}→{1,2,3,….,M}.
2. Situamos el elemento D en la posición k(k(D)) de la 
tabla T. 
3. Pseudocódigo de Buscar :
 Tiempo de búsqueda constate con un consumo de 
memoria no exagerado.
 Problema: muy difícil encontrar una función inyectiva y 
universal (independiente del conjunto de claves).
ind Buscar2(dato D, tabla T)
si T[k(k(D))]==D
return k(k(D));
else 
devolver NULL 
Obs: nBuscar2(k,D)=O(1)
Idea 3
1. Buscamos una función k universal (válida para 
cualquier conjunto de claves).
2. Somos flexibles con la inyectividad de k:
Permitimos que k no sea inyectiva, luego dos 
datos distintos pueden optar a ocupar la misma 
posición en la tabla T, pero 
a) Imponemos que el número de colisiones, esto es, 
pares kk’ pero k(k)=k(k’) sean pocos.
b) Implementamos algún mecanismo de resolución de 
colisiones
1. Cuestiones abiertas:
a) Cómo encontrar una tal h 
b) Cómo resolver colisiones
Funciones hash
 Objetivo: probabilidad pequeña de colisiones
 Si T tiene M datos, lo óptimo sería que
p(colisión)=1/M
 Idea: h(D) = valor al lanzar un dado de M caras 
pero
 Cada vez que aparece D el dado lo puede enviar a 
posiciones distintas!!
 Luego queremos que h(k(D)) siempre valga lo 
mismo para cada k(D) particular.
 Esto es, queremos que h sea función y 
aleatoria
 Como rand() en C
 Q: ¿cómo construir funciones aleatorias?
Hash por división
 Dado un diccionario D fijamos un número 
m>|D|, que sea primo.
 Definimos h(k)=k%m
 Con alguna condición adicional sobre m, se 
puede conseguir que para valores kj
aleatorios, los valores h(kj) también lo 
parezcan
 Esto es, superan diversos tests de aleatoriedad
Hash por multiplicación
 Fijamos un número m>|D|, no necesariamente 
primo (por ejemplo 2k o 10k) y un número 
irracional (p. ej. (1+5)/2 ó (5-1)/2)
 Definimos 
h(k)=m·(k·) , 
con (x) la parte fraccionaria de x: (x)=x- x
 De nuevo se puede conseguir que para valores 
kj aleatorios, los valores h(kj) también lo 
parezcan
 Cuestión pendiente: cómo resolver colisiones.
Función hash uniforme
 Definición: Decimos que una función hash h
es uniforme si
 Las funciones hash uniforme son “ideales”.
1. No se pueden conseguir por medios algorítmicos.
2. Pero el rendimiento para ellas es óptimo.
 Las usaremos en nuestros análisis teóricos
Dados k,k’; kk’ entonces p(h(k)=k(k’))=1/m
Resolución por Encadenamiento
 En el hash por encadenamiento, usamos 
como tabla hash una tabla de punteros 
a listas enlazadas
D
D
Dx Dy 0
k
h(k)
h
Si estamos seguros de que D no
Está en T, introducimos el dato D
al principio de la lista enlazada.
Si primero comprobamos que no 
Está, lo insertamos al final
Buscar en Encadenamiento
 Pseudocódigo: Blin en lista enlazada.
 Coste ya no O(1), pues en BLin hay un bucle
 Además WBLin (N)=N si para todo k, h(k) = h0 
ind Buscar(dato D, tabla T)
return BLin(D,T[h(k(D))]);
···· 0
N
D
D
D
D
Obs: Esta situación puede pasar, pero debería ser muy poco probable si la
función hash está bien construida.
Encadenamiento con hash uniforme I
 Proposición: Sea h función hash uniforme en 
tabla hash con encadenamiento y dimensión m
y sean N los datos a introducir; entonces:
 se denomina el factor de carga: cuanto 
mayor es, tanto más costosa es la búsqueda

m
N
mNAi fBHE ),( )(
)1(
2
1),( )( OmNAii eBHE 

Factor de carga

Coste medio en búsqueda sin éxito
 Demostración (i): Sea D un dato que no esta 
en la tabla hash y sea h(k(D))=h(D)=i, sea 
nBHE(D,T)=|T[i]| (número de elementos en la 
lista enlazada de la posición i de la tabla hash).
 
 m
N
iT
m
iTiDhpmNA
m
i
m
i
h
f
BHE
11
uniforme 
|][|
1
|][|))((),(

···· 0
|T[i]|
i
D
Coste medio en búsqueda con éxito
 Demostración (ii): Vamos a reducir la búsqueda con 
éxito a una búsqueda sin éxito en una tabla más 
pequeña. 
 Para ello numeramos los datos de la tabla T, según el 
orden en el que los introducimos en la tabla T, 
{D1,D2,….,Dj,….,DN}
 Además denotamos por Ti al estado de la tabla T antes
de introducir el elemento Di (la tabla Ti tiene los 
elementos D1,D2,….,Dj-1), 
 Por tanto Di no está en Ti, con lo cual se tiene:

éxitosin búsquedaéxitocon búsqueda
),(1),( mDnmDn i
f
BHEi
e
BHE 
Nota: aquí asumimos que cada elemento Di se inserta al final de la lista enlazada.
Búsqueda con éxito=
1+Búsqueda sin éxito
Coste medio en búsqueda con éxito II
 Asumimos la aproximación
m
i
miAmDn fBHEi
e
BHE
1
1),1(1),(

 Factor de carga
en Ti





 
 


1
111
1
1
1
1
1
),(
1
),(
N
i
N
i
N
i
i
e
BHE
e
BHE i
Nmm
i
N
mDn
N
mNA
entonces
)1(
2
1
2
1
2
1
1
2
)1(1
1 O
mm
NNN
Nm





m
N
mNA fBHE ),(
)1(
2
1),( OmNAeBHE 

Obs: Si la función hash es uniforme se obtienen
búsquedas en tiempo constante si =(1), lo cual
ocurre si Nm. Por ejemplo si N=200 y m=100 
Af200/100=2 Ae 1+2/2=2
Hashing por direccionamiento abierto
 En el hash por direccionamiento abierto la tabla T 
contiene los datos
 ¿Qué hacemos cuando la función hash nos asigna una 
casilla que está ya ocupada (colisión)?
Dx
DY
D k
h(k)
h
Libre
Libre
Libre
Libre
Ocupada
Libre
Ocupada
Dx
D
DY
Libre
Libre
Libre
Libre
Ocupada
Ocupada
Ocupada
T T
Colisiones en direccionamiento abierto
 Hay varios métodos para resolución de colisiones en 
direccionamiento abierto mediante repetición de sondeos
 Sondeos lineales: Si la posición p=T[h(D)] está 
ocupada, se intenta colocar D sucesivamente el las 
posiciones (p+1)%m, (p+2)%m,…., hasta llegar a un i 
donde la posición (d+i)%m está libre.
Dx
Dy
Dz
p=h(k(D))
D
Ocupada
Ocupada
Ocupada
Libre
Dx
Dy
Dz
D
Ocupada
Ocupada
Ocupada
Ocupada
(p+2)%m
(p+1)%m
(p+3)%m
Colisiones en direccionamiento abierto
 Sondeos cuadráticos: Igual que los sondeos 
lineales pero intentando en las posiciones 
p=(p+02)%m, (p+12)%m, (p+22)%m,…., hasta que 
para algún i, (p+i2)%m.
 Sondeos aleatorios: Intentamos las posiciones, 
p1, p2, p3,….,pi obtenidas aleatoriamente
 Este método es inviable en la práctica
 Es una opción “ideal” en tablas hash
 Es adecuada para calcular el rendimiento de las 
búsquedas.
Diferencias en los métodos
 Obs 1: En hash con encadenamiento, la posición de un 
dato D, siempre será una posición fija de la tabla (h(k(D)), 
En hash con direccionamiento abierto, la posición de D 
dependerá h(k(D) y del estado de la tabla en el momento 
de la Inserción.
 Obs 2: En hash con encadenamiento  (=N/m), puede 
ser >1. 
En hash con direccionamiento abierto siempre se tiene 
Nm, y por tanto  1. 
En la práctica se usa N< m y  <1 (por ejemplo m=2*N y 
=.0.5).
Coste medio con sondeos aleatorios I
 Proposición: Sea h función hash uniforme en 
tabla hash con direccionamiento abierto y sondeos 
aleatorios. Entonces:


1
1
),(
)( mNAi fBHE
 

1
1
log
1
),( )( mNAii eBHE
Obs 1:  ),( entonces 1 Si mNA fBHE
Obs 2:  ),( entonces 1 Si mNAeBHE
Nota: Estos dos resultados
se dejan como ejercicio.
Coste medio en búsqueda sin éxito
 Demostración (i): Sea T una tabla hash con DA, de 
dimensión m y N datos. Como h es uniforme se tiene, dado 
un dato D
p(T[h(D)] ocupada) = N/m = 
p(T[h(D)] libre) = 1-
N datos en una
Tabla de tamaño m
 )1(· sondeos)k (·),(
1
1
1







k
k
k
e
BHDA khacerpkmNA 
nº de sondeos hechos k-1 posiciones
ocupadas
1 posición
libre
Para hacer k sondeos
tiene que ocurrir
y
p(hacer k sondeos) =k-1(1-)1


































1
1
)1(
1
)1(
1
1
)1()1( · )1(
2
0
1
1
d
d
d
d
k
k
k
k
k
Coste medio en búsqueda con éxito I
 Proposición (ii):
 

1
1
log
1
),( mNAeBHE
 Demostración: De nuevo vamos a reducir la búsqueda 
con éxito a una búsqueda sin éxito en una tabla más 
pequeña. 
 Al igual que en BHE enumeramos los datos de la tabla 
T, según el orden en el que los introducimos en la tabla 
T, {D1,D2,….,Dj,….,DN}, y denotamos por Ti al estado de 
la tabla T antes de introducir el elemento Di.
Obs: Si es el número de sondeos necesarios para 
encontrar (= al numero necesario para insertar) el 
elemento Di en la tabla Ti tenemos que 
)( i
e
T Dn
),1()()( miADnDn fBHAi
f
Ti
e
T i

Coste medio en búsqueda con éxito II
 Por tanto se tiene:


 




1
011 1
11
1
1
11
)(
1
),(
N
j
N
i
N
i
i
e
T
e
BHA
m
jN
m
iN
Dn
N
mNA
Esta última expresión se puede aproximar mediante una integral, con lo que
se tiene:
du
uu
m
N
dx
m
xN
mNA
mNN
e
BHA  






 0
/
00 1
11
1
11
1
11
),(
Esta integral es inmediata, con lo que se obtiene:
 

1
1
log
1
),( mNAeBHE
Cambio de variable.
u=x/m  dx=m·du
Costes medios para otros sondeos I
 En la demostración anterior vemos que si tenemos la 
expresión del rendimiento de la búsqueda sin éxito
podemos calcular el rendimiento de la búsqueda con 
éxito calculando
 Este argumento lo podemos repetir con cualquier tipo 
de sondeo S con direccionamiento abierto, es decir




1
1
),()( mNAf fBHA
 


 00 1
11
)(
1
),( du
u
duufmNAeBHA




0
)(
1
),( entonces )(),( Si duufmNAfmNA eS
f
S
Costes medios para otros sondeos II
 Proposición: Si se usan sondeos lineales:








2)1(
1
1
2
1
),()(

mNAi fSL














  

1
1
1
2
1
)1(
1
1
2
11
),()(
0 2
dumNAii eSL
En esta sección …
 Hemos aprendido
El Concepto tabla hash.
Los mecanismos de construcción y búsqueda 
en una tabla hash.
El concepto de función hash uniforme
Algunos tipos universales de funciones hash 
(división y multiplicación).
En esta sección ……
 Y también
Los principales métodos de resolución de 
colisiones en una tabla hash: 
encadenamiento y direccionamiento 
abierto
Los principales métodos de sondeo en una 
tabla hash con direccionamiento abierto.
A estimar el rendimiento medio de las 
búsquedas con o sin éxito en el caso de 
sondeos aleatorios.
A reducir el rendimiento medio de las 
búsquedas con éxito al rendimiento de las 
búsquedas sin éxito.
 Funcionamiento y construcción de tablas 
hash
 Diseño de tablas hash que aseguren un 
cierto rendimiento 
 Estimación de costes medios de 
búsquedas con éxito a partir de costes 
medios sin éxito
 Problemas a resolver (al menos)
128, 129, 130, 131, 133, 134, 135, 136
Herramientas y técnicas a trabajar
2013Tema1Intro.pdf
Tema 1: Introducción
J.Dorronsoro, P. Varona, C. Aguirre
1
1.1 Introducción al 
Análisis de Algoritmos
J.Dorronsoro, P. Varona, C. Aguirre
2
Tiempo Abstracto de Ejecución (TAE)
 ¿Qué analizar en un algoritmo?
Corrección.
Uso de memoria.
Rendimiento (tiempo de ejecución).
 ¿Cómo medir el rendimiento?
Mediante un reloj (tiempo puro de ejecución)
 Intuitivo pero problemático …
Analizando el pseudocódigo: tiempo 
abstracto de ejecución (tae)
J.Dorronsoro, P. Varona, C. Aguirre
3
¿Cómo medir el tae?
 Opción 1: Contar el número de sentencias 
básicas (líneas acabadas en ; que no son 
llamadas a función) que ejecuta el algoritmo 
dada una entrada I.
Opción compleja
Depende de cómo se escriba el pseudocódigo
Aporta información innecesaria.
 Esto es, damos un tae de 1 a las sentencias 
básicas
 Pero vamos a ver un ejemplo
J.Dorronsoro, P. Varona, C. Aguirre
4
Cálculo del TAE
Ejemplo. SelectSort (Pseudocódigo)
void SelectSort(Tabla T, ind P, ind U)
i=P;
mientras i<U:
min=i ;
para j de i+1 a U :
si T[j]<T[min] : 
min=j ;
swap(T[i],T[min]) ;
i++;
J.Dorronsoro, P. Varona, C. Aguirre
5
Funcionamiento de SelectSort
 Ejemplo. SelectSort 
 Entrada: T=[4,3,2,1], P=1, U=4. 
Iteración Operaciones Tabla
i=1 min=4
swap(T[1],T[4])
[1,3,2,4]
i=2 min=3
swap(T[2],T[3])
[1,2,3,4]
i=3 min=3
swap(T[3],T[3])
[1,2,3,4]
J.Dorronsoro, P. Varona, C. Aguirre
6
Funcionamiento de SelectSort II
En más detalle:
Entrada: T=[4,3,2,1], P=1, U=4. 
1 3 2 4
1 2 3 4
i=1
1 2 3 4
1 2 3 4
i=2
1 2 3 4
1 2 3 4
i=3
i=4 Fin (i=U)
min =1
j=2 ¿T[2]<T[1]? Si → min=2
j=3 ¿T[3]<T[2]? Si → min=3
j=4 ¿T[4]<T[3]? Si → min=4
min=4, swap(T[1],T[4])
Bucle 2
min =2
j=3 ¿T[3]<T[2]? Si → min=3
j=4 ¿T[4]<T[3]? No → min=3
Bucle 2
min=3, swap(T[2],T[3])
min =3
¿T[4]<T[3]? No → min=3Bucle 2
min=3, swap(T[3],T[3])
4 3 2 1
1 2 3 4
J.Dorronsoro, P. Varona, C. Aguirre
Bucle 1
7
TAE de SelectSort
SelectSort funciona con 2 bucles anidados
void SelectSort(Tabla T, ind P,ind U)
i=P;
mientras i<U:
min=i;
para j de i+1 a U:
si T[j]<T[min] :
min=j;
swap(T[i],T[min]);
i++;
Vamos a intentar calcular su TAE
J.Dorronsoro, P. Varona, C. Aguirre
Bucle 2Bucle 1
8
TAE de SelectSort II
 Cálculo de taeSelectsort(T;P,U):
void SelectSort(Tabla T, ind P,ind U)
i=P;
mientras i<U:
min=i;
para j de i+1 a U:
si T[j]<T[min]:
min=j;
swap(T[i],T[min]);
i++;
Bucle de P a U-1
bucle 1
U-P
iteraciones
J.Dorronsoro, P. Varona, C. Aguirre
bucle 2
U-i
iteraciones
Bucle de i+1 a U
9
Parece que el número de bucles y su 
tamaño determina el tae
TAE de SelectSort III
J.Dorronsoro, P. Varona, C. Aguirre
10
32/52/3
2/)1(3)1(41
2/))(1(3)(41
3)(41))(34(1
)),,(4(1))((1),,(
2
1
1
1
2 
1





 









NN
NNN
PUPUPU
jPUiU
UiTtaeiitertaeUPTtae
U
Pi
PU
j
U
Pi
bucle
U
Pi
SS
Hemos llegado a un tae de la forma f(N)
Pero hay cosas sueltas, sobre todo en los coeficientes
Ejemplo: es el de tae (swap) 1? ó 3?
Observando que N=U-P+1 es el tamaño de T, se tiene
2/)1(
1
1
NNi
PUN
N
i




¿Cómo simplificar y normalizar el TAE?
 Observación: el TAE de SS está dominado por el 
bucle más interno
 Opción 2.
 Definir una operación básica y contar el número de veces 
que la ejecuta el algoritmo A sobre una entrada I (nA(I))
 Tomar como tiempo abstracto de ejecución del algoritmo A, 
para la entrada I el número de operaciones básicas que 
ejecuta A sobre I: taeA(I)= nA(I) .
 Operación básica:
 Se ha de encontrar en el bucle más interno del algoritmo (es la 
operación que más veces se ejecuta).
 Debe ser representativa del algoritmo (pero también de otros 
que resuelven el mismo problema).
J.Dorronsoro, P. Varona, C. Aguirre
11
Vuelta al psc de SelectSort
void SelectSort(Tabla T, ind P, ind U)
i=P;
mientras i<U:
min=i ;
para j de i+1 a U :
si T[j]<T[min] : 
min=j ;
swap(T[i],T[min]) ;
i++;
J.Dorronsoro, P. Varona, C. Aguirre
12
Operación básica de SelectSort
 Operación básica
 Debe estar en el bucle más interno
 Ser “representativa” del algoritmo.
 Un buen candidato a ser OB de SelectSort es la 
operación si T[j]<T[min]; .
 Esta operación se denomina “comparación de claves” 
(CDC).
 Efectivamente, se encuentra en
el bucle mas interno.
 Es representativa de SelectSort y de otros muchos 
algoritmos de ordenación
J.Dorronsoro, P. Varona, C. Aguirre
13
Análisis del rendimiento de SelectSort
 Cálculo de nSelectSort(T,P,U)
void SelectSort(Tabla T, ind P,ind U)
i=P;
mientras i<U:
min=i;
para j de i+1 a U:
si T[j]<T[min]:
min=j;
swap(T[i],T[min]);
i++;






 



1
1
1
1
1
1 1
1
1
2 )(1),,(),1,(
N
j
N
i
N
i
N
ij
N
i
bucleSelectSort jiNNiTnNTn
Bucle de P a U-1
222
)1( NNNN



2
bucle 1
U-P
iteraciones
J.Dorronsoro, P. Varona, C. Aguirre
bucle 2
U-i
iteraciones
Bucle de i+1 a U
14
Ejemplo: Búsqueda Binaria
Búsqueda Binaria
ind BBin(Tabla T, ind P, ind U, clave k)
mientras P≤U :
m=(P+U)/2;
si T[m]==k :
devolver m;
else si k < T[m] :
U=m-1;
else :
P=m+1;
devolver error;
Importante: BBin sólo funciona si la tabla T está ordenada.
J.Dorronsoro, P. Varona, C. Aguirre
15
 En cada iteración o hay retorno o la tabla se reduce
 El tamaño de la tabla es aproximadamente la mitad 
tras cada iteración
 Si se sale del bucle P≤U porque P > U significa que la 
clave buscada k no está en T.
¿Cómo funciona BBin?
P Um m+1m-1
k<T[m] k>T[m]
Si k<T[m]
P UP=m+1U=m-1
Si k>T[m]Si k==m
Devolver m
J.Dorronsoro, P. Varona, C. Aguirre
16
OB para BBin
 Un buen candidato a ser OB es la operación:
si T[m]==k :
…..
else si k < T[m] :
……
else :
……..
 Se trata de nuevo de una operación de 
comparación de clave
 Aunque hay dos sólo la contamos una vez
J.Dorronsoro, P. Varona, C. Aguirre
17
Análisis de rendimiento de BBin
 nBBin(T,P,U,k)= número de iteraciones (P<U) ≤ número de 
veces que se puede dividir un número N entre 2.
 Tras cada iteración el tamaño de la tabla es menor que:
 Ejercicio: Realizar el calculo anterior, contando todas la 
sentencias básicas en lugar de solamente la OB
 Solución: nBBin ≤5 log2N + 2
1
2
.......
22 2
 k
NNNN
k=máximo de divisiones
por 2=número máximo
de iteraciones
  k)N,(T,1,n22 BBin1  Nlog2kN kk
J.Dorronsoro, P. Varona, C. Aguirre
18
Observaciones sobre tae
 Observación 1: Parece que para cualquier 
algoritmo A, a sus entradas I se les puede 
asignar un tamaño de entrada ((I)) y se puede 
encontrar una cierta función de N, fA(N) tal que:
taeA(I)=nA(I) ≤ fA((I))
 En los ejemplos vistos
A I  fA
SelectSort (T,P,U) U-P+1 N2/2-N/2
BBin (T,P,U,k) U-P+1 log2N
J.Dorronsoro, P. Varona, C. Aguirre
19
Observaciones sobre tae
 Observación 2: El tae permite
 Generalizar los tiempos de ejecución en función del tamaño de la 
entrada.
 Estimar tiempos reales de ejecución.
 Ejemplo: SelectSort con I tal que (I)=N e I’ tal que (I’)=2N
 taeSSort(I)= N2/2+…, taeSSort(I’)= (2N)2/2+…=4N2/2+… ~ 4taeSSort(I)
 En general si (I’)=kN se tiene taeSSort(I’) ~k2taeSSort(I)
 Supongamos que una tabla con N=1000 tarda 1seg. en ser 
ordenada. Entonces
Tamaño 1000 2000 10000 100000
Tiempo real 1s 4s 100s 10000s
J.Dorronsoro, P. Varona, C. Aguirre
20
Ejemplo: método de la Burbuja
 Ordenación por burbuja (BurbujaSort_v1).
BurbujaSort_v1(Tabla T, ind P,ind U)
para i de U a P+1:
para j de P a i-1:
si T[j]>T[j+1]:
swap(T[j],T[j+1]);
 Índice j: burbuja que intenta subir. Si no puede, 
cambiamos de burbuja
 En cada iteración en i el final de la tabla se va 
ordenando de derecha a izquierda
J.Dorronsoro, P. Varona, C. Aguirre
21
 BubbleSort_v1 
Entrada: T=[4,3,2,1], P=1, U=4. 
Funcionamiento de la Burbuja
i j Operaciones Tabla
4 1 T[1]> T[2] ? Si
swap(T[1],T[2])
3,4,2,1
4 2 T[2]> T[3] ? Si
swap(T[2],T[3])
3,2,4,1
4 3 T[3]> T[4] ? Si
swap(T[3],T[4])
3,2,1,4
3 1 T[1]> T[2] ? Si
swap(T[1],T[2])
2,3,1,4
3 2 T[2]> T[3] ? Si
swap(T[2],T[3])
2,1,3,4
2 1 T[1]> T[2] ? Si
swap(T[1],T[2])
2,1,3,4
Burbuja
J.Dorronsoro, P. Varona, C. Aguirre
22
j=1
T[1]> T[2] ? Si
4 3 2 1 43 2 1 Swap(T[1],T[2])
1 2 43 1 2 43
j=2 T[1]> T[2] ? Si3 4 2 1 23 4 1 Swap(T[2],T[3])
1 2 43 1 2 43
j=3
T[1]> T[2] ? Si
3 2 4 1 23 1 4 Swap(T[3],T[4])
1 2 43 1 2 43
j=1
T[1]> T[2] ? Si
3 2 1 4 32 1 4 Swap(T[1],T[2])
1 2 43 1 2 43
j=2
T[1]> T[2] ? Si
2 3 1 4 12 3 4 Swap(T[2],T[3])
1 2 43 1 2 43
j=1
T[1]> T[2] ? Si
2 1 3 4 21 3 4 Swap(T[1],T[2])
1 2 43 1 2 43
i=4
i=3
i=2
J.Dorronsoro, P. Varona, C. Aguirre
23
Rendimiento de la Burbuja
 OB? CDC!!
 Ordenación por burbuja (BurbujaSort_v1).
BurbujaSort_v1(Tabla T, ind P,ind U)
para i de U a P+1:
para j de P a i-1:
si T[j]>T[j+1] :
swap(T[j],T[j+1]);
 Entonces
OB(i-1)-P+1
Iteraciones
22
)1(1),1,(
122
1
1
1_
NiiNTn
N
i
N
i
N
i
i
j
vBSort  



2N
J.Dorronsoro, P. Varona, C. Aguirre
24
Observaciones sobre el tae de la Burbuja
 El tae de BurbujaSort_v1 (y de SelectSort) NO
depende de la entrada (es siempre N2/2-N/2).
 Se tarda lo mismo en ordenar una tabla desordenada 
que una tabla ordenada!!!
 En SelectSort no tiene remedio:
 No se puede saber si T ya está ordenada
J.Dorronsoro, P. Varona, C. Aguirre
25
Mejorando la Burbuja
 En BurbujaSort_v1 sí se puede saber si T está 
ordenada
 Ejemplo: T = [ 1 2 3 4 ]
 En la primera iteración no se hacen swaps, pues la 
subtabla está ordenada
 Se puede añadir un flag para comprobar si se 
hacen o no swaps en el bucle interno
 Si no se hacen, la subtabla ya está ordenada y 
también la tabla completa
 Se puede terminar el algoritmo y mejorar así el 
rendimiento.
J.Dorronsoro, P. Varona, C. Aguirre
26
Rendimiento de la V2 de la Burbuja
 Ordenación por burbuja (BurbujaSort_v2).
BurbujaSort_v2(Tabla T, ind P,ind U)
Flag=1; i=U;
mientras (Flag==1 && i≥P+1) :
Flag=0;
para j de P a i-1 :
si T[j]>T[j+1] :
swap(T[j],T[j+1]); Flag=1;
i--;
 Ahora se tiene nBSort_v2([1,2,….N])=N-1 y para el 
caso peor se sigue teniendo nBSort_v2(T,1,N)≤ 
N2/2-N/2
J.Dorronsoro, P. Varona, C. Aguirre
27
Pero …
 Estamos trabajando con algoritmos de manera 
individual …
 Pero queremos comparar unos algoritmos con 
otros
 Q: ¿Cómo comparar dos algoritmos?
J.Dorronsoro, P. Varona, C. Aguirre
28
Comparación de Algoritmos
 Sólo `posible sobre algoritmos “parecidos”
1. Que resuelvan el mismo problema (ordenación, 
búsqueda)
2. Que tengan la misma operación básica.
 Agrupamos los algoritmos en familias F que 
cumplan las condiciones 1 y 2.
 Ejemplo
F={Algoritmos de ordenación por comparación de clave}
={InsertSort, SelectSort, BubbleSort, QuickSort, 
MergeSort,…..}
29
Comparación de Algoritmos II
 Método a seguir
1. Para todo algoritmo AF encontrar fA(N) tal que
nA(I) ≤ fA((I))
con (I) el tamaño de entrada
2. Diremos que A1 es mejor que A2 si
fA1(N) es “menor” que fA2(N)
 Sólo tiene sentido la comparación para entradas 
“grandes” = asintótica 
 Sólo compararemos fA1(N) y fA2(N) cuando N es 
grande (es decir para N →∞):
30
En esta sección hemos aprendido…
 La medida básica de eficacia de algoritmos 
 El concepto de operación básica
 El funcionamiento de algunos algoritmos simples 
(BBin, BurbujaSort, SelectSort).
 El cálculo del tae de los algoritmos simples 
anteriores como número de ejecuciones de su 
OB.
 Cómo enfocar la comparación del algoritmos
J.Dorronsoro, P. Varona, C. Aguirre
31
Herramientas y técnicas a trabajar …
 Sumatorios
 Estimación del número de iteraciones en bucles
 Buen conocimiento del funcionamiento del 
algoritmo a analizar
 Problemas a resolver: los recomendados de la 
sección 1 de las hojas de ejercicios y problemas 
(al menos!!)
J.Dorronsoro, P. Varona, C. Aguirre
32
1.2 Estimación del 
crecimiento de funciones
J.Dorronsoro, P. Varona, C. Aguirre
33
Comparación asintótica de funciones: o
 Definición 1 (f=o(g), f “<“g): Si f y g son funciones 
positivas, decimos que f=o(g) si
 Ejemplos
f=Nk , g=Nk+ε
f=log(N) , g=Nε
f=(log(N)) k , g=Nε
(ejercicio; se puede hacer por L’Hôpital)
0
)(
)(lim 
 Ng
Nf
N
34
Comp. asintótica de funciones: O
 Definición 2 (f=O(g), f “≤“g): f=O(g) si existen N0 y 
C ≥0 tales que para todo N ≥N0
f(N)≤Cg(N) 
 Ejemplo
f=N2 , g=N2+√N
Y también g = O(f)
 Interpretación: g es mayor o igual que f 
“eventualmente y con ayuda”
35
Observaciones sobre f=O(g)
 f=o(g) f=O(g)
 El reciproco a lo anterior es falso:
f=O(g)  f=o(g)
 Las constantes “no importan” en O, es decir, si
f=O(g)  f=O(kg) donde k > 0.
 Si f=O(g) y h=o(g) entonces f=O(g+h), pues 
g+h = O(g)
 Decir f=O(N2+N) no añade precisión 
 Basta con f=O(N2)
36
Comp. asintótica de funciones: 
 Definición 3 (f=(g), f “≥“g)
f=(g) si g=O(f)
 Definición 4 (f=(g), f “=“g)
f= (g) si f=O(g) y f=(g)
 Observamos que
f=(g)  g=(f) 
 Además f =(g) si 
0
)(
)(lim 

L
Ng
Nf
N
37
Comp. asintótica de funciones: ~
 Definición 5 (f~g): Decimos que f es 
asintóticamente equivalente a g si
 Ejemplo
f(N)=N2+√N+log N, g(N)=N2
 Observación
f~g  f=(g) 
Pero el recíproco es falso
1
)(
)(
lim 
 Ng
Nf
N
38
Comp. asint. de funciones: f=g+O(h)
 Definición 6 (f=g+O(h))
Si h=o(g) entonces decimos que f=g+O(h) si |f-
g|=O(h)
 Ejemplo
f(N) = N2 + √N + log(N), g(N)=N2. 
Entonces f = g + O(√N)
39
Comparación asintótica de funciones
 Tenemos una escala de precisión decreciente
 Si f=g+O(h)  f~g 
 Si f~g, entonces f=(g) 
 Si f=(g) entonces f=O(g) 
 Pero los recíprocos son falsos
40
Comparación asintótica de funciones II
Además:
 Si f=O(g) y f’ = O(g’), entonces
f + f’ = O(g + g’)
f f’ = O(g g’)
 Si P(N) es un polinomio de grado k se tiene que
P(N)=akNk+O(Nk-1)
41
Crec. de progs. aritméticas y geométricas
Observaciones:



)(
22
)1()(
2
1
NONNNiSNf
N
i
N 

 

1
1
1 




 x
xxxS
NN
i
i
N
x
x
x
xxS N
N
N 
 


 

11
 1 xSi
1
)( 1 xSi NN xS 
NSN  1 xSi
42
Ya hemos visto
Progresión geométrica (muy importante!!) 
Crecimiento de funciones derivadas
 Serie derivada
 Suma de potencias cúbicas
 Nos interesa el crecimiento y no tanto la fórmula 
cerrada
 Se puede simplificar?
)(
11
N
N
i
i
N
i
i
N Nxxdx
dxixS  

)(
36
)12)(1( 23
1
2 NONNNNiS
N
i
N 



43
Estimaciones de crecimiento de sumas
 ¿Que hacer cuando no tenemos una expresión 
cerrada para una suma ?
 Podemos aproximar la suma mediante integrales.
  


 



N
i
i
i
N
i
N
i
i
i
i
i
i
i
dxxfifdxxfdxxfifdxxf
1
1
1 1
1
1
1
)()()()()()(
dxxfSdxxf
N
N
N



1
10
)()(
f(x) creciente



N
i
N ifS
1
)(
44
Estimaciones de crecimiento de sumas II
 Análogamente, si f(x) es decreciente
 Algunas sumas que se estiman por este método 
dxxfSdxxf
N
N
N



1
10
)()(
)(
1
 también o 
1
11
1
k
k
N
k
N
N
i
k
N NOk
NS
k
NSiS 







)log()!log()log(
1
NNSNiS N
N
i
N 

harmónico) número simo-(N )log(1
1
NH
i
H N
N
i
N 

Nota: Se recomienda seguir en la pizarra o en los apuntes el método por el cual se 
han obtenido estas expresiones, ya que cada una de ellas presenta peculiaridades 
sobre la aplicación directa de la fórmula de la acotación por integrales. 45
En esta sección hemos aprendido…
 Los diferentes tipos de comparaciones asintóticas 
entre funciones.
 Cómo estimar el crecimiento de algunas 
funciones, mediante fórmulas cerradas o mediante 
integrales.
46
Herramientas y técnicas a trabajar …
 Trabajo básico con las estimaciones o, O, etc
 Aplicación de las estimaciones o, O, etc.
 Estimación mediante integrales del crecimiento 
asintótico de sumas 
 Problemas a resolver: los recomendados de la 
sección 2 de las hojas de ejercicios y problemas 
(al menos!!)
J.Dorronsoro, P. Varona, C. Aguirre
47
1.3 Complejidad de 
Algoritmos
J.Dorronsoro, P. Varona, C. Aguirre
48
Complejidad de Algoritmos
 Hasta ahora, el trabajo realizado por un algoritmo dependía 
de cada entrada en particular: nA(I) ≤ fA((I)).
 En algunos algoritmos hay un desequilibrio muy grande 
entre diferentes entradas, por ejemplo
NBSort_v2([N,N-1,….,1],1,N)=1/2(N2-N) (mucho)
NBSort_v2([1,2,….,N],1,N)=(N-1) (muy poco)
 Nos gustaría precisar la definición del trabajo que realiza un 
algoritmo, 
 Para ello definimos el Espacio de entradas de tamaño N 
de un algoritmo A como:
EA(N)={I entrada de A/ (I)=N}
49
Ejemplo: BSort
 EBSort(N)={(T,P,U)/U-P+1=N}
 Con, P,U y T cualquiera este espacio es inmanejable 
(demasiado grande) => es necesario hacer este 
espacio mas pequeño.
 Una simplificación sencilla es tomar P=1 y U=N.
 Otra simplificación es tomar TN (permutaciones de 
tamaño N), ya que lo importante es el desorden entre 
los elementos de la tabla.
 Con estas simplificaciones 
EBSort(N)= N y | EBSort(N) |=N!
50
Ejemplo: BBin
 EBBin(N)={(T,P,U,k)/k cualquiera, U-P+1=N, T 
ordenada}
 Una simplificación sencilla es tomar P=1 y U=N.
 Como T está ordenada, tomamos T=[1 … N]
 Como claves en la tabla tomamos k=1, …, N
 BBin hace el mismo número de cdcs para cualquier 
k no en T => añadimos la clave de error otra
 Con estas simplificaciones 
EBBin(N)= { 1, 2, … N, otra} y |EBBin(N) |=N+1
51
Casos mejor, peor, medio
Definiciones de complejidad
WA(N)=max {nA(I)/ IEA(N)}
Caso peor
BA(N)=min {nA(I)/ IEA(N)}
Caso mejor
AA(N)= 
donde p(I) es la probabilidad con la que aparece la entrada I
Caso medio
)()(
)(
IpIn
NEI
A
A


Observación: BA(N) ≤ AA(N) ≤ WA(N)
52
Complejidad en el caso peor
 ¿Cómo estimar el caso peor de un algoritmo?
 Paso 1: Encontrar fA(N) tal que si (I)=N se tiene 
nA(I) ≤ fA(N)
 Paso 2: Encontrar una entrada Î, que sea la entrada 
peor del algoritmo, Î tal que 
nA(Î) ≥ fA(N)
 Por el paso 1, se tiene WA(N)≤fA(N) 
 Por el paso 2 WA(N) ≥ fA(N), 
 Por tanto WA(N) = fA(N) 
 El caso mejor se estima de una forma similar
 se deja como ejercicio escribir ambos pasos para el 
caso mejor).
53
Caso peor de BSort
 Ejemplo: WBSort2(N)
 (1) Ya vimos que para toda N
nBSort2()≤N2/2+O(N)
 (2) Si =[N,N-1,N-2,…1] entonces 
nBSort2()=N2/2+O(N) 
 Por (1) y (2) se tiene 
WBSort2(N)= N2/2+O(N) 
 Ejercicio: demostrar que BBSort2(N)=N-1 54
Complejidad en el caso medio
 El caso medio suele ser el mas difícil de calcular.
 En general (aunque no siempre) supondremos 
equiprobablidad en el espacio de entradas, es 
decir 
p(I)=1/|EA(N)|
 Ejemplos:
 En BSort p()=1/N!, y 
 En BBin p(k)=1/(N+1)
55
Caso medio de búsqueda lineal
 Consideramos la Búsqueda Lineal equiprobable.
 Operación básica: CDC (si T[i]==k)
 EBLin(N) = {1, 2, …, N, otra}
BLin(tabla T, ind P, ind U, clave k)
para i de P a U;
si T[i]==k;
devolver k;
devolver ERROR;
56
Caso medio de búsqueda lineal II
 EBLin(N) = {1,2,3,…,N, otro}, |EBLin(N)| = N+1
 Se tiene
 p(k==i) = 1/(N+1) (1≤i≤N)
p(k==otro) = 1/(N+1)
 Si k≠T[i]  nBlin(k) = N
Si k=T[i]  nBlin(k) = i 
 En consecuencia
 WBlin(N) = N, 
 BBlin(N) = 1. 
 ABlin(N) = N/2 + O(1)
57
Caso medio de búsqueda lineal III
 Ejemplo: B. lineal con éxito no equiprobable.
 En este caso se tiene que 
 CN es una constante de normalización que garantiza 
 SN y CN se aproximan (por ejemplo, por integrales) 
 Se obtiene finalmente una aproximación para A.
 

)(1])[(])[()(
11
if
C
iiTkpiTknNA
N
N
i
N
i
BLinBLin
)(1])[( if
C
iTkp
N




N
i
N
N
i N
ifCif
C 11
)(decir es ,1)(1
)( donde ,)(1
11
ifiS
C
Sifi
C
N
i
N
N
N
N
iN



58
Caso medio de búsqueda lineal IV
 Por ejemplo, si tenemos 
 Aproximando por integrales se tiene
 De lo que se obtiene fácilmente:
 Este ultimo paso no es difícil, pero tampoco inmediato 
pues hay que demostrar la última equivalencia asintótica.
i
i
C
iTkp
N
)log(1])[( 



N
i
N
i
N
N
i
N ii
iiS
i
iCentonces
111
)log()log(y )log( 
)log(y (log(N))
2
1 2 NNSC NN 
)log(
2)(
N
NNABLin 
59
En esta sección hemos aprendido…
 Las expresiones de los casos mejor, peor y 
medio de un algoritmo.
 Cómo calcular el caso
mejor peor y medio de 
algunos algoritmos simples (BSort y Blin)
60
Herramientas y técnicas a trabajar …
 Cálculo de casos peores y mejores de 
algoritmos simples 
 Cálculo de caso medio de búsqueda lineal y 
variantes
 Problemas a resolver: los recomendados de la 
sección 3 de las hojas de ejercicios y problemas 
(al menos!!)
J.Dorronsoro, P. Varona, C. Aguirre
61
2011_Tema_2_Algoritmos_de_Ordenacion.pdf
Tema 2 
Algoritmos de ordenación 
 
1 
2.1 Algoritmos locales de 
ordenación 
 
2 
InsertSort 
 La idea de InsertSort consiste en tener los i-1 
primeros elementos de la tabla ordenados entre 
sí al inicio de la iteración i. 
 
 
 
 En la iteración i se coloca el elemento (i) en la 
posición correspondiente entre 1 e i de tal forma 
que pasan a estar ordenados entre sí los i 
primeros elementos de la tabla. 
(2) …. (i-1) (i) (i+1) (1) ….. (N) 
 
Ordenados Elemento a insertar 
Elemento a insertar Posición de inserción Elemento insertado 
1 2 i-1 i i+1 N 
Ordenados Ordenados 
1 3 6 7 2 5 4 1 3 3 6 7 5 4 1 2 3 6 7 5 4 
3 
InsertSort 
InsertSort(Tabla T, ind P, ind U) 
 para i de P+1 a U; 
 A=T[i]; 
 j=i-1; 
 mientras (j ≥ P && T[j]>A); 
 T[j+1]=T[j]; 
 j--; 
 T[j+1]=A; 
 Observaciones: 
 El trabajo de bucle interno depende de la entrada 
 El trabajo sobre una entrada  será: 
 
 
 1≤nIS(,i)≤i-1 
 
Operación Básica (CDC) 



N
i
ISIS inn
2
),()( 
4 
InsertSort: casos mejor y peor 
 Tenemos que 1≤nIS(,i)≤i-1; por tanto se tiene que 
N: 
 
 
 
 Caso peor 
 Paso 1: Por lo anterior N, nIS()≤N(N-1)/2 
 Paso 2: nIS([N,N-1,N-2,…..,1])= N(N-1)/2 
 
 Caso mejor 
 Paso 1: Por lo anterior N, nIS()≥N-1 
 Paso 2: nIS([1,2,3,…..,N])= N-1 
 
 
 
2
)1(
)(11),(1
222

 

NN
nNiin IS
N
i
N
i
IS
N
i

 WIS(N)=N(N-1)/2 
 BIS(N)=N-1 
5 
InsertSort: caso medio 
 El caso medio para IS es 
 
 
 
 
 
 Estado de la tabla en la iteración i 
 
 
 
 
  
  NNN
N
i
ISISISIS in
N
n
N
npNA


2
),(
!
1
)(
!
1
)()()(
 
 

N
i
IS
N
i
IS iNAin
N
N 22
),(),(
!
1


Nº medio de operaciones que realiza 
IS en la iteración i 
(2) …. (i-1) (i) (i+1) (1) ….. (N) 
Ordenados Elemento a insertar 
1 2 i-1 i i+1 N 
6 
InsertSort: caso medio 
 Observación: al abordar IS la entrada (i), ésta puede 
acabar en las posiciones 
 i, i-1, i-2, …, j, …, 2, 1 
haciendo respectivamente 
 1, 2, 3, …, i-j+1, …, i-1 e i-1 
cdcs respectivamente 
Posición Final CDC perdidas ((i)<(j)) CDC ganadas ((i)>(j)) Total CDC 
i 0 1 ((i)>(i-1)) 1=i–i+1 
i-1 1 ((i)<(i-1)) 1 ((i)>(i-2)) 2=i–(i-1)+1 
i-2 2 ((i)<(i-1), (i)<(i-2)) 1 ((i)>(i-3)) 3=i–(i-2)+1 
…j… i-j 1 ((i)>(j-1) i–j+1 
3 i-3 ((i)<(i-1),…, (i)<(3)) 1 ((i)>(2)) i-2=i–3+1 
2 i-2 ((i)<(i-1),…, (i)<(2)) 1 ((i)>(1)) i-1=i–2+1 
1 i-1 ((i)<(i-1),…, (i)<(1)) 0 i-1 
7 
InsertSort: caso medio 
 Esto es, 
nIS(i→j)=i-j+1 si 1<j≤i y nIS(i→1)=i-1, 
donde nIS(i→j) en el numero de CDC necesarias para 
insertar el elemento (i) en la posición j. 
Q: con qué probabilidad acabará (i) en la posición j? 
Si las  son equiprobables, es razonable pensar que P((i) 
acabe en j) = 1/i para todo j entre 1 e i 
De aquí se deduce que el trabajo medio AIS (N, i) de IS 
sobre la entrada i-ésima de una tabla de N elementos 
será i/2 + O(1) 
Y por tanto AIS (N) = N
2/4 + O(N) 
En más detalle … 
 
8 
InsertSort: caso medio 
 
 
 Recordamos que , 
 donde p(j) es la probabilidad de que el 
elemento (i) termine en la posición j. 
 Asumimos por equiprobabilidad que p(j) = 1/i 
(j=1,2,…i) , con lo que se tiene: 
 
 
 Dado que , sustituyendo lo 
anterior resulta: 
 
 



i
j
ISIS jinjpiNA
1
)()(),(
i
ii
iji
i
jin
i
iNA
i
j
i
j
ISIS
1
2
1
)1()(
1
)(
1
),(
11




















 




N
i
ISIS iNANA
2
),()(
)(
4
1
2
11
2
1
)(
21
1
1
12
NO
N
i
i
i
i
ii
NA
N
i
N
i
N
i
IS 






 


 




9 
InsertSort: caso medio 
 Sabemos que 
WIS (N) = N
2/2 + O(N) 
AIS (N) = N
2/4 + O(N) 
 Conclusión: IS es algo mejor que SS y que BS, 
pero no mucho más en el caso medio e igual en 
el caso peor 
 Q: hemos llegado al límite de eficacia en 
ordenación? 
 
 
10 
Cotas inferiores 
 ¿Cuánto podemos mejorar un algoritmo de ordenacion por 
cdcs? 
 Es decir ¿existe una f(N) universal tal que nA()≥f(N) para 
cualquier A? 
 Obviamente se tiene que nA()≥N, por tanto nA()=(N). 
 ¿Existe algún algoritmo que alcance esa cota mínima? 
 Si existe ¿cómo es ese algoritmo y en que condiciones la 
alcanza ? 
 Herramienta: medida del desorden de una tabla 
 
11 
¿Cómo medir el desorden de una tabla? 
 Las operaciones que realiza un algoritmo dependen del 
orden de la tabla. 
 ¿Como medir el orden o desorden que hay en una 
tabla?. 
 Definición: 
 Decimos que dos índices i<j están en inversión si (i)> (j) 
 Ejemplo: 
 =(3 2 1 5 4) 
 
 Inversiones de =((1,2),(1,3),(2,3),(4,5)) => 4 inversiones. 
 Inv()=4 
 En la práctica decimos que “3 está en inversión con 2” en vez de 
que “los índices 1 y 2 están en inversión” 
 
4 1 2 3 5 
12 
¿Cómo medir el desorden de una tabla? 
 Observaciones 
1. inv([1,2,3,…..,N-1,N])=0 
2. inv([5,4,3,2,1])=10 
3. inv([N,N-1,N-2,….,2,1])=N+(N-1)+….+2+1=N2/2-N/2 
 
Obs: No puede haber ninguna permutación con más 
inversiones que = [N,N-1,N-2,….,2,1] ya que 
 
inv([(1), (2),…., (N)])= inv((1))+inv((2))+ …+inv((N-1))+inv((N))≤ 
 
 
 ≤(N-1)+(N-2)+…..+1=N2/2-N/2 
 
 
 
≥
 
N-1 
≥
 
N-2 
≥
 
1 
13 
Cotas inferiores para algoritmos locales 
 Definición: Un algoritmo de ordenación por comparación 
de clave (CDC) es local si por cada CDC que realiza el 
algoritmo se deshace a lo sumo una inversión. 
 InsertSort, BurbujaSort y (moralmente) SelectSort son 
locales 
 Obs: Si A es un algoritmo local, el número mínimo de 
CDC que realizará A será el número de inversiones que 
tenga la tabla a ordenar , es decir nA()≥inv(). 
 Caso peor: Si A es local, WA(N)≥N
2/2-N/2 
 
WA(N)≥nA([N,N-1,N-2,…,2,1]) ≥inv ([N,N-1,N-2,…,2,1]) =N
2/2-N/2 
 
 Consecuencia: IS, BS y SS son óptimos en el caso 
peor entre los algoritmos locales 
14 
Cotas inferiores en el caso medio 
 Definición: Si N definimos su traspuesta, 
t como 
t(i)= (N-i+1). 
 Ejemplo =[3,2,1,5,4] entonces t=[4,5,1,2,3] 
 Observaciones: 
 (t)t=  
 inv([3,2,1,5,4])+inv([4,5,1,2,3])=3+7=10=(5*4)/2 
 inv([5,4,3,2,1])+inv([1,2,3,4,5])=10+0=10=(5*4)/2 
 Proposición: Si N 
 inv()+ inv(t)=N(N-1)/2 
Demo: Si 1 ≤ i < j ≤ N, o bien (i,j) es inversión de  o 
(N-j+1, N-i+1) lo es de t 
 
 
15 
Cotas inferiores en el caso medio 
 Si A es local AA(N)≥N
2/4+O(N) 
 
 
 
 
 
 InsertSort es óptimo para el caso medio 
entre los algoritmos locales. 
  
 tNN
t
AA invinv
N
inv
N
n
N
NA


,
)()(
!
1
)(
!
1
)(
!
1
)(
)(
42
!
2
)1(
!
1
1
2
)1(
!
1 2
,
NO
NNNN
N
NN
N t




 

A local 
Los algoritmos locales de ordenación son 
poco eficaces. 
16 
En esta sección hemos aprendido… 
 El algoritmo de ordenación InsertSort, así 
como el cálculo de sus casos mejor, peor 
y medio. 
 El concepto de algoritmo de ordenación 
local, así como sus cotas inferiores para 
los casos peor y medio. 
17 
Herramientas y técnicas a trabajar … 
 Funcionamiento de InsertSort 
 Evolución de algoritmos locales 
 Casos peor, medio y mejor de InsertSort y 
algoritmos similares y variantes 
 Detección y cuenta de inversiones en 
permutaciones 
 Rendimiento de algoritmos locales en 
permutaciones concretas 
 Problemas a resolver (al menos!!) : 
32, 33, 34, 35, 37, 39, 40, 44, 45, 46
J.Dorronsoro, P. Varona, C. Aguirre 
18 
2.2 Algoritmos recursivos 
de ordenación 
 
19 
Métodos divide y vencerás (DyV) 
 La idea de los algoritmos divide y vencerás es la 
siguiente: 
 Partir la tabla T en dos subtablas T1 y T2 
 Ordenar T1 y T2 recursivamente. 
 Combinar T1 y T2 ya ordenados en T también ordenada. 
 Pseudocódigo general de algoritmos DyV 
 
 
 
 
 
 
 
 Una primera opción es implementar una función Partir 
sencilla y una función Combinar complicada. 
 Resultado: MergeSort. 
 
DyVSort(tabla T) 
 si dim(T)≤dimMin : 
 directSort(T); 
 else : 
 Partir(T,T1,T2); 
 DyVSort(T1); 
 DyVSort(T2); 
 Combinar(T,T1,T2); 
20 
MergeSort 
Va a requerir memoria dinámica 
status MergeSort(tabla T, ind P, ind U) 
 si P>U: 
 devolver ERROR; 
 si P==U: //tabla con un elemento 
 devolver OK; 
 else: 
 M=(P+U)/2; // ”partir” 
 MergeSort(T,P,M); 
 MergeSort(T,M+1,U); 
 devolver Combinar(T,P,M,U); 
21 
Combinar 
MergeSort 
 Ejemplo 
 5 3 1 4 6 2 
1 2 3 4 5 6 
Partir 
5 3 1 4 6 2 
Partir Partir 
5 3 4 6 
Partir Partir 
1 2 
Combinar 
3 5 4 6 
Combinar Combinar 
1 3 5 2 4 6 
Combinar 
1 2 3 4 5 6 
5 3 4 6 
22 
MergeSort: Combinar 
status Combinar(Tabla T,ind P,ind U,ind M) 
 T’=TablaAux(P,U); 
 Si T’==NULL: devolver Error; 
 i=P;j=M+1;k=P; 
 mientras i≤M y j≤U: 
 si T[i]<T[j]: T’[k]=T[i];i++; 
 else: T’[k]=T[j];j++; 
 k++; 
 si i>M: // copiar resto de tabla derecha 
 mientras j≤U: 
 T’[k]=T[j];j++;k++; 
 else si: j>U: // copiar resto de tabla izquierda 
 mientras i≤M: 
 T’[k]=T[i];i++;k++; 
 Copiar(T’,T,P,U); 
 Free(T’); 
 devolver T; 
Operación 
Básica de 
Combinar 
y de MS 
Tabla auxiliar con 
indices de P a U 
Copia T’ en T 
entre los indices P y U 
23 
1 2 3 4 5 6 
Combinar: Ejemplo 
1 3 5 2 4 6 
1 2 3 4 5 6 
i j 
T 
1 2 3 4 5 6 
k 
T’ 
1 3 5 2 4 6 
i j 
T 
1 2 3 4 5 6 
k 
T’ 1 
1 2 3 4 5 6 
1 3 5 2 4 6 
i j 
T 
1 2 3 4 5 6 
T’ 1 2 
k 
1 2 3 4 5 6 
1 3 5 2 4 6 
i j 
T 
1 2 3 4 5 6 
T’ 1 2 3 
k 
1 2 3 4 5 6 
1 3 5 2 4 6 
i j 
T 
1 2 3 4 5 6 
T’ 1 2 3 4 5 
k 
1 2 3 4 5 6 
1 3 5 2 4 6 
i j 
T 
1 2 3 4 5 6 
T’ 1 2 3 4 5 6 
k 
T[1]<T[4] 
i++,k++ 
T[3]>T[4] 
j++,k++ 
T[2]<T[5] 
i++,k++ 
T[3]>T[5] 
j++,k++ 
T[3]<T[6] 
i++,k++ 
i>M 
Finalmente copiamos T’ en T y liberamos T’ 
24 
MergeSort: Rendimiento 
 
 
 Observaciones 
1. OB: en Combinar T[i]<T[j] 
2. nMS()= nMS(i)+ nMS(d)+ nCombinar(, i , d) 
3. tamaño (i)=N/2 ; tamaño (d)=N/2 
4. N/2 ≤nCombinar(, i , d)≤N-1 
 Con estas observaciones se tiene: 
 WMS(N) ≤ WMS(N/2 ) + WMS(N/2 ) +N-1; 
 WMS(1)=0. 
 Primer ejemplo de desigualdad recurrente. 
CG: T(N) ≤ T(N1) + T(N2) + …..+ T(Nk) +f(N), con Ni<N 
CB: T(1)=X (X constante). 
25 
MergeSort: Rendimiento, caso peor 
 
 
 ¿ Cómo se resuelve una desigualdad recurrente ? 
 Paso 1: Se obtiene una solución particular, por ejemplo 
sobre un caso particular fácil de calcular. 
 Por ejemplo en el caso de MS, se toma N=2k 
 En el caso de MS, tomando N=2k se tiene la desigualdad 
recurrente 
 WMS(N) ≤ 2WMS(N/2)+N-1 y WMS(1)=0 
 Desarrollando en cadena la expresión anterior se obtiene 
 WMS(N) ≤ Nlg(N)+O(N). 
 Paso 2: Se demuestra que la expresión obtenida en el 
paso 1 es válida para todo N mediante el método de 
demostración por inducción. 
Nota importante: Se recomienda ver el desarrollo anterior para ambos 
pasos en clase o en los apuntes de la asignatura. 
26 
MergeSort: Rendimiento, casos peor y medio 
 
 
 Por un razonamiento similar al del caso peor se tiene que 
BMS(N) ≥ BMS(N/2 ) + BMS(N/2 ) + N/2 y 
 BMS(1)=0 
 Tomando, de nuevo N=2k se obtiene la ecuación 
recurrente BMS(N) ≥ 2BMS(N/2)+N/2 y BMS(1)=0 
 Resolviendo la desigualdad anterior se obtiene: 
BMS(N) ≥ (1/2)Nlg(N) 
 Para estimar el caso medio observamos que: 
 (1/2)Nlg(N) ≤ BMS(N) ≤ AMS(N) ≤ WMS(N) ≤ Nlg(N)+O(N), con 
lo cual se tiene que: AMS(N)=(Nlg(N)) 
 El rendimiento es bueno, pero el algoritmo necesita 
memoria dinámica y además tiene costes ocultos en la 
recursión 
 
27 
QuickSort 
 En Quicksort (QS), se parte de una función 
Partir complicada que hace innecesaria una 
función Combinar. 
 La idea de Partir en QS consiste en elegir una 
elemento M=T[m] de la tabla a ordenar (pivote). 
 Tras Partir los elementos de la tabla quedan 
ordenados respecto a M 
 =>no hace falta Combinar. 
 
M T[2] T[3] T[N] M=T[1] 
T[1] T[2] T[i-1] M T[i-1] T[N] 
i 
> M < M 
Partir 
Ti Td 
Ejemplo: 
28 
QuickSort: pseudocódigos 
status QS(tabla T, ind P, ind U) 
 si P>U: 
 devolver ERROR; 
 si P==U: 
 devolver OK; 
 else: 
 M=Partir(T,P,U); 
 si P<M-1: 
 QS(T,P,M-1); 
 si M+1 < U: 
 QS(T,M+1,U); 
 devolver OK; 
ind Partir(tabla T, ind P, ind U) 
 M=Medio(T,P,U); 
 k=T[M]; 
 swap(T[P],T[M]); 
 M=P; 
 para i de P+1 a U: 
 si T[i]<k: 
 M++; 
 swap(T[i],T[M]); 
 swap(T[P],T[M]); 
 devolver M; 
Pivote 
29 
QuickSort: Elección del pivote 
 El pivote se puede elegir de varias 
maneras: 
 El primer elemento (devolver P). 
 El último elemento (devolver U). 
 La posición que está en mitad de la tabla 
(devolver (P+U)/2). 
 Una posición aleatoria entre el primer y 
ultimo elemento de la tabla (devolver 
aleat(P,U)). 
 No se garantiza que el valor del pivote 
sea aproximadamente el valor medio de 
la tabla 
30 
Ejemplo 
4 5 3 1 6 2 
M=1,k=4 
swap(T[1],T[1]) 4 5 3 1 6 2 
i=2 
T[2]>k 
4 5 3 1 6 2 i=3 
T[3]<k, M=2 
swap(T[2],T[3]) 
4 3 5 1 6 2 i=4 
T[4]<k, M=3 
swap(T[3],T[4]) 
1 2 3 4 5 6 
4 3 1 5 6 2 i=5 
T[5]>k 
4 3 1 5 6 2 i=6 
T[6]<k, M=4 
swap(T[4],T[6]) 
4 3 1 2 6 5 swap(T[1],T[4]) 
2 3 1 4 6 5 
< > 
devolver 4 
31 
QS: Rendimiento en el caso peor 
 
 
 Observaciones 
1. OB: en Partir “si T[i]<k” 
2. nQS()= nQS(i)+ nQS(d)+ nPartir() 
3. nPartir()=N-1 (Si Medio devuelve P, nMedio()=0) 
 Entonces, si i tiene k elementos, d tiene N-1-k elementos y 
por tanto 
 nQS() ≤ N-1+ W (k) + W(N-1-k) 
 ≤ N-1+ maxk = 1,…, N-1 { W(k) + W(N-1-k) } 
 Esto es, 
 W(N) ≤ N-1+ maxk = 1, …, N-1 { W(k) + W(N-1-k) } 
 Y se puede demostrar por inducción que 
 W(N) ≤ N2/2-N/2 
32 
QS: Rendimiento en el caso peor 
 
 
 Pero además WQS(N)  N
2/2-N/2. 
 Consideramos T=[1,2,3,….., N] 
 
 
Partir 
 
[2,3,….., N] 
[1,2,3,….., N] 
 
Partir 
N-1 cdc 
N-2 cdc 
[3,….., N] 
[N-1,N] 
Partir 1 cdc 
 
 
[N] 
Partir 
 Por tanto se tiene: 
nQS([1,2,3,…,N])= 
(N-1)+(N-2)+…..+1= 
N2/2-N/2 
Luego WQS(N) = N
2/2-N/2 
33 
QS: Rendimiento en el caso medio 
 
 
 De nuevo tenemos nQS()= nQS(i)+ nQS(d)+ N-1. 
 Aproximamos nQS(i)AQS(i-1) y nQS(d)AQS(N-i) con lo 
que obtenemos nQS() AQS(i-1) + AQS(N-i) + N-1. 
 Y obtenemos la igualdad recurrente aproximada 
 
 
 
 Se puede demostrar 
 
0)1(
)]()1([
1
)1()(
1

 

A
iNAiA
N
NNA
N
i
QSQSQS
)()log(2)( NONNNAQS 
Nota: Se recomienda seguir la demostración de lo anterior en la pizarra o 
en los apuntes de la asignatura. 
34 
En esta sección hemos aprendido… 
 Los algoritmos Quick y MergeSort 
 Sus ecuaciones de rendimiento en los casos peor y 
medio 
 Cómo resolverlas 
 Cómo escribir la ecuación de rendimiento de un 
algoritmo recursivos 
 Cómo efectuar estimaciones de ecs. recurrentes 
 Intuyendo soluciones particulares en algunos casos 
 Desplegando para estimar
una solución general o 
particular 
 Estimando el caso general por inducción 
Herramientas y técnicas a trabajar … 
 Funcionamiento de MergeSort y QuickSort 
 Casos peor, medio y mejor de MS y QS y 
variantes 
 Estimación del crecimiento de funciones en 
desigualdades recurrentes 
 Determinación de ecuaciones de rendimiento de 
algoritmos recurrentes y su resolución 
 Problemas a resolver (al menos!!) : 
63, 64, 65, 66, 67, 68, 69, 70, 71, 74, 75, 76, 
78, 79 
J.Dorronsoro, P. Varona, C. Aguirre 
36 
2.3 HeapSort 
 
37 
HeapSort 
 Definición: Un heap (montón) es un árbol binario 
quasicompleto (es decir, solo tiene huecos en los elementos 
más a la derecha del último nivel). 
Árbol binario 
completo 
Árbol binario 
quasicompleto (heap) 
Árbol binario 
(no heap) 
 Definición: Un Max-heap es un heap tal que  subárbol T’ de T 
se tiene info(T’)>info(T’i), info(T’d) 
Ejemplo: 
7 
6 5 
4 3 2 1 
 Observación: Un max-heap es fácil de ordenar. 
38 
Ordenación de max-heap. 
1. Se intercambia el nodo de la raiz con el nodo inferior derecho 
2. Se mantiene la condición de max-heap con el nodo recién 
colocado en la raiz. 
7 
6 5 
4 3 2 1 
1 
6 5 
4 3 2 7 
6 
1 5 
4 3 2 7 
6 
4 5 
1 3 2 7 
2 
4 5 
1 3 6 7 
5 
4 2 
1 3 6 7 
3 
4 2 
1 5 6 7 
4 
3 2 
1 5 6 7 
1 
3 2 
4 5 6 7 
3 
1 2 
4 5 6 7 
2 
1 3 
4 5 6 7 
2 
1 3 
4 5 6 7 
1 
2 3 
4 5 6 7 
1 
2 3 
4 5 6 7 39 
HeapSort: Ordenación en tablas 
 Observaciones: 
1. Si recorremos el árbol resultante al final de arriba a abajo y de 
izquierda a derecha se tiene una tabla ordenada 
2. Los nodos de un heap se pueden colocar en una tabla de tal 
forma que el método sea in-place. 
 
Ejemplo: 
7 
6 5 
4 3 2 1 
1 
0 
2 
3 4 5 6 
7 6 5 4 3 2 1 
0 1 2 3 4 5 6 
7 
6 5 
4 3 2 1 
1 
0 
2 
3 4 5 6 
7 6 5 4 3 2 1 
0 1 2 3 4 5 6 
1 6 5 4 3 2 7 
0 1 2 3 4 5 6 
swap(T[0],T[6]) 
40 
HeapSort: Posiciones en tablas que contienen 
max-heaps 
 Padre →Hijo izquierdo y Padre →Hijo derecho 
Padre Hijo Izq Hijo der 
j 2j+1 2j+2 
P HI HD 
0 1 2 
1 3 4 
2 5 6 
… … … 
 Hijo →Padre 
H P 
1 0 
2 0 
3 1 
4 1 
5 2 
6 2 
… … 
Hijo Padre 
j (j-1)/2 
41 
HeapSort: Creación del heap 
 El proceso anterior permite ordenar un heap 
 ¿Cómo podemos crear un heap a partir de una tabla dada? 
 Se mantiene la condición de heap en todos los nodos internos 
(nodos que tienen al menos un hijo), de derecha a izquierda y 
de abajo arriba. 
 1 
2 3 
4 5 6 7 
1 
2 7 
4 5 6 3 
1 
5 7 
4 2 6 3 
7 
5 1 
4 2 6 3 
7 
5 6 
4 2 1 3 
ya es un heap 
Ejemplo: 
1 2 3 4 5 6 7 
0 1 2 3 4 5 6 
1 2 7 4 5 6 3 
0 1 2 3 4 5 6 
1 5 7 4 2 6 3 
0 1 2 3 4 5 6 
7 5 1 4 2 6 3 
0 1 2 3 4 5 6 
7 5 6 4 2 1 3 
0 1 2 3 4 5 6 
42 
HeapSort: Pseudocódigo 
 
HeapSort(tabla T, int N) 
 CrearHeap(T,N); 
 OrdenarHeap(T,N); 
 
CrearHeap(tabla T, int N) 
 si N==1: 
 volver ; 
 para i de (N-2)/2 a 0 : 
 heapify(T,N,i); 
 
OrdenarHeap(tabla T, int N) 
 para i de N-1 a 1 : 
 swap(T[0],T[i]); 
 heapify(T,i,0); 
 
 
heapify(tabla T,int N,ind i) 
 mientras ( 2*i+1 ≤ N-1) : 
 ind=max(T,N,i,izq(i),der(i)); 
 if (ind ≠ i) : 
 swap( A[i], A[ind] ) ; 
 i = ind ; 
 else : 
 return; 
HeapSort 
CrearHeap 
OrdenarHeap 
heapify 
Donde la función max(T,N,i,izq(i),der(i)) 
devuelve el índice del elemento de la tabla 
T que contiene el valor mayor entre 
i, izq(i), der(i) 
43 
Profundidad de Heaps 
 Observación: Si T es un heap con N nodos, prof(T)= 
log(N) 
 
Nº de nodos N Ejemplo de Heap Prof. 
1 0 
2, 3 1 
4, 5, 6, 7 
 
 
2 
… … 
HeapSort: Rendimiento 
 Observaciones: 
 nHeapSort(T)=nCrearHeap(T)+nOrdenarHeap(T) 
 El número máximo de cdc que CrearHeap y 
OrdenarHeap realizan sobre un nodo es prof(T) 
 prof(T)= log(N) pues T es quasi-completo 
 nCrearHeap(T)≤N log(N) y nOrdenarHeap(T)≤N log(N) 
 WHS(N)=O(Nlog(N)) 
 nCrearHeap ([1,2,…,N])=Nlog(N) 
 El método seguido no es recursivo 
 Es el método de ordenación más eficaz hasta 
ahora! 
WHS(N)=(Nlog(N)) 
45 
En esta sección hemos aprendido… 
 El concepto de Maxheap y su construcción 
 El algoritmo HeapSort y su rendimiento 
Herramientas y técnicas a trabajar 
 La construcción de Maxheaps 
 La aplicación del algoritmo HeapSort 
 Problemas a resolver (al menos!!) : 
 83, 90 
 
2.4 Árboles de decisión 
para algoritmos de 
ordenación 
 
Cotas inferiores para algoritmos de 
ordenación por cdcs 
 Hasta ahora el mejor algoritmo de ordenación 
por cdcs es HeapSort 
 Ningún algoritmo de ordenación va a tener un 
coste mejor que (N) 
 Pregunta: ¿hay algoritmos de ordenación de 
coste mejor que (Nlog(N))? 
 Respuesta: NO al menos si trabajamos sobre 
cdcs 
 Herramienta: árboles de decisión 
 
 
Árbol de decisión: Ejemplo InsertSort 
1 2 3 
1:2 
1 2 3 
2:3 
2 1 3 
1:3 
1 2 3 1 3 2 
1:3 
2 1 3 2 3 1 
2:3 
1 3 2 3 1 2 2 3 1 3 2 1 
< 
< 
< 
< 
< 
> 
> > 
> > 
3
IST
1 2 3 
1 3 2 2 3 1 
2 1 3 
3 1 2 3 2 1 
Árbol de decisión: definición 
 Si A es un algoritmo de ordenación por comparación de 
clave y N es un tamaño de tabla, se puede construir su 
árbol de decisión TA
N
 sobre N cumpliendo las 
siguientes 4 condiciones: 
 
1. Contiene nodos de la forma i:j (i<j) que indica la cdc 
entre los elementos inicialmente en las posiciones i 
y j. 
2. El subárbol izquierdo de i:j en TA
N contiene el resto 
del trabajo (cdcs) que realiza el algoritmo A si i < j. 
3. El subárbol derecho de i:j en TA
N contiene el el resto 
del trabajo (cdcs) que realiza el algoritmo A si i > j. 
4. A cada N le corresponde una única hoja H en 
TA
N y los nodos entre la raíz y la hoja H son las 
sucesivas cdc que realiza el algorimo A al recibir la 
permutación  para ordenarla. 
 
Ejemplo de árbol de decisión: BurbujaSort 
1 2 3 
1:2 
1 2 3 
2:3 
2 1 3 
1:3 
1 2 3 1 3 2 
1:3 
2 1 3 2 3 1 
2:3 
1 3 2 3 1 2 
2 3 1 3 2 1 
< 
< 
< 
< 
< 
> 
> 
> 
> 
> 
1 2 3 
1 3 2 2 3 1 3 1 2 3 2 1 
3
BST
1:2 
2 1 3 
2 1 3 
> < 
* 
Imposible 
B 
B 
B 
B 
B B 
B=Burbuja 
Árbol de decisión: consecuencias 
1. El número de hojas en TA
N
 es N! =|N|. 
2. nA()=nº de cdc=profundidad de la hoja 
H en TA
N 
 
 
3. Por tanto: 
 
)()(  Hprofn N
AT
A 
)(max)(max)( 

 HprofnNW N
A
NN
TAA 

Cota inferior en el caso peor I 
 ¿Cuál es la profundidad mínima de un árbol 
binario de H hojas? 
 
Nº de hojas H ABMinimo(H) Prof. 
1 0 
2 1 
3 2 
4 2 
…. …. …. 
Cota inferior en el caso peor II 
 Parece que la Prof Mínima de un AB con 
H hojas es log(H) 
 Para el caso peor se tiene: 
 
 
 
 Como sabemos que log(N!)=(Nlog(N)) 
se tiene que WA(N)=(Nlog(N)). 
 HeapSort y MergeSort son óptimos para 
el caso peor. 



)!log( 
hojas N!con AB demín prof)(max)(
N
HprofNW N
A
N
TA 
Cota inferior en el caso medio I 
 Tenemos 
 
 
 Luego AA(N)≥PMmin(N) donde 
 
PMmin(k) = mín {prof media(T): T AB con k hojas} 
 
 Pero 
 
 LCE: Longitud de Caminos Externos 
 



N
A
N
A
N TH
TAA
Hprof
N
n
N
NA )(
!
1
)(
!
1
)(


)(
1
prof(H)
1
)( 
T de hojasH 
TLCE
kk
Tmediaprof
hojaskcon
 

Cota inferior en el caso medio II 
H1 
H2 
H3 
Suma de estas 
longitudes=LCE 
 Tenemos 
 
 
  hojask tieneT :)(min)(
con )!(
!
1
)(
min
min
TLCEkLCE
NLCE
N
NAA


Cota inferior en el caso medio III 
 Estimamos LCEmin(k) 
 k T Óptimo LCEmin(k) 
1 0 
2 2(1+1) 
3 5(2+2+1) 
4 8(2+2+2+2) 
5 12(3+3+2+2+2) 
…. …. …. 
Cota inferior en el caso medio IV 
 Se puede demostrar (ver apuntes o clase) 
 LCEmin(k)=klog(k)+k-2 
log(k) 
 Dado que 
 
 
 
 
 
 Se sigue que 
 MS, QS y HS son óptimos para el caso medio.
 )!(
!
1
)( min NLCE
N
NAA
  


!
2
1)!log(2!)!log(!
!
1 )!log()!log(
N
NNNN
N
N
N
))log(()!log( NNN 
))log(()( NNNAA 
En esta sección hemos aprendido… 
 El concepto de árbol de decisión para un 
algoritmo de ordenación por cdc 
 A construir un árbol de decisión para un 
algoritmo de ordenación por CDC. 
 Las cotas inferiores para los algoritmos 
de ordenación por CDC 
 Cómo se obtienen mediante el uso de 
árboles de decisión. 
 La construcción de Árboles de Decisión 
para tablas de 3 elementos 
 La construcción de Árboles de Decisión 
parciales para tablas de 4 elementos 
 Problemas a resolver (al menos!!) : 
 92, 96, 97, 100, 101, 102, 103, 106 
Herramientas y técnicas a trabajar