Universidad de Alcalá _ Grado en Ingeniería Informática _ Algoritmia y complejidad _ Temario PEC1 Temas 1_4 _ Algoritmia

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

Teoría/Tema 1/1_00_Teoria_de_eficiencia.pdf
Teoría del Cálculo de la Eficiencia
1
Introducción
Este tema está dedicado a analizar algoritmos desde el punto de vista de su 
eficiencia, haciendo especial hincapié en la resolución de ecuaciones en 
recurrencia, que permitan determinar la eficiencia de los algoritmos recursivos.
Un algoritmo es un conjunto finito de reglas precisas que resuelven un 
problema en una cantidad finita de tiempo.
El cálculo de la eficiencia de un algoritmo permitirá medir de alguna forma el 
coste (en nuestro caso el tiempo) que consume un algoritmo para encontrar la 
solución. 
Asimismo ofrecerá la posibilidad de comparar distintos algoritmos que 
resuelven un mismo problema y ver cual es el más eficiente.
2
Eficiencia y Complejidad
Una vez se tiene un algoritmo implementado que funciona correctamente, es 
necesario analizar su simplicidad y eficiencia para medir su rendimiento o 
comportamiento.
La simplicidad facilita la verificación, el estudio de la eficiencia y el 
mantenimiento de un determinado algoritmo.
Es importante cuando se diseña un algoritmo encontrar el compromiso
adecuado entre simplicidad (Menos eficiente) y alternativas más complejas (Más 
eficientes).
3
Eficiencia y Complejidad
La eficiencia de un algoritmo suele medirse en espacio (memoria que utiliza) y 
tiempo (lo que tarda en ejecutarse).
Ambos parámetros representan los costes que supone encontrar la solución al 
problema planteado mediante un algoritmo.
Gracias a estos parámetros se puede comparar algoritmos y determinar cual es 
el más adecuado (solución a un mismo problema).
El tiempo depende de diversos factores (datos de entrada, calidad del código, 
naturaleza de las instrucciones, complejidad intrínseca del algoritmo, etc.).
Esta asignatura se centra en el estudio del tiempo.
4
Eficiencia y Complejidad
La unidad del tiempo para referenciar la eficiencia de un algoritmo no puede 
ser expresada en una unidad de tiempo concreta (ms, s, m, h, …), pues no 
existe un ordenador estándar al que puedan hacer referencia todas las 
medidas.
Por este motivo se denota como medida de tiempo T(n) y representa el tiempo 
de ejecución de un algoritmo para una entrada de tamaño n.
T(n) indica el número de instrucciones ejecutadas por un ordenador idealizado.
Por tanto se debe buscar medidas simples y abstractas independientes del 
ordenador a utilizar.
5
Eficiencia y Complejidad
Para ello es necesario acotar de alguna forma la diferencia que se puede 
producir entre distintas implementaciones de un mismo algoritmo.
Aplicando el principio de invarianza se concluye que el tiempo de ejecución de 
dos implementaciones distintas de un mismo algoritmo no va a diferir más que 
en una constante multiplicativa.
Esta constante dependerá del orden del algoritmo y de sus entradas de datos 
(Ordenadas o no).
6
Eficiencia Lineal. Operaciones Elementales
La medición del tiempo de un algoritmo se realizará en función del número de 
operaciones elementales (Oes) que este realiza.
Una OE es aquella cuyo consumo de tiempo de ejecución puede acotarse por 
una constante, es decir, que no depende en ninguna medida del tamaño 
ejemplar que se esté resolviendo.
Para simplificar, se considera el coste de una OE o de una instrucción 
compuesta únicamente por Oes, como coste 1, es decir OE ∈ O(1).
7
Eficiencia Lineal. Operaciones Elementales
Las siguientes operaciones, si se aplican sobre datos de tipo básico son 
operaciones elementales:
◦ Operaciones Aritméticas básicas: +, -, *,/, DIV, MOD, ABS, …;
◦ Operaciones lógicas: Y, O, NO , XOR;
◦ Operaciones de Orden: <, ≤, >, ≥, ≠;
◦ Lectura o escritura;
◦ Asignación de valores;
◦ La instrucción de pseudocódigo Devolver.
8
Eficiencia Lineal. Instrucción Condicional
Son instrucciones del tipo:
Si cond entonces InstrV si no InstF fsi
El coste de la instrucción completa es:
coste cond    Max coste InstrV , coste InstF
Siempre y cuando las instrucciones InstrV e InstrF puedan ocurrir con 
aproximadamente la misma frecuencia. En caso de que la condición cond
tenga un valor lógico mucho más frecuente que el otro, en vez de tomar el 
máximo de las dos ramas se usará únicamente el del caso más habitual.
9
Eficiencia Lineal. Instrucción Condicional
Son instrucciones del tipo:
Si cond entonces InstrV si no InstF fsi
El coste de la instrucción completa es:
coste cond    Max coste InstrV , coste InstF
10
proc Condicional1(E/S:entero1, entero2)
si entero1 > entero2 entonces
entero2 = entero2 + 1
sino
entero1 = entero1 +1
fsi
fproc
proc Condicional2(E/S: entero1, entero2)
si entero1 > entero2 entonces
entero2 = entero2*2
entero2 = entero2 + 1
sino
entero1 = entero1*2 + 1
fsi
fproc
Eficiencia Lineal. Instrucción Condicional
Son instrucciones del tipo:
Si cond entonces InstrV si no InstF fsi
El coste de la instrucción completa es:
coste cond    Max coste InstrV , coste InstF
11
proc Condicional3(E/S:entero1, entero2)
si entero1 > Potencia (entero2, 2)
entonces
entero2 = entero2 * 2
entero1 = Potencia (entero1, 2)
sino
entero1 = entero1 + 1
Condicional3(entero1, entero2)
fsi
fproc
proc Condicional4(E/S:entero1, entero2)
si entero1 > Potencia (entero2, 2) entonces
entero2 = entero2 * 2
entero1 = Potencia (entero1, 2)
entero2 = entero2 * 2
entero1 = Potencia (entero1, 2)
entero2 = entero2 * 2
entero1 = Potencia (entero1, 2)
Condicional4(entero1, entero2)
sino
entero1 = entero1 + 1
Condicional4(entero1, entero2)
entero2 = entero2 - 1
Condicional4(entero1, entero2)
fsi
fproc
Eficiencia Lineal. Instrucción Condicional
Si la instrucción condicional es múltiple:
Caso de expr sea
Lista1: instr1;
Lista2: instr2;
…
Lista3: instr3;
El coste se calcula de manera análoga entre todas las ramas disponibles.
12
Eficiencia Lineal. Instrucción por Bucle
Para los bucles no determinados, como en la instrucción:
Mientras cond Hacer InstrM fmientras
El coste se obtiene mediante:
coste cond    ∑cond Verdad  coste InstrM    coste cond
13
proc Bucle(E/S: n)
entero x = 1
mientras x < n Hacer
x = x * 2
fmientras
fproc
SOLUCIÓN: Añadir una variable contador “k” al bucle
14
15
proc BucleFor1(E/S:entero1, entero2)
desde contador = 1 hasta entero2
entero2 = entero2 / 2
Escribir (entero1, entero2)
fdesde
fproc
proc BucleFor2(E/S:entero1, entero2)
desde contador = 1 hasta Potencia (entero2, 2)
entero2 = entero2 / 2
Escribir (entero1, entero2)
fdesde
fproc
Órdenes de Complejidad. Costes.
Se dice que Ο f n   define un orden de complejidad. Se escoge como 
representante de este orden a la función f(n) más sencilla del mismo.
◦ Ο 1   Orden Constante.
◦ Ο log n   Orden Logarítmico.
◦ Ο n   Orden Lineal.
◦ Ο n2   Orden Cuadrático.
◦ Ο na   Orden Polinomial, a 2.
◦ Ο an   Orden Exponencial, a 2.
◦ Ο n!   Orden Factorial.
◦ Ο nn   Orden Potencial.
O 1   O log n   O n   O n2   O na   O an   O n!   O nn  . 
16
17
Eficiencia Recursiva (Básica)
Si un método tiene llamadas recursivas, a la hora de conseguir representarlo 
por una función matemática hay que tener en cuenta:
◦ Al ser un método recursivo, el tamaño del ejemplar debe reducirse hasta 
llegar a los casos básicos. 
Nota: Inicialmente, las llamadas recursivas serán siempre más costosas
que el análisis de los casos básicos, que pueden obviarse.
◦ El tamaño del ejemplar dependerá exclusivamente de los parámetros de 
entrada y entrada/salida.
Nota: Habrá que encontrar la forma de asociar el trabajo que realiza el 
método (uso de los recursos) con sus parámetros.
◦ El tamaño de los ejemplares recursivos puede depender de la ejecución
del método, por lo que es necesario llevar un seguimiento de los valores 
de los parámetros en las llamadas recursivas.
18
Eficiencia Recursiva (Básica)
Recursividad. Técnica aplicada para resolver un problema que está sujeto a 
reglas o pautas recurrentes.
Según donde se haga la llamada recursiva se tiene:
◦ Recursividad Directa. La función se llama a si misma.
◦ Recursividad Indirecta. La función A llama a la función B, y está
llama a A.
Según el número de llamadas recursivas generadas en tiempo de ejecución se 
tiene:
◦ Recursividad Lineal o Simple. Se genera una única llamada interna.
◦ Recursividad no Lineal o Múltiple. Se generan 2 o más llamadas internas.
19
Eficiencia Recursiva (Básica)
Ventajas Recursividad. 
◦ Solución de problemas natural, sencilla, comprensible y elegante.
◦ Facilidad para comprobar y verificar que la solución obtenida es correcta.
Inconvenientes Recursividad. 
◦ Suelen ser más ineficientes en tiempo y espacio que las iterativas.
◦ Suelen repetir cálculos de forma innecesaria.
20
Eficiencia Recursiva. Ecuación Característica
Para obtener la eficiencia de un método recursivo se usará el método de la 
Ecuación Característica, que consiste en encontrar las raíces de la función 
matemática que representa el uso de recursos de un método recursivo.
El método de la Ecuación Característica que se aplicará en esta asignatura 
consta de 6 pasos que permitirá obtener la eficiencia de un método recursivo 
de forma simplificada. 
21
1. Obtener la función matemática que modela el método recursivo.
22
2. Transformar la función en una ecuación. Cada llamada a la función 
recursiva se convierte en un término polinómico con grado igual al 
parámetro de la función.
Nota: ¡Debe quedar un polinomio! Si los parámetros no son números 
naturales se deberá hacer un cambio de variable.
3. Resolver la parte Homogénea de la ecuación. Es decir, se iguala el 
polinomio a 0 y se encuentran su raíces, sin considerar las nulas.
Lo más fácil es sacar factor común al menor término polinómico y 
eliminarlo.
23
4. Resolver la parte No Homogénea de la ecuación. Es decir, se agrupan los 
términos en productos por exponenciales, y se obtienen las raíces según 
la Teoría del Análisis.
De cada Producto p(n)·an, se obtienen las raíces (x-a)1+grado p(n).
5. Se combinan las raíces de la parte Homogénea y No Homogénea, y se 
obtiene la eficiencia asociada a la función recursiva como la suma de las 
familias exponenciales linealmente independientes.
La raíz k-ésima (x-a) proporciona el sumando ck·an, siendo ck una 
constante.
Las raíces múltiples deben proporcionar sumandos independientes, así
que si es necesario el sumando deberá multiplicarse por la variable.
Si en el Paso2 se ha hecho un cambio de variable, ahora hay que 
deshacerlo.
6. Si se necesita, se calculan las constantes implicadas.
24
Paso 2.Transformar la función en una ecuación
Nota: xn/3 no se puede poner en término polinómico al no ser un número N. Se debe hacer por 
tanto un cambio de variable.
Se pasa a polinomio T n    xn
T 3k    T 3k‐1 2 9k 1
T 3k    T 3k‐1 2 9k 1
xk        xk ‐1    2 9k 1 xk ‐ xk ‐1  2 9k 1 
Paso 3.Se resuelve la parte Homogénea de la ecuación
Se iguala la parte polinómica a 0 y se encuentran su raíces, sin considerar las nulas.
xk ‐ xk ‐1  0
25
xk‐a  xb‐k a
Se saca factor común. Se coge el término menor.
xk ‐ xk ‐1  0 
Para el primer monomio  xK‐1  xk‐k 1  x1
Para el segundo monomio  xK‐1  xk‐1‐k 1  x0  1 
xk ‐1 x1 ‐ 1  0 
Se obtienen las raíces. 
Nota: En este caso como el polinomio obtenido es de grado 1 no hace falta factorizar.
Raíz parte Homogénea x ‐ 1  0 
Paso 4.Se resuelve la parte No Homogénea de la ecuación
Se iguala la parte no homogénea a 0 y se encuentran su raíces, sin considerar las nulas.
2 9k 1  0
26
Se modifica la ecuación para que sea de la forma polinomio por exponencial. 
Nota: p(n)·an
2 9 k  1  0
p(n)·an p(n)·an
9k  ‐ 1k  02k0 k0
Se obtienen las raíces. 
Nota: De cada Producto p(n) an, se obtienen las raíces (x-a)1+grado p(n).
p(n)·an, (x-a)1+grado p(n).
k0·9k (x-9)1+0 (x-9)
k0·1k (x-1)1+0 (x-1)
Raíces de la parte No Homogénea x ‐ 1   x ‐ 9  0 
Se obtiene la eficiencia asociada a la función recursiva como la suma de las familias exponenciales 
linealmente independientes. 
Nota: La raíz k-ésima (x-a) proporciona el sumando ck·an, siendo ck una constante.
x‐1 2 x‐9
27
Se deshace el cambio. 
n 3k   k  log3n
T(3k) = c1·1k + c2·k ·1k + c3·9k
Eficiencia  T n   Ο n2
T 3k    c1 c2 k c3 9k
= c1 · nlog31 + c2·log3n · nlog31 + c3·nlog39
= c1 + c2·log3n + c3·n2
T(n) = c1 ·1log3n + c2·log3n ·1log3n + c3·9log3n
nlog3a = alog3n
Teoría/Tema 1/1_01_Eficiencia_y_series.pdf
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 1 / 2 
 
RESUMEN DEL CÁLCULO DE EFICIENCIA 
SECUENCIAL (BÁSICA) 
Vamos a trabajar con los siguientes costes reducidos para el cálculo de la eficiencia: 
OPERACIONES ELEMENTALES: 
 Una operación elemental es aquella cuyo consumo de tiempo de ejecución puede 
acotarse por una constante, es decir, que no depende en ninguna medida del tamaño del 
ejemplar que se está resolviendo. Para simplificar, se considerará el coste de una 
operación elemental, o de una instrucción compuesta únicamente por operaciones 
elementales, como coste 1, es decir, OE ∈O(1). 
 Las siguientes operaciones, si se aplican sobre datos de tipo básico, son 
operaciones elementales 
• Operaciones aritméticas básicas: +, –, *, /, DIV, MOD, ABS…; 
• Operaciones lógicas: Y, O, NO, XOR; 
• Operaciones de orden: <, ≤, >, ≥, =, ≠; 
• Lectura o escritura; 
• Asignación de valores; 
• La instrucción de pseudocódigo Devolver. 
INSTRUCCIÓN CONDICIONAL
 En las instrucciones del tipo 
Si cond entonces InstrV si no InstF fSi 
se considera el coste de la instrucción completa como 
coste(cond) + Max { coste(InstrV), coste(instrF) } 
siempre las instrucciones InstrV y InstrF puedan ocurrir con aproximadamente la misma 
frecuencia. En caso de que la condición cond tenga un valor lógico mucho más 
frecuente que el otro, en vez de tomar el máximo de las dos ramas se usa únicamente el 
del caso más habitual. 
 Si la instrucción condicional es múltiple 
 Caso de expr sea 
 Lista1: instr1 
 Lista2: instr2 
 … 
 ListaN: instrN 
 fCaso 
el coste se calcula de manera análoga entre todas las ramas disponibles. 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 2 / 2 
 
INSTRUCCIÓN DE BUCLE
 Para los bucles no determinados, como en la instrucción 
Mientras cond Hacer InstrM fMientras 
el coste se obtiene mediante 
coste(cond) + ( )∑
=
+
Verdadcond
condInstrM )(coste)(coste 
y análogamente, para Repetir InstrR Hasta cond fRepetir se utiliza 
coste(InstrR) + coste(cond) + ( )∑
=
+
Falsocond
condInstrR )(coste)(coste . 
 Para los bucles determinados 
Desde var ← vini hasta vfin Hacer InstrD fDesde 
el coste completo se consigue mediante 
Max { coste(vini), coste(vfin) } + ∑
=
vfin
vini
InstrD
var
)(coste
SUMATORIOS Y SERIES BÁSICAS 
 Las siguientes fórmulas, y algunas variantes, se necesitarán para calcular la 
eficiencia del código secuencial. 
• Sumatorio de una constante: . Por tanto, . knk
n
i
=∑
=1
)1( +−=∑
=
abkk
b
ai
• Sumatorio sobre la variable del sumatorio: 
2
)1(
1
+
=∑
=
nni
n
i
. Si faltan los 
primeros términos, 
2
)1()1( aabbi
b
ai
−−+
=∑
=
. 
• Otra fórmula útil: 
6
)12)(1(
1
2 ++=∑
=
nnni
n
i
 
• Sumatorio de la serie geométrica: 
1
11
0 −
−
=
+
=
∑ r
rr
nn
i
i 
• Los sumatorios pueden descomponerse en sumas y extraer constantes: 
 ( ) nnnnnniii
n
i
n
i
n
i
n
i
523)1(2343434 2
1111
+=++=+=+=+ ∑∑∑∑
====
 
 
Teoría/Tema 1/1_02_Eficiencia_recursiva.pdf
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 1 / 2 
 
RESUMEN DEL CÁLCULO DE 
EFICIENCIA RECURSIVA (BÁSICA) 
Si un método tiene llamadas recursivas, a la hora de conseguir representarlo por una función 
matemática hay que tener en cuenta… 
• Al ser un método recursivo, el tamaño del ejemplar debe reducirse hasta llegar a los 
casos básicos. Inicialmente, las llamadas recursivas serán siempre más costosas que el 
análisis
de los casos básicos, que puede obviarse. 
• El tamaño del ejemplar dependerá exclusivamente de los parámetros de entrada y de 
los parámetros de entrada / salida. Por lo tanto, hay que encontrar la forma de asociar 
el trabajo que realiza el método (uso de recursos) con sus parámetros. 
• El tamaño de los ejemplares recursivos puede depender de la ejecución del método, 
por lo que es necesario llevar un seguimiento de los valores de los parámetros en las 
llamadas recursivas. 
ECUACIÓN CARACTERÍSTICA 
Para obtener la eficiencia de un método recursivo usaremos el método de la Ecuación 
Característica, que consiste en encontrar las raíces de la función matemática que representa el 
uso de recursos del método recursivo. Seguiremos los siguientes pasos: 
1. Obtener la función matemática que modela el método recursivo. 
2. Transformar la función en una ecuación: cada llamada a la función recursiva se 
convierte en un término polinómico con grado igual al parámetro de la función. 
• ¡Debe quedar un polinomio! Si los parámetros no son números naturales hay 
que hacer un cambio de variable. 
3. Se resuelve la parte Homogénea de la ecuación: se iguala el polinomio a 0 y se 
encuentran sus raíces, sin considerar las raíces nulas. 
• Lo más fácil es sacar factor común al menor término polinómico y eliminarlo. 
4. Se resuelve la parte No Homogénea de la ecuación: se agrupan los términos en 
productos de polinomio por exponenciales, y se obtienen sus raíces según la Teoría del 
Análisis. 
• De cada producto se obtienen las raíces . nanp )·( )( grado1)( npax +−
5. Se combinan las raíces de las partes Homogénea y No Homogénea, y se obtiene la 
eficiencia asociada a la función recursiva como la suma de las familias de 
exponenciales linealmente independientes. 
• La raíz k-ésima proporciona el sumando siendo una constante. )( ax − nkac kc
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 2 / 2 
 
• Las raíces múltiples deben proporcionar sumandos independientes, así que si 
es necesario el sumando debe multiplicarse por la variable. 
• ¡Si en el Paso 2 se ha hecho un cambio de variable, ahora hay que deshacerlo! 
6. Si se necesita, se calculan las constantes implicadas. 
EJEMPLO 
Vamos a resolver la ecuación recursiva 
nnTnT n 2)()( 22 ++= 
usando el método de la ecuación característica (esta función sería el resultado del Paso 1 sobre 
algún procedimiento o función recursivo) para ver cuál es el orden de eficiencia de . )(nT
2. Transformar la función en una ecuación. 
• Como no podemos poner 2
n
x porque no es un término polinómico (sería como 
tener nx ), tenemos que hacer un cambio de variable. 
• Definimos . La ecuación nos queda kn 2= kk
k
k TT 2·2)2(
2
2)2( 2 ++⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
= , es 
decir, . kkkk TT 2·24)2()2( 1 ++= −
• Lo pasamos a polimonios y queda . kkkk xx 2·241 ++= − kkkk xx 2·241 +=− −
3. Se resuelve la parte Homogénea de la ecuación. 
• La parte Homogénea es , y quitando las raíces obtenemos 01 =− −kk xx 0=x
0)1( =−x . 
4. Se resuelve la parte No Homogénea de la ecuación. 
• Los términos No Homogéneos son kk 2·24 + , que producen las raíces 
y . 
1)4( −x
1)2( −x
5. Se combinan las raíces de las partes Homogénea y No Homogénea, y se obtiene la 
eficiencia asociada a la función recursiva como la suma de las familias de 
exponenciales linealmente independientes. 
• El total de raíces es )4)(2)(1( −−− xxx , por lo que . kkkk cccT 421)2( 321 ++=
• Deshacemos el cambio (por lo que kn 2= nk 2log= ) y tenemos el resultado 
final, que es . 2321)( ncnccnT ++=
El resultado de este ejemplo es . )()( 2nOnT ∈
Teoría/Tema 1/Ejercicios_01_Eficiencia.pdf
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 1 / 4 
 
EJERCICIOS DE EFICIENCIA 
1. Resolver las siguientes ecuaciones recursivas: 
a) nnTnT 3)1()(  
b) 8)2()1(2)(  nTnTnT 
c) )2(2)1(34)(  nTnTnnT 
d) 4)2(4)(  nnTnT 
2. Resolver las siguientes ecuaciones recursivas: 
a)  
2
3)( nTnnT  ¿es mejor, peor o equivalente a )( 2nO ? 
b) nnTnT n 2)()( 2
2
 
c) )(212)(
3
nTnnT  ¿es mejor, peor o equivalente a )(nO ? 
d) nTnT n lg4)(2)(
2
 
e) 12)(2)(3)(
42
 nTTnT nn 
3. Analiza la eficiencia del siguiente código recursivo usando su ecuación característica. 
const dim = ... 
tipos tipovector = array[1..dim] de entero 
proc Ejercicio3(E p: entero; E/S v: tipovector) 
var i: entero 
 si (p>0) y (p<=dim) entonces 
 Desde i  1 hasta (p-1) Hacer v[i]  v[i+1] fdesde 
 Ejercicio(p-1, v) 
 fsi 
fproc 
4. La función EsPar (que puede considerarse como una operación elemental) devuelve 
TRUE si el número entero que recibe como argumento es un número par, y FALSE en otro 
caso (el cero es un número par). Analiza la eficiencia de la siguiente función mediante la 
ecuación característica. 
fun Ejercicio4(x: entero) dev r: entero 
 si (x<2) entonces r  2* x -1 
 si no 
 si Espar(x) entonces r  x - Ejercicio4(x-1) 
 si no r  x + 2*Ejercicio4(x-1) 
 fsi 
 fsi 
 Devolver r 
ffun 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 2 / 4 
 
5. Analizar la eficiencia del siguiente procedimiento usando el método de la ecuación 
característica, considerando como 1 el coste de las operaciones elementales (sin importar lo 
complejas que sean). 
tipos vector = array[1..Tam] de entero 
procedimiento Ejercicio(E/S A: vector; E a, b: 1..Tam) 
var B: vector 
 aux, pos, c1, c2: 1..Tam 
 si (a+1<=b) entonces 
 aux  (a + b)/2 {la división puede suponerse exacta} 
 Ejercicio(A,a,aux) 
 Ejercicio(A,aux,b) 
 c1  a 
 c2  aux 
 Desde pos  a hasta b Hacer 
 si (c1<aux) Y ((c2>b) O (A[c1]<A[c2])) entonces 
 B[j]  A[c1] 
 c1  c1+1 
 si no 
 B[j]  A[c2] 
 c2  c2+1 
 fsi 
 fdesde 
 Desde pos  a hasta b Hacer 
 A[pos]  B[pos] 
 fDesde 
 fsi 
fproc 
6. Analizar la eficiencia de la siguiente función atendiendo a las partes recursivas y usando 
el método de la ecuación característica. 
fun Calculo(x,y,z: entero) dev valor:entero 
var i,j,t: entero 
 valor  0 
 Desde i  x hasta y Hacer valor  valor + i fdesde 
 si (valor ÷ (x+y)) <= 1 entonces Devolver z 
 si no 
 t  x + ((y-x) ÷ 2) { ÷ es la división entera } 
 Desde i  x hasta y Hacer 
 Desde j  (3*x) hasta (3*y) Hacer 
 valor  valor + Minimo(i,j) 
 fdesde 
 fdesde 
 valor  valor + 4*Calculo(t,y,valor) 
 Devolver valor 
 fsi 
ffun 
 La función Minimo(a,b), que devuelve el valor mínimo de a y b, puede suponerse 
propia del sistema y de coste constante. 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 3 / 4 
 
7. Encuentra el orden de la familia de eficiencia del siguiente procedimiento, considerando 
el coste de las operaciones elementales (sin importar lo complejas que sean) como 
perteneciente a O(1). Se puede suponer que el sistema se encarga de cortar la recursión bajo 
condiciones externas 
const dim = ... 
tipos tabla = array[1..dim, 1..dim] de entero 
proc TablaInc(E xi, xf, yi, yf: entero; E/S t: tabla) 
var j, distx, disty, xA, xB, yA, yB: entero 
 Desde j  1 hasta (xf-xi) Hacer 
 t[xi+j, yi+j]  t[xi+j, yi+j] + 1 
 fdesde 
 distx  (xf - xi) ÷ 4 
 xA  xi + distx 
 xB  (xi + xf) ÷ 2 
 disty  (yf - yi) ÷ 4 
 yA  yi + disty 
 yB  yf - 2*disty 
 TablaInc(xi, xA, yi, yA, t) 
 TablaInc(xA, xB, yi, yA, t) 
 TablaInc(xi, xA, yA, yB, t) 
 TablaInc(xA, xB, yA, yB, t) 
 TablaInc(xB,
xf, yi, yB, t) 
 TablaInc(xi, xB, yB, yf, t) 
 TablaInc(xB, xf, yB, yf, t) 
fproc 
8. Analizar la eficiencia de esta función utilizando el método de la ecuación característica. 
proc Ejercicio(x: entero) 
var i, j, valor: entero 
 si (x<=0) entonces 
 Desde i  1 hasta x Hacer Escribir(i) fdesde 
 si no 
 Desde i  0 hasta x Hacer 
 valor  0 
 Desde j  1 hasta Potencia(2,i) Hacer 
 valor  valor+j 
 fdesde 
 Escribir(’Resultado: ’,valor) 
 fdesde 
 Ejercicio(x-1) 
 fsi 
fproc 
Suponer el coste de la función Potencia(base,expo) (que devuelve el valor base
expo
) 
como lineal sobre la variable de exponente expo. 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 4 / 4 
 
9. Analizar la eficiencia del siguiente procedimiento por el método de la ecuación 
característica considerando como 1 el coste de las operaciones elementales (sin importar lo 
complejas que sean). 
const dim = ... 
tipos vector = array[1..dim] de entero 
proc Ejercicio(E/S v: vector; E a,b: entero) 
var i,j,max,aux,c: entero 
 si (a>=b) entonces Escribir(v[a]) 
 si no 
 c  (a+b)/2 
 max  0 
 Desde i  a hasta b Hacer 
 si (max<v[i]) entonces 
 max  v[i] 
 fsi 
 fdesde 
 Desde i  a hasta c Hacer 
 v[i]  v[i]+max 
 fdesde 
 Desde i  c hasta b Hacer 
 v[i]  v[i]-max 
 fdesde 
 Desde i  a hasta c Hacer 
 Desde j  c hasta b Hacer 
 si (v[j]<v[i]) entonces 
 aux  v[i] 
 v[i]  v[j] 
 v[j]  aux 
 fsi 
 fdesde 
 fdesde 
 Ejercicio(v,a,c) 
 Ejercicio(v,c,b) 
 fsi 
fproc 
 
Teoría/Tema 1/LABORATORIO_SESION_1.pdf
LABORATORIO 1 
1 
 
 Los algoritmos estructurados suelen combinar sus 
sentencias de alguna de las formas siguientes: 
 
 sentencias sencillas 
 secuencia (;) 
 decisión (if) 
 bucles 
 llamadas a procedimientos 
 
Sentencias sencillas 
 Son sentencias de asignación, entrada/salida, etc. siempre y 
cuando no trabajen sobre variables estructuradas cuyo tamaño 
este relacionado con el tamaño N del problema. 
 
 La mayoría de las sentencias de un algoritmo requieren un 
tiempo constante de ejecución, siendo su complejidad O(1). 
 
 
2 
Secuencia (;) 
 La complejidad de una secuencia de elementos de un programa es 
del orden de la suma de las complejidades individuales. 
 
Decisión (if) 
 La condición suele ser de O(1), complejidad a sumar con la peor 
posible, bien en la rama THEN, o bien en la rama ELSE. En decisiones 
multiples (ELSE IF, SWITCH CASE), se tomara la peor de las ramas. 
 
Bucles 
 a) En los bucles con contador explícito, podemos distinguir dos casos: 
 
 - Que el tamaño N forme parte de los límites o que no. Si el bucle se 
realiza un número fijo de veces, independiente de N, entonces la 
repetición sólo introduce una constante multiplicativa que puede 
absorberse. 
 Ej: for (int i= 0; i < K; i++) {algo_de_O(1)} => K*O(1) = O(1) 
 
 
3 
 
- Que el tamaño N aparezca como límite de iteraciones ... 
 
 Ej.- for (int i= 0; i < N; i++) { algo_de_O(1) } 
 tendremos N * O(1) = O(n) 
 
 Ej.- for (int i= 0; i < N; i++) { 
 for (int j= 0; j < N; j++) { 
 algo_de_O(1) } } 
 tendremos N * N * O(1) = O(n2) 
 
 Ej.- for (int i= 0; i < N; i++) { 
 for (int j= 0; j < i; j++) { 
 algo_de_O(1) } } 
 el bucle exterior se realiza N veces, mientras que el 
 interior se realiza 1, 2, 3, ... N veces respectivamente. 
 En total, 1 + 2 + 3 + ... + N = N*(1+N)/2 -> O(n2) 
 
 
4 
 
b) A veces aparecen bucles multiplicativos, donde la evolución de la 
variable de control no es lineal (como en los casos anteriores) 
 Ej.- c= 1; 
 while (c < N) { 
 algo_de_O(1) 
 c= 2*c; 
 } 
 El valor inicial de "c" es 1, siendo "2k" al cabo de "k" iteraciones. El 
número de iteraciones es tal que 2k >= N => k= (log2 (N)). La complejidad 
del bucle es O(log n). 
 Ej.- c= N; 
 while (c > 1) { 
 algo_de_O(1) 
 c= c / 2; 
 } 
 Un razonamiento similar nos lleva a log2(N) iteraciones y, por tanto, 
 a un orden O(log n) de complejidad. 
 
 
 
 
5 
 
Ej.- for (int i= 0; i < N; i++) { 
 c= i; 
 while (c > 0) { 
 algo_de_O(1) 
 c= c/2; 
 }} 
 
 tenemos un bucle interno de orden O(log n) que se ejecuta N 
veces, luego el conjunto es de orden O(n log n) 
 
Llamadas a procedimientos (no recursivas) 
 La complejidad de llamar a un procedimiento viene dada por 
la complejidad del contenido del procedimiento en sí. El coste de 
llamar no es sino una constante que podemos obviar. 
 
 
 6 
 
 Determinar la Función de eficiencia y el Orden de complejidad 
de los siguientes fragmentos de código: 
 
 for i := 1 to n do 
 for j := 1 to n do 
 A[i,j] := 0 
 
 for j := i+1 to n do 
 If A[j] < A[chico] then 
 chico := j 
 
 
7 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
 If A[1,1] = 0 Then 
 For i := 1 to n do 
 For j := 1 to n do 
 A[i,j] := 0 
 Else 
 For i := 1 to n do 
 A[i,i] := 1 
 
8 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
For i := 1 to n-1 do begin 
 chico := i 
 For j := i+1 to n do 
 If A[j] < A[chico] Then 
 chico := j 
 Temp := A[chico] 
 A[chico] := A[i] 
 A[i] := temp 
end 
 
9 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
Procedure Insert (T[1..n]) 
 for i := 2 to n do 
 x:= T[i]; 
 j := i-1 
 while j > 0 and x < T[j] do 
 T[j+1] := T[j] 
 j := j-1 
 T[j+1] := x 
 end 
 
10 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
function mcd(m,n) 
 i := min(m,n) +1 
 repeat 
 i := i - 1 
 until (m mod I ==0 and n mod I == 0) 
 return i 
 
 
11 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
function Euclides (m,n) 
 while m > 0 do 
 t := n mod m 
 n := m 
 m := t 
 return n 
 
 
 
 
12 
 
Determinar la Función de eficiencia y el Orden de complejidad 
de: 
 
Funcion potencia1 (y:num, z:nat) dev p:nat 
 p:=1; 
 mientras z>0 hacer 
 p:= p*y; 
 z:= z-1; 
 fmientras; 
ffuncion; 
 
 
13 
 
Determinar la Función de eficiencia y el Orden de complejidad de: 
 
 
Funcion potencia2 (y:num, z:nat) dev p:nat 
 p:=1; 
 mientras z>0 hacer 
 Si impar (z) entonces 
 p:= p*y 
 fsi; 
 z:= z div 2; 
 y:= y*y; 
 fmientras; 
ffuncion; 
 
14 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
 
function fib2(n) 
 a1 := 1; 
 a0 := 0; 
 for k := 1 to n do 
 a2=a1+a0; 
 a0=a1; 
 a1=a2; 
 return a2; 
 
 
15 
 Determinar la Función de eficiencia y el Orden de complejidad 
del siguiente código: 
 
function fib3(n) 
 i := 1; 
 j := 0; 
 k := 0; 
 h := 1 
 while n > 0 do 
 if n es impar then 
 t := jh 
 j := ih +jk + t 
 i := ik + t 
 t := h ; 
 h := 2kh + t; 
 k := k + t; 
 n := n div 2 
 return j 
 
 
16 
 
 Determinar Función de eficiencia y Orden de complejidad de: 
 
 Funcion factorial (y:nat) 
 f:=1; 
 mientras y>1 hacer 
 f:= f*y; 
 y:= y-1; 
 fmientras; 
 return f; 
 ffuncion; 
 
 
17 
Determinar la Función de 
eficiencia y el Orden de 
complejidad del siguiente 
código: 
 
Program ginebra (input, output) 
var a, n : integer; 
 
begin (*programa ginebra*) 
 readln(n); 
 a := 0; 
 pub(a,n); 
 writeln(bar(a,n)) 
end 
 
 
 
18 
19 
procedure pub(var x,n: integer); 
var i: integer; 
Begin 
 For i := 1 to n do 
 x := x + bar(i,n)
end; (*pub*) 
 
Function bar(x,n: integer): integer; 
var i: integer; 
Begin 
 For i := 1 to n do 
 x = x + i; 
 bar := x 
End (*bar*) 
 
 Realiza el pseudocódigo de una función que determine si un número recibido 
como parámetro es primo. 
 Realiza el pseudocódigo de una función que determine si un número recibido 
como parámetro es perfecto. 
 Realiza el pseudocódigo de un programa que pida un número positivo al 
usuario (N) y le diga cuantos primos hay entre 1 y ese número N, y cuantos 
perfectos hay entre 1 y ese número N. 
 
 Realiza el análisis de los tres algoritmos: 
 -Función de eficiencia. 
 -Orden de complejidad. 
20 
Teoría/Tema 1/TEORIA_TEMA1_SESION_1.pdf
1 
Algoritmo. 
 
 Descripción abstracta y ordenada de todas las acciones que 
se deben realizar, así como la descripción de los datos que 
deben ser manipulados por dichas acciones, para llegar a la 
solución de un problema. 
2 
Algoritmo. 
Un algoritmo debe: 
◦ Ser independiente tanto del lenguaje de programación en que se 
exprese, como del ordenador en que se vaya a ejecutar. 
◦ Ser claro y sencillo. 
◦ Indicar el orden de realización de cada paso. 
◦ Tener un número finito de pasos (así como un principio y un fin). 
◦ Ser flexible (para facilitar su mantenimiento). 
◦ Estar definido (de manera que si se sigue un algoritmo N veces 
con los mismos datos de entrada, se debe obtener el mismo 
resultado N veces). 
3 
 
Algoritmo. 
 
Los algoritmos resuelven problemas. 
Un problema suele tener muchos ejemplares (a veces infinitos). 
Los algoritmos deben funcionar correctamente en todos los casos 
del problema que afirman resolver. 
Un solo caso erróneo, hace que el algoritmo sea incorrecto. 
Normalmente encontramos más de una forma de resolver un 
problema, es decir, hay varios algoritmos que resuelven el mismo 
problema. 
 
4 
 
 
5 
6 
7 
8 
9 
 Tal y como lo hemos presentado no mejora en eficiencia al 
algoritmo clásico. Pero, puede mejorarse: 
 Es posible reducir un producto de dos números de muchas cifras a 
3 (en vez de 4) productos de números de la mitad de cifras, y éste 
si que mejora al algoritmo clásico. 
 
 Y aún se conocen métodos más rápidos para multiplicar 
números muy grandes. 
 Necesitamos alguna forma de medir la eficiencia de un 
algoritmo para poder encontrar “el mejor” algoritmo. 
 
10 
Algoritmia 
-Tratamiento sistemático de técnicas fundamentales para el 
diseño y análisis de algoritmos eficientes. 
-La algoritmia estudia las propiedades de los algoritmos y nos 
ayuda a elegir la solución más adecuada en cada situación. Esto 
ahorra tiempo y dinero. 
-En muchos casos, una buena elección marca la diferencia entre 
poder resolver un problema y no poder hacerlo. 
 
11 
Análisis de algoritmos 
 La resolución práctica de un problema exige por una 
parte un algoritmo y por otra una codificación de aquel en un 
ordenador real. Ambos componentes tienen su importancia; 
pero la del algoritmo es absolutamente esencial. 
 Nos importan los recursos físicos necesarios para que un 
programa se ejecute. Aunque puede haber muchos 
parámetros, los mas usuales son el tiempo de ejecución y la 
cantidad de memoria (espacio). Nosotros nos centraremos 
casi siempre en el parámetro tiempo de ejecución. 
 
12 
Análisis de algoritmos 
 Para cada problema determinaremos un medida N de su 
tamaño (por número de datos) e intentaremos hallar 
respuestas en función de dicho N. 
 El concepto exacto que mide N depende de la naturaleza 
del problema. Así, para un vector se suele utilizar como N su 
longitud; para una matriz, el número de elementos que la 
componen; para un grafo, puede ser el número de nodos (a 
veces es mas importante considerar el número de arcos, 
dependiendo del tipo de problema a resolver); en un fichero se 
suele usar el número de registros, etc. 
 
13 
Análisis de algoritmos 
 Una medida que suele ser útil conocer es el tiempo de 
ejecución de un programa en función de N, lo que 
denominaremos T(N). Esta función se puede calcular sobre el 
código contando instrucciones a ejecutar y multiplicando por el 
tiempo requerido por cada instrucción. 
 
 Así, un trozo sencillo de programa como 
 S1; 
 for (int i= 0; i < N; i++) 
 S2; 
 
 requiere 
 T(N)= t1 + t2*N 
 
 siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, 
y t2 el que lleve la serie "S2“. 
14 
Análisis de algoritmos 
 Prácticamente todos los programas reales incluyen alguna 
sentencia condicional, haciendo que las sentencias efectivamente 
ejecutadas dependan de los datos concretos que se le presenten. 
 Esto hace que mas que un valor T(N) debamos hablar de un 
rango de valores: 
 Tmin(N) <= T(N) <= Tmax(N) 
 los extremos son habitualmente conocidos como "caso 
peor" y "caso mejor". Entre ambos se hallara algún "caso 
promedio" o más frecuente. 
 
15 
Análisis de algoritmos 
 Cualquier fórmula T(N) incluye referencias al parámetro N y a una 
serie de constantes "Ti" que dependen de factores externos al algoritmo 
como pueden ser la calidad del código generado por el compilador y la 
velocidad de ejecución de instrucciones del ordenador que lo ejecuta. 
 Dado que es fácil cambiar de compilador y que la potencia de los 
ordenadores crece a un ritmo vertiginoso (en la actualidad, se duplica 
anualmente), intentaremos analizar los algoritmos con algún nivel de 
independencia de estos factores; es decir, buscaremos estimaciones 
generales ampliamente válidas. 
 
16 
Asíntotas 
 Necesitamos analizar la potencia de los algoritmos 
independientemente de la potencia de la máquina que los ejecute y de la 
habilidad del programador que los codifique, y además, este análisis nos 
interesa especialmente cuando el algoritmo se aplica a problema grandes 
(ya que casi siempre los problemas pequeños se pueden resolver de 
cualquier forma, apareciendo las limitaciones al atacar problemas 
grandes). 
 Esto nos lleva a estudiar el comportamiento de un algoritmo cuando 
se fuerza el tamaño del problema al que se aplica. 
 Matemáticamente hablando, cuando N tiende a infinito. Es decir, su 
comportamiento asintótico. 
17 
Asíntotas 
 Sean "g(n)" diferentes funciones que determinan el uso de recursos. 
Habrá funciones "g" de todos los colores. Lo que vamos a intentar es 
identificar "familias" de funciones, usando como criterio de agrupación su 
comportamiento asintótico. 
 A un conjunto de funciones que comparten un mismo comportamiento 
asintótico le denominaremos un orden de complejidad. Habitualmente estos 
conjuntos se denominan O, existiendo una infinidad de ellos. 
 Para cada uno de estos conjuntos se suele identificar un miembro f(n) 
que se utiliza como representante de la clase, hablándose del conjunto de 
funciones "g" que son del orden de "f(n)“ (O(f(n)) 
18 
Asíntotas 
 Con frecuencia nos encontraremos con que no es necesario conocer el comportamiento exacto, 
sino que basta conocer una cota superior, es decir, alguna función que se comporte "aún peor". 
 El conjunto O(f(n)) es el de las funciones de orden de f(n), que se define como 
 O(f(n))= {g: INTEGER -> REAL+ 
 tales que existen las constantes k y N0 
 tales que para todo N > N0, g(N) <= k*f(N) } 
 en palabras, O(f(n)) esta formado por aquellas funciones g(n) que crecen a un ritmo menor o 
igual que el de f(n). Si un algoritmo tiene un tiempo de ejecución O(f(n)), a f(n) le llamaremos Tasa de 
Crecimiento. 
 De las funciones "g" que forman este conjunto O(f(n)) se dice que "están dominadas 
asintóticamente" por "f", en el sentido de que para N suficientemente grande, y salvo una constante 
multiplicativa "k", f(n) es una cota superior de g(n). 
 
 Principio de Invarianza. 
 
 “dos implementaciones diferentes de un mismo algoritmo 
no diferirán en eficiencia mas que, a lo sumo, en una 
constante multiplicativa”
 Si dos implementaciones consumen t1(n) y t2(n) unidades de 
tiempo, respectivamente, en resolver un caso de tamaño n, 
entonces siempre existe una constante positiva c tal que 
t1(n)<=ct2(n), siempre que n sea suficientemente grande. 
 
 Esto es válido, independientemente del ordenador usado, 
del lenguaje de programación empleado y de la habilidad 
del programador (supuesto que no modifica el 
algoritmo). 
 
19 
20 
 Órdenes de Complejidad 
 Se dice que O(f(n)) define un "orden de complejidad". Escogeremos como 
representante de este orden a la función f(n) más sencilla del mismo. Así tendremos: 
 
 O(1) orden constante 
 O(log n) orden logarítmico 
 O(n) orden lineal 
 O(n log n) 
 O(n2) orden cuadrático 
 O(na) orden polinomial (a > 2) 
 O(an) orden exponencial (a > 2) 
 O(n!) orden factorial 
 Es más, se puede identificar una jerarquía de órdenes de complejidad que 
coincide con el orden de la tabla anterior, ya que cada orden de complejidad superior 
tiene a los inferiores como subconjuntos. Si un algoritmo A se puede demostrar de un 
cierto orden O1, es cierto que también pertenece a todos los órdenes superiores. Pero en 
la práctica lo útil es encontrar la "menor cota superior", es decir el menor orden de 
complejidad que lo cubra. 
 
21 
 Órdenes de Complejidad 
 Sea un problema que sabemos resolver con algoritmos de diferentes 
complejidades. Para compararlos entre si, supongamos que todos ellos 
requieren 1 hora de ordenador para resolver un problema de tamaño N=100 
¿Qué ocurre si disponemos del doble de tiempo? O lo que es lo mismo ¿qué 
ocurre si queremos resolver un problema de tamaño 2N? 
 Los algoritmos de complejidad O(n) y O(n log n) mostrarán un 
comportamiento "natural": prácticamente a doble de tiempo, doble de datos 
procesables. 
 Los algoritmos de complejidad logarítmica son un descubrimiento 
fenomenal, pues en el doble de tiempo permiten atacar problemas 
notablemente mayores, y para resolver un problema el doble de grande sólo 
hace falta un poco más de tiempo (ni mucho menos el doble). 
 Los algoritmos de tipo polinómico no son una maravilla, y se enfrentan 
con dificultad a problemas de tamaño creciente. La práctica viene a decirnos 
que son el límite de lo "tratable". 
 
22 
 Órdenes de Complejidad 
 Cualquier algoritmo por encima de una complejidad polinómica 
se dice "intratable" y sólo será aplicable a problemas ridículamente 
pequeños. 
 
 A la vista de lo anterior se comprende que los programadores 
busquen algoritmos de complejidad lineal. Es un golpe de suerte 
encontrar algo de complejidad logarítmica. Si se encuentran 
soluciones polinomiales, se puede vivir con ellas; pero ante 
soluciones de complejidad exponencial, más vale seguir buscando. 
 
 No obstante lo anterior ... 
23 
 Órdenes de Complejidad 
 
 ... si un programa se va a ejecutar muy pocas veces, los 
costes de codificación y depuración son los que más 
importan, relegando la complejidad a un papel secundario. 
 ... si a un programa se le prevé larga vida, hay que pensar 
que le tocará mantenerlo a otra persona y, por tanto, 
conviene tener en cuenta su legibilidad, incluso a costa de la 
complejidad de los algoritmos empleados. 
 ... si podemos garantizar que un programa sólo va a trabajar 
sobre datos pequeños (valores bajos de N), el orden de 
complejidad del algoritmo que usemos suele ser irrelevante, 
pudiendo llegar a ser incluso contraproducente. 
 
Por ejemplo, tenemos dos algoritmos cuyas implementaciones en 
una máquina dada, consumen respectivamente n2 días y n3 
segundos para resolver un caso de tamaño n. 
Es solo en casos que requieran más de 20 millones de años para 
resolverlos, donde el algoritmo cuadrático puede ser más rápido 
que el algoritmo cúbico. 
En cualquier caso, el primero es asintóticamente mejor que el 
segundo, es decir, su eficiencia teórica es mejor en todos los 
casos grandes, aunque desde un punto de vista práctico se 
recomiende el empleo del cubico. 
24 
25 
 Órdenes de Complejidad 
 
 ... usualmente un programa de baja complejidad en cuanto a 
tiempo de ejecución, suele conllevar un alto consumo de 
memoria; y viceversa. A veces hay que sopesar ambos 
factores, quedándonos en algún punto de compromiso. 
 ... en problemas de cálculo numérico hay que tener en cuenta 
más factores que su complejidad pura y dura, o incluso que 
su tiempo de ejecución: queda por considerar la precisión del 
cálculo, el máximo error introducido en cálculos intermedios, 
la estabilidad del algoritmo, etc. etc. 
 
Regla de la suma. 
 
 Supongamos, en primer lugar, que T1(n) y T2(n) son los tiempos 
de ejecución de dos segmentos de programa, P1 y P2, que T1(n) es 
O(f(n)) y T2(n) es O(g(n)). Entonces el tiempo de ejecución de P1 seguido 
de P2, es decir T1 (n) + T2 (n), es O(max(f(n), g(n))). 
 
 Por ejemplo, tenemos un algoritmo constituido por 3 etapas, en el 
que cada una de ellas puede ser un fragmento arbitrario de algoritmo 
con bucles y ramas. Supongamos sus tiempos respectivos O(n2), O(n3) 
y O(n log n). Entonces 
 
 El tiempo de ejecución de las dos primeras etapas ejecutadas 
secuencialmente es O(max(n2 , n3)), es decir O(n3). 
 
 El tiempo de ejecución de las tres juntas es O(max(n2, n3, nlogn)), 
es decir O(n3 ). 
 
 
26 
 
Regla del producto. 
 
 Si T1 (n) y T2 (n) son los tiempos de ejecución de dos 
segmentos de programa, P1 y P2, T1(n) es O(f(n)) y T2(n) es 
O(g(n)), entonces T1(n) T2(n) es O(f(n) g(n)). 
 
 De esta regla se deduce que O(cf(n)) es lo mismo que O(f(n)) 
si c es una constante positiva, así que por ejemplo 
O(n2/2) es lo mismo que O(n2). 
 
27 
Teoría/Tema 2/1_03_Ordenacion_y_busqueda.pdf
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 1 / 4 
 
ORDENACIÓN DE ELEMENTOS EN PSEUDOCÓDIGO 
MÉTODOS DE ORDENACIÓN BÁSICOS: INSERCIÓN Y SELECCIÓN 
const dim = ... 
tipos vector = array[1..dim] de entero 
proc OrdenaciónPorInserción (E/S v: vector) 
var i, j, valmin: entero 
 Desde i ← 2 hasta dim Hacer 
 valmin ← v[i] 
 j ← i – 1 
 Mientras (j > 0) y (valmin < v[j]) Hacer 
 v[j+1] ← v[j] 
 j ← j – 1 
 fmientras 
 v[j+1] ← valmin 
 fdesde 
fproc 
proc OrdenaciónPorSelección (E/S v: vector) 
var i, j, posmin, valmin: entero 
 Desde i ← 1 hasta dim - 1 Hacer 
 posmin ← i 
 valmin ← v[i] 
 Desde j ← i + 1 hasta dim Hacer 
 si v[j] < valmin entonces 
 posmin ← j 
 valmin ← v[j] 
 fsi 
 fdesde 
 v[posmin] ← v[i] 
 v[i] ← valmin 
 fdesde 
fproc 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 2 / 4 
 
ORDENACIÓN DE ELEMENTOS EN PSEUDOCÓDIGO 
ORDENACIÓN BÁSICA CON ORDEN LINEAL 
const maxdato = ... 
const elementos = ... 
tipos matriz_datos = array[1..elementos] de 0..maxdato 
tipos matriz_auxiliar = array[0..maxdatos] de entero 
proc OrdenarLineal (E/S datos: matriz_datos) 
var aux, i: entero 
 auxiliar: matriz_auxiliar 
 Desde aux ← 0 hasta maxdato Hacer 
 auxiliar[aux] ← 0 
 fdesde 
 Desde i ← 1 hasta elementos Hacer 
 inc (auxiliar[datos[i]]) 
 fdesde 
 i ← 1 
 Desde ← 0 hasta maxdato Hacer aux 
 Mientras (auxiliar[aux] > 0) Hacer 
 datos[i] ← aux 
 i ← i + 1 
 auxiliar[aux] ← auxiliar[aux] - 1 
 fmientras 
 fdesde 
fproc 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 3 / 4 
 
BÚSQUEDA DE ELEMENTOS EN PSEUDOCÓDIGO 
BÚSQUEDA BINARIA 
const dim = ... 
tipos vector = array[1..dim] de tipo_problema 
fun BusquedaBinaria (E v: vector; E ini, fin: entero; 
 E dato: tipo_problema) 
 dev resultado:
entero 
var m: entero 
 si (ini = fin) entonces 
 si (v[ini] = dato) entonces Devolver ini 
 si no Devolver 0 {el dato no está} 
 fsi 
 si no 
 m ← (ini + fin) ÷ 2 
 si dato ≤ v[m] entonces 
 Devolver BusquedaBinaria (v, ini, m, dato) 
 si no 
 Devolver BusquedaBinaria (v, ini+1, fin, dato) 
 fsi 
 fsi 
ffun 
BÚSQUEDA BINARIA NO CENTRADA 
const dim = ... 
 factor = ... {por ejemplo, 3} 
tipos vector = array[1..dim] de tipo_problema 
fun BusqBinariaNoCentrada (E v: vector; E ini, fin: entero; 
 E dato: tipo_problema) 
 dev resultado: entero 
var t: entero 
 si (ini = fin) entonces 
 si (v[ini] = dato) entonces Devolver ini 
 si no Devolver 0 
 fsi 
 si no 
 t ← ini + (fin - ini) ÷ factor 
 si ≤ v[t] entonces dato 
 Devolver BusqBinariaNoCentrada (v, ini, t, dato) 
 si no 
 Devolver BusqBinariaNoCentrada (v, t+1, fin, dato) 
 fsi 
 fsi 
ffun 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 4 / 4 
 
BÚSQUEDA DE ELEMENTOS EN PSEUDOCÓDIGO 
BÚSQUEDA TERNARIA 
const dim = ... 
tipos vector = array[1..dim] de tipo_problema 
fun BusquedaTernaria (E v: vector; E ini, fin: entero; 
 E dato: tipo_problema) 
 dev resultado: entero 
var t1, t2: entero 
 si (ini = fin) entonces 
 si (v[ini] = dato) entonces Devolver ini 
 si no Devolver 0 
 fsi 
 si no 
 t1 ← ini + (fin - ini) ÷ 3 
 t2 ← ini + 2 * (fin - ini) ÷ 3 
 si dato ≤ v[t1] entonces 
 Devolver BusquedaTernaria (v, ini, t1, dato) 
 si no 
 si dato ≤ v[t2] 
 Devolver BusquedaTernaria (v, t1+1, t2, dato) 
 si no 
 Devolver BusquedaTernaria (v, t2+1, fin, dato) 
 fsi 
 fsi 
 fsi 
ffun 
Teoría/Tema 2/Ejercicios_02_DyV_lab.pdf
 
 
 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
Pág. 1 / 5 
 
 
3 2 5 
1 2 6 
 
 
 
EJERCICIOS DE DIVIDE Y VENCERÁS 
 
 
Ejercicio 1) 
Se tiene un vector V[1..N] formado por números enteros, de manera que todos ellos 
son distintos y están ordenados de manera creciente. Se dice que un vector de estas 
características es coincidente si tiene al menos una posición tal que es igual al valor que 
contiene el vector en esa posición. Por ejemplo, en el vector 
 
1 2 3 4 5 6 7 8 
 
-14 -6 3 6 16 18 27 43 
 
puede verse que V[3] = 3; por lo tanto, este vector es coincidente. 
 
Diseñar un algoritmo Divide y Vencerás que determine en un orden de eficiencia no 
superior a O(lg N) si un vector es coincidente, recibiendo como datos el vector y su tamaño. 
 
Ejercicio 2) 
Se tiene acceso a una función continua f(x) de la que se sabe que en el intervalo real 
[p1, p2] tiene un único mínimo local en el punto x0, que es estrictamente decreciente entre 
[p1, xo] y que es estrictamente creciente entre [x0, p2] . Hay que observar que x0 puede 
coincidir con p1 o con p2. 
 
Se tiene que buscar, de la manera más eficiente posible, todos los puntos x (si es que 
existen) del intervalo [p1, p2] tales que la función f(x) tome un cierto valor k, es decir, se 
busca el conjunto de valores {x  [p1, p2] tal que f(x) = k}. Para simplificar el proceso, en 
vez del valor exacto de cada x puede indicarse un intervalo de valores [α, β], con β – α < , 
donde se encuentre x. Los datos del algoritmo serán los valores de p1 y p2, el valor k que se 
está buscando, y el valor  para la aproximación. 
 
Ejercicio 3) 
Se dispone de una matriz M de tamaño FxC (F es la cantidad de filas y C la cantidad de 
columnas, de arriba abajo y de izquiera a derecha), cuyas celdas tienen un valor numérico 
entero positivo. Por ejemplo, la matriz con 2 filas y 3 columnas siguiente 
 
1 2 3 
1 
2 
 
Se define un movimiento entre las casillas Mij y Mpq como válido solamente si se cumple 
que (p=i && q=j+1) o bien si (p=i+1 && q=j), es decir, movimientos “hacia abajo” y 
“hacia la derecha”. Se denomina un camino de la matriz a la sucesión de movimientos que 
llevan de la casilla M11 a la casilla MFC. En la matriz anterior, los caminos posibles son: 
M11  M12  M22  M23 
M11  M21  M22  M23 
M11  M12  M13  M23 
 
 
 
 
 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
Pág. 2 / 5 
 
 
 
 
El coste de un camino es igual a la suma de los valores de las casillas que recorre. En 
nuestro ejemplo, los costes serían: 
M11  M12  M22  M23 3 + 2 + 2 + 6 = 13 
M11  M21  M22  M23 3 + 1 + 2 + 6 = 12 
M11  M12  M13  M23 3+ 2 + 5 + 6 =16 
 
Se pide: 
 
1) Diseñar un algoritmo Divide y Vencerás que obtenga el menor de los costes de 
todos los caminos de una matriz dada como parámetro (en el ejemplo anterior, el 
algoritmo debería devolver 12 como resultado). 
 
2) Modificar el algoritmo del apartado 1) para que devuelva el camino propiamente 
dicho. Por ejemplo, puede usarse una cadena de caracteres en la que “A” indique un 
movimiento hacia abajo y “D” un movimiento a la derecha. En el ejemplo anterior, 
el resultado correcto sería “ADD”. 
 
 
Ejercicio 4) 
Se quiere programar un robot para poner tapones de corcho a las botellas de una fábrica de 
reciclado. Se tienen disponibles N botellas y los N corchos que las tapan (N es constante en 
el problema), pero hay una serie de problemas: 
 
 Las botellas son todas distintas entre sí, igual que los corchos: cada botella solo puede 
cerrarse con un corcho concreto, y cada corcho solo sirve para una botella concreta. 
 
 El robot está preparado para cerrar botellas, por lo que lo único que sabe hacer es 
comparar corchos con botellas. El robot puede detectar si un corcho es demasiado 
pequeño, demasiado grande, o del tamaño justo para cerrar una botella. 
 
 El robot no puede comparar corchos entre sí para “ordenarlos” por grosor, y tampoco 
puede hacerlo con las botellas. 
 
 El robot tiene espacio disponible y brazos mecánicos para colocar botellas y corchos a 
su antojo, por ejemplo en distintas posiciones de una mesa, si es necesario. 
 
Diseñar el algoritmo que necesita el robot para taponar las N botellas de manera óptima. 
 
 
Ejercicio 5) 
Se tiene un vector V[1..N] del que se quiere obtener información como si estuviese 
ordenado, pero que no puede ordenarse por motivos de trabajo (tampoco pueden realizarse 
copias en memoria del vector). Para poder hacerlo se quiere crear un vector de índices 
Ind[1..N] de tal manera que el valor Ind[i] sea precisamente la posición del vector 
original con el dato que debería estar en la posición i si efectivamente estuviese 
ordenado. 
 
 
 
 
 
 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
Pág. 3 / 5 
 
 
50 98 10 63 31 25 63 74 
 
3 6 5 1 4 7 8 2 
 
 
 
Por ejemplo, si el vector V[1..N] fuese 
 
1 2 3 4 5 6 7 8 
V 
 
entonces el vector de índices Ind[1..N] sería 
 
1 2 3 4 5 6 7 8 
Ind 
 
ya que Ind[1] = 3 es la posición de V donde está 10, que es el elemento que quedaría 
primero si se ordenase V, Ind[2] = 6 es la posición de 25, que sería el segundo 
elemento en el vector ordenado, etc. 
 
Modificar el algoritmo de ordenación por mezcla Mergesort para obtener el vector de 
índices de un vector V[1..N] dado como parámetro. 
 
Ejercicio 6) 
Tras su paso por la Sala de las Baldosas y conseguir la Cuna de la Vida, ahora Indiana 
Croft se enfrenta a un nuevo desafío antes de poder salir del Templo Maldito. Se encuentra 
en un puente bajo el que se observa una profunda oscuridad. 
 
Afortunadamente, este lugar también aparece en el diario. El puente cruza el llamado Valle 
de Sombras, que empieza con una
pendiente de bajada (la pendiente no es necesariamente 
constante) para después de llegar al punto más bajo empezar a subir hasta el otro extremo 
del puente (de nuevo, no necesariamente con pendiente contante). Justo en la parte inferior 
del valle hay un río, pero el diario no especifica su ubicación con respecto al puente (por 
ejemplo, no se sabe si el río está a 53 metros desde el comienzo del puente) ni la distancia 
en altura (es decir, no se sabe si el río está 228 metros por debajo, por ejemplo). En las 
pendientes hay afiladísimas rocas. 
 
Si Indiana Croft tuviese tiempo, podría encontrar sin problema el punto por donde 
descolgarse del puente para llegar exactamente al río, ya que tiene un puntero laser para 
medir alturas que le dice cuántos metros hay desde el puente hasta el suelo en un punto 
determinado. El problema es que los sacerdotes del templo han averiguado que les han 
robado la Cuna de la Vida, están persiguiendo a Indiana Croft y le alcanzarán enseguida. El 
aventurero debe encontrar rápidamente la posición del río para descolgarse y huir seguro. 
 
Diseñar el algoritmo que debería usar Indiana Croft para buscar el punto mínimo del valle 
en las condiciones indicadas. El algoritmo debe ser eficiente: al menos en el mejor caso 
debe tener un orden logarítmico. Se puede considerar el tiempo que tarda Indiana Croft en 
desplazarse a lo largo del puente es nulo y que la estimación del punto del río por donde 
descolgarse puede tener un error de aproximación de  metros ( es una constante dada). 
 
 
 
 
 
 
 
 
 
 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
Pág. 4 / 5 
 
 
 
Ejercicio 7) 
En Abecelandia, ciudad famosa por sus N bellas plazas, tienen un curioso sistema de 
carreteras: desde cada plaza sale una calle a todas las otras plazas que comienzan con una 
letra que se encuentre en su nombre (por ejemplo, de la plaza Aro salen calles que llevan 
a las plazas que empiezan por R, como las plaza Ruido y Reto, o por O, como la plaza 
Osa, pero no salen calles a plazas como Duende, Cascada o Tiara). Las calles son de 
sentido único (de la plaza Aro se puede ir a la plaza Ruido, pero no al revés ya que no 
cumple la regla de las letras; obviamente, otras plazas como Aro y Osa están conectadas 
entre sí en ambas direcciones). Todas estas conexiones entre las N plazas están recogidas en 
un callejero, representado por una matriz de adyacencia de tamaño NxN; así, el valor de 
Callejero[p, q] indica si se puede ir de la plaza p a la plaza q. 
 
Se acerca el día 26 de Abril, festividad de San Isidoro de Sevilla (patrón de las 
Letras y, casualmente, de los informáticos), y en el Ayuntamiento de Abecelandia han 
decidido que para celebrarlo van a invertir la dirección de todas las calles que conectan sus 
plazas. En ese día no se podrá circular de Aro a Ruido, pero sí se permitirá ir de Ruido a 
Aro; obviamente, Aro y Osa seguirán conectadas entre sí. 
 
Diseñar formalmente un algoritmo Divide y Vencerás estándar que, teniendo por 
dato el callejero de la ciudad (representado por la matriz de adyacencia), obtenga el nuevo 
callejero válido para el día de San Isidoro de Sevilla, indicando las estructuras de datos que 
se utilicen. 
Ejercicio 8) 
Ejercicio 9) 
Se tiene una cadena de texto de longitud conocida (puede considerarse que no hay una 
longitud máxima determinada, o usar un valor constante TamMax) que está compuesta por 
caracteres alfanuméricos ya ordenados de manera lexicográfica; por ejemplo, la cadena: 
 aabeeeeffhkklmmmmmmpqqqrsszz 
Diseñar un algoritmo Divide y Vencerás que determine, de la manera más eficiente posible, 
si un carácter determinado (por ejemplo “p”) se encuentra en la cadena; los datos del 
algoritmo serán la cadena y el carácter. No importa la posición del carácter dentro de la 
cadena, únicamente si está o no está presente. 
 
 
 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
Pág. 5 / 5 
 
 
 
Ejercicio 10) 
En una empresa dedicada a los juegos de mesa han comprado una máquina para cortar 
imágenes pegadas sobre madera (la base puede suponerse cuadrada y con 2
N
 centímetros de 
lado) en piezas y venderlas como puzzles. Como novedad en el sector de los puzzles, se 
quiere utilizar cada imagen para una tirada limitada y numerada de puzzles, todos distintos 
entre sí. 
Para lograr este objetivo, la máquina de cortar puzzles debe tener un patrón de la 
descomposición de las piezas que forman la imagen. Para generar este patrón, el creador de 
los puzzles ha decidido el siguiente esquema: se selecciona automáticamente una única 
pieza de 1x1 centímetros, que será diferente para cada puzzle con la misma imagen (así se 
aseguran de que todos los puzzles sean distintos), y el resto de piezas tendrán una forma de 
“L” de manera que los lados “largos” de la pieza midan 2 centímetros y los lados “cortos” 
midan 1 centímetro. Cada pieza recibe un código numérico distinto para su representación 
en el patrón que se le tiene que pasar a la máquina cortadora. 
Diseñar un algoritmo eficiente que, teniendo como datos el valor N y la posición de la pieza 
de tamaño 1x1 centímetros dentro de la imagen, genere el patrón de piezas para la máquina 
de cortar puzzles. 
Teoría/Tema 2/resumen_Divide_y_Venceras.pdf
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 1 / 2 
 
DIVIDE Y VENCERÁS 
ESQUEMA BÁSICO DE LA METODOLOGÍA DIVIDE Y VENCERÁS 
proc DyV (E X: TipoProblema; E/S Y: TipoSolucion) 
var subproblemas : array[1..k] de TipoProblema 
 subsoluciones: array[1..k] de TipoSolucion 
 bucle: 1..k 
 if CasoBasico(X) entonces 
 Y ← Solucion(X) 
 si no 
 Dividir(X, subproblemas) 
 Desde bucle ← 1 hasta k Hacer 
 DyV (subproblemas[bucle], subsoluciones[bucle]) 
 fdesde 
 Combinar(subsoluciones, Y) 
 fsi 
fproc 
 
EXPONENCIACIÓN DE ENTEROS (POSITIVOS): 
ENFOQUE SECUENCIAL 
fun Exposec (E a, n: entero) dev r: entero 
var aux, i: entero 
 aux ← 1 
 Desde i ← 1 hasta n Hacer 
 aux ← aux * a 
 fdesde 
 
ffun 
Devolver aux 
 
EXPONENCIACIÓN DE ENTEROS (POSITIVOS): 
ENFOQUE DIVIDE Y VENCERÁS 
fun ExpoDyV (E a, n: entero) dev r: entero 
 si (n = 1) entonces 
 Devolver a 
 si no 
 si (n es par) entonces Devolver [ExpoDyV (a, n ÷ 2)]2
 si no Devolver a * [ExpoDyV (a, n - 1)] 
 fsi 
 fsi 
ffun 
 
Universidad de Alcalá 
Departamento de Ciencias de la Computación 
Algoritmia y Complejidad 
Grado en Ingeniería Informática 
 
Jesús Lázaro García Pág. 2 / 2 
 
DIVIDE Y VENCERÁS 
EXPONENCIACIÓN DE ENTEROS (POSITIVOS): 
VERSIÓN ITERATIVA DEL ENFOQUE DyV 
fun Expoiter (E a, n: entero) dev r: entero 
var i, r, x: entero 
 i ← n 
 r ← 1 
 x ← a 
 Mientras i > 0 Hacer 
 si i es impar entonces 
 r ← r * x 
 fsi 
 x ← x2
 ← ÷ 2 i i 
 fmientras 
 Devolver r 
ffun 
 
EJEMPLO: PROBLEMA DE EXAMEN 2011/2012 
P.1. Buscando el equilibrio: Se tiene acceso a dos funciones, denominadas 
subir(x), que es una función monótona creciente, y bajar(x), que es monótona 
decreciente. El objetivo del problema es encontrar, de la manera más eficiente 
posible, todos los puntos en el intervalo de números reales [p1, p2] en los que las dos 
funciones toman el mismo valor, es decir, hay que encontrar el conjunto de valores 
{x ∈ [p1, p2] tales que subir(x) = bajar(x)}. 
 Para simplificar el proceso, en vez del valor exacto de cada posible punto x puede 
indicarse un intervalo de valores [α, β], con β – α < ε, donde se encuentre x. Los 
datos del algoritmo serán los extremos del intervalo [p1, p2], y el valor ε para la 
aproximación. (3 puntos) 
 
Teoría/Tema 2/Teoria_02a_DyV_transparencias.pdf
Tema 2. Algoritmos Divide y Vencerás.
1 
 El coste de realizar las operaciones elementales de 
suma y multiplicación es razonable considerarlo 
constante si los operandos son directamente 
manipulables por el hardware, es decir, no son muy 
grandes. 
 
 Pero si se necesitan enteros muy grandes, hay que 
implementar por software las operaciones. 
 
2 
 
Enteros muy grandes: 
– La representación de un entero de n cifras puede hacerse en 
un vector con un espacio en O(n) bits. 
– Operaciones de suma, resta: pueden hacerse en tiempo 
lineal. 
– Operaciones de multiplicación y división entera por potencias 
positivas de 10: pueden hacerse en tiempo lineal 
(desplazamientos de las cifras). 
– Operación de multiplicación con el algoritmo clásico (o con el 
de multiplicación rusa): tiempo cuadrático. 
 
3 
4 
5 
6 
7 
8 
9 
 
– La diferencia entre los órdenes n2 y n1,59 es 
menos espectacular que la existente entre 
n2 y n log n. 
 
– Descomponiendo los operandos en más de 
dos partes se puede lograr la multiplicación 
de dos enteros en un tiempo del orden de 
na , para cualquier a>1. 
 
 
 
- Descomponer el caso a resolver en subcasos 
más pequeños del mismo problema. 
- Resolver independientemente cada subcaso. 
- Combinar los resultados para construir la 
solución del caso original. 
 
Este proceso se suele aplicar recursivamente. 
 
La eficiencia de esta técnica depende de cómo se 
resuelvan los subcasos. 
 
 
10 
 
Esquema en 3 etapas: 
 
División. Divide el problema original en k subproblemas 
de menor tamaño 
 
Conquistar. Estos subproblemas se resuelven 
independientemente: 
◦ Directamente si son simples. 
◦ Reduciendo a casos más simples (típicamente de forma 
recursiva) 
 
Combinar. Se combinan sus soluciones parciales para 
obtener la solución del problema original. 
 
 El caso más frecuente: k=2 
 
 
11 
 
funcion DivideYVenceras (c: tipocaso) : tiposolucion; 
 var 
 x1,..., xk : tipocaso; 
 y1,...,yk: tiposolucion; 
 si c es suficientemente simple entonces 
 devolver solucion_simple(c) 
 sino 
 descomponer c en x1, ..., xk 
 para i← 1 hasta k hacer 
 yi ← DivideYVenceras (xi) 
 fpara 
 devolver combinar_solucion_subcasos(y1, ..., yk) 
 fsi 
ffuncion 
 
 
12 
 
 El número de subejemplares, k, suele ser 
pequeño e independiente del caso particular a 
resolver. 
 Cuando k = 1, el esquema divide y vencerás pasa a 
llamarse reducción o simplificación. 
 Algunos algoritmos de divide y vencerás pueden 
necesitar que el primer subejemplar esté resuelto 
antes de formular el segundo subejemplar. 
 
13 
 
 Para que el enfoque divide y vencerás 
merezca la pena, se deben cumplir las siguientes 
condiciones: 
 
 Debe ser posible descomponer el caso a resolver 
en subcasos. 
 La formulación recursiva nunca resuelva el mismo 
subproblema más de una vez. 
 Se debe poder componer la solución a partir de 
las soluciones de los subcasos de un modo eficiente. 
 Los subejemplares deben ser, aproximadamente, del 
mismo tamaño. 
 
14 
 
 El umbral será un n0 tal que cuando el 
tamaño del caso a tratar sea menor o 
igual, se resuelva con un algoritmo 
básico, es decir, no se generen más 
llamadas recursivas. 
 La determinación del umbral óptimo, 
es un problema complejo. 
 Dada una implementación particular, 
puede calcularse empíricamente. 
 
 
15 
 
También puede emplearse una técnica híbrida para 
su cálculo: 
 
 Obtener las ecuaciones de recurrencia del algoritmo 
(estudio teórico). 
 Determinar empíricamente los valores de las 
constantes que se utilizan en dichas ecuaciones para 
la implementación concreta que estamos empleando. 
 El umbral óptimo se estima hallando el tamaño n del 
caso para el cual no hay diferencia entre aplicar 
directamente el algoritmo clásico o pasar a un nivel 
más de recursión. 
 
16 
17 
 
Sea n el tamaño de nuestro caso original y sea k el 
número de subcasos: 
Existe una constante b tal que el tamaño de los k subcasos 
es aproximadamente n/b 
 
Si g(n) es el tiempo requerido por el algoritmo divide y vencerás en 
casos de tamaño n, sin contar el tiempo necesario para realizar 
las llamadas recursivas ⇒ 
 
 t(n) = k*t(n/b) + g(n) 
 
Donde t(n) es el tiempo total requerido por el algoritmo divide y 
vencerás, siempre que n sea lo suficientemente grande. 
 
 
18 
19 
 
 Sea T[1..n] un vector ordenado tal que 
 T[j] ≥ T[i] siempre que n ≥ j ≥ i ≥ 1 
 y sea x un elemento. 
 
 El problema consiste en buscar x en T. 
 Es decir, queremos hallar un i tal que 
 n ≥ i ≥ 1 y x = T[i], si x ∈ T. 
 
 
 
20 
 
 El algoritmo secuencial de búsqueda estará en el 
orden de O(n). 
 
método búsquedaSecuencial(entero[1..n] t, entero x) 
 desde i:=1 hasta n hacer 
 si t[i] = x entonces 
 retorna i // encontrado 
 fsi 
 fhacer 
 retorna -1 // no encontrado 
fmétodo 
 
 
 
 
21 
 
Identificación del problema con el esquema 
 
 División: El problema se puede descomponer en 
subproblemas de menor tamaño (k = 1). 
 Conquistar: No hay soluciones parciales, la 
solución es única. 
 Combinar: No es necesario. 
 
 
 
 
22 
23 
 
Pasos del algoritmo de búsqueda binaria: 
 
 Se compara x con el elemento que está en k= 
(i+j)/2 
 Si T[k] ≥ x la búsqueda continúa en T[i..k] 
 Si T[k] < x la búsqueda continúa en T[k+1..j] 
 Estos pasos continuarán hasta localizar x, o 
determinar que no está en T. 
 
 
 
24 
 
método búsquedaBinaria(entero[1..n] t, entero i, entero j, entero x) 
 // calcula el centro 
 k := (i + j)/2 
 // caso directo 
 si i > j entonces 
 retorna -1 // no encontrado 
 fsi 
 si t[k] = x entonces 
 retorna k // encontrado 
 fsi 
 // caso recursivo 
 si x > t[k] entonces 
 retorna búsquedaBinaria(t, k+1, j, x) 
 sino 
 retorna búsquedaBinaria(t, i, k-1, x) 
 fsi 
fmétodo 
 
 
25 
26 
 
 Dado un vector T[1..n], inicialmente 
desordenado, lo ordenaremos aplicando la 
técnica de Divide y Vencerás partiendo el 
vector inicial en dos subvectores más 
pequeños. 
 
 Utilizaremos dos técnicas: 
 
 Ordenación por mezcla (mergesort) 
 Ordenación rápida (quicksort) 
27 
 
Identificación del problema con el esquema: 
 
 División: El problema se puede descomponer en 
subproblemas de menor tamaño (k = 2) 
 Conquistar: Los subvectores se siguen dividiendo 
hasta alcanzar un tamaño umbral. 
 Combinar: Dependerá del tipo de algoritmo. 
 
28 
 
Pasos del Algoritmo: 
 
1. Dividir el vector en dos mitades 
2. Ordenar esas dos mitades 
recursivamente 
3. Fusionarlas en un solo vector 
ordenado. 
 
29 
30 
31 
32 
33 
 
Pasos del Algoritmo: 
 
 Escoger un elemento de la matriz a 
ordenar como pivote. 
 Se parte el vector a ambos lados del pivote. 
Los elementos mayores que el pivote se 
almacenan a la derecha del mismo y los 
demás a la izquierda. 
 El vector se ordena mediante llamadas 
recursivas a este algoritmo. 
 
 
34 
 
Selección del pivote: 
 Cualquier elemento es válido, lo más 
sencillo es escoger el que ocupa la 
primera posición del subvector. 
 
Mejor pivote: 
 La mediana. 
 
35 
 
procedimiento pivote (T[i..j]; var b) 
 p ← T[i] 
 k ← i 
 b ← j + 1 
 repetir 
 k ← k + 1 
 hasta que T[k] > p o k >= j frepetir 
 repetir 
 b ← b – 1 
 hasta que T[b] <= p frepetir 
 mientras k < b hacer 
 intercambiar T[k] y T[b] 
 repetir 
 k ← k + 1 
 hasta que T[k] > p frepetir 
 repetir 
 b ← b – 1 
 hasta que T[b] <= p frepetir 
 fmientras; 
 intercambiar T[i] y T[b] 
fprocedimiento 
36 
 
procedimiento ordenacion_rapida(T[i..j]) 
 {Ordena la submatriz T[i..j]
por orden no decreciente} 
 si j – i es suficientemente pequeño entonces 
 ordenar (T[i..j]) {P.ej., Ord. por inserción} 
 sino 
 pivote(T[i..j],b); 
 ordenacion_rapida (T[i..b-1]); 
 ordenación_rapida (T[b+1..j]); 
 fsi 
fprocedimiento 
 
37 
Coste: 
-Si partimos de la hipótesis de que todos 
los elementos de T son diferentes ⇒ las n! 
permutaciones tienen la misma probabilidad. 
-El valor b devuelto por pivote(T[1..n],b) será 
un entero entre 1 y n con probabilidad 1/n. 
-pivote(T[1..n],b) requiere un tiempo g(n)∈Θ(n). 
 
38 
 
 Si suponemos que: 
 
 El orden inicial del vector es aleatorio 
 Los elementos de T son diferentes en su mayoría 
 Todas las n! permutaciones de sus elementos 
son igualmente probables 
 Los subproblemas estarían equilibrados 
 
 El orden sería: O(n log n). 
 
 Aunque los subproblemas no estén del todo 
equilibrados se suele asumir que el coste es O(n 
log n) 
 
Teoría/Tema 2/Teoria_02b_DyV_transparencias PARTE2.pdf
Tema 2. Algoritmos Divide y Vencerás. 
(2ª parte.) 
1 
Problema de la Selección: Encontrar el k-ésimo elemento 
mayor o menor en una lista de n números (cálculo de los 
estadísticos de orden) 
Caso particular: Encontrar la mediana [k=n/2]. 
 Dado un vector T[1..n] de enteros, la mediana de T es 
un elemento m de T que tiene tantos elementos menores 
como mayores que él en T. (nótese que la definición formal 
es más general porque n puede ser par y además puede 
haber elementos repetidos). 
Primera solución: Ordenar T y extraer el elemento [n/2]-
ésimo. Su coste: O(nlog n), el de la ordenación. 
 
2 
 
Dado un vector T de n elementos y 1<=k <=n, el 
k-ésimo menor elemento de T es aquel elemento 
m de T que ocupa la posición k si T estuviese 
ordenado crecientemente. 
 
Por tanto, la mediana de T es el [n/2] -ésimo 
menor elemento de T. 
 
Solución del problema: Inspirada en el algoritmo 
de ordenación Quicksort (pero ahora sólo se 
resuelve uno de los subejemplares). 
 
 
 
3 
Algoritmo DyV: 
 Se elige un valor como “pivote” 
 Se reorganiza la tabla en dos partes, una con los 
elementos mayores que el pivote y otra con los 
elementos menores (la clave estará en la 
selección correcta del pivote). 
 Se realiza de nuevo el proceso sobre la parte de 
la tabla que contiene el elemento buscado. 
4 
La función select llama a selectRec con los parámetros 
iniciales. 
Retorna el elemento del array t que ocuparía la posición 
k-ésima en el caso de que el array estuviera ordenado 
(la primera posición es la 1, no la 0). 
 
Función select(int[] t, int ini, int fin, int k) Devuelve int. 
{ 
 return selectRec(t,ini,fin,k); 
} 
5 
La función selectRec es la que realmente implementa el 
algoritmo recursivo DyV. 
Retorna el elemento de la parte del array t comprendida 
entre los índices ini y fin que ocuparía la posición k-
ésima (en esa parte) en el caso de que esa parte 
estuviera ordenada. 
ini es el índice inicial de la parte de t utilizada. 
fin es el índice final de la parte de t utilizada. 
 
6 
Función selectRec(int[] t, int ini, int fin, int k) Devuelve int { 
 // caso directo 
 if (ini == fin) { 
 return t[ini]; // elemento en la pos. k-ésima 
 } 
 // reorganiza los elementos y retorna la posición 
 // del último elemento menor que el pivote 
 int p = reorganiza(t, ini, fin); 
 int k1 = p - ini + 1; 
 // offset del primer elemento mayor que el pivote 
 // divide 
 if (k <= k1) { 
 return selectRec(t,ini,p,k); 
 } else { 
 return selectRec(t,p+1,fin,k-k1); 
 } 
} 
7 
Reorganiza: Permuta los elementos de la parte de t comprendida 
entre los índices ini y fin en dos partes, una con los elementos 
mayores que el pivote y otra con los menores: 
ini<=m<=fin; 
 para todo k tal que ini<=k<m entonces T[k]<=x; T[m]=x; 
 para todo k tal que m<k<=fin entonces T[k]>x; 
Donde x (pivote) es, por ejemplo, el valor inicial de T[ini]. 
ini es el índice inicial de la parte de t utilizada. 
fin es el índice final de la parte de t utilizada. 
Devuelve el índice del último elemento menor que el pivote 
8 
funcion reorganiza(int[] t, int ini, int fin) Devuelve int { 
 int x=t[ini]; // usa el primer ele. como pivote 
 int i=ini-1; int j=fin+1; 
 while (true) { 
 do { // busca ele. menor o igual que el pivote 
 j--; 
 }while (t[j]>x); 
 do { // busca ele. mayor o igual que el pivote 
 i++; 
 } while (t[i]<x); 
 if (i < j) { 
 int z=t[i]; t[i]=t[j]; t[j]=z; // intercambio 
 } else { 
 return(j); 
 } 
 } 
} 
9 
10 
11 
La eficiencia mejora si somos capaces de modificar 
reorganiza para que elija un buen pivote: 
• que divida aproximadamente a la mitad el vector 
• y cuya búsqueda se realice en un tiempo aceptable (p.e. O(n)) 
• el tiempo de ejecución de reorganiza seguirá siendo O(n). (O(n) 
para encontrar el pivote, más O(n) para reordenar). 
 
En ese caso el tiempo de ejecución del algoritmo de 
selección será: 
 t(n) = t(n/2) + O(n) con (s=1, b=2 y k=1) 
Estamos en el caso s<bk (1<21) luego t(n) es O(nk) = O(n) 
12 
 
El pivote ideal sería la mediana de los elementos de la tabla ya que es 
el elemento que utilizado pivote divide a la tabla en dos mitades, pero 
su cálculo es demasiado complejo. 
En su lugar se utiliza la pseudo-mediana, que es un valor cercano a la 
mediana que puede calcularse en O(n). 
Cálculo de la pseudo-mediana: 
 Se divide la tabla en grupos de r elementos (puede demostrarse que 
un valor apropiado de r es 5). 
 Para cada grupo se calcula su mediana exacta. 
 Se obtiene la mediana de las medianas utilizando el algoritmo de 
selección recursivamente. 
13 
Función pseudomediana(entero[0..n-1] t, entero ini, entero fin) 
Devuelve entero{ 
 nGrupos := (fin-ini+1)/r; 
 // un valor apropiado de r es 5. "/" es la división entera 
 //Los restantes "(fin-ini+1)%r" elemen. no se consideran 
 // calcula medianas 
 desde i:=0 hasta nGrupos-1 hacer 
 medGrupo[i]:=calculaMediana(t[r*i+ini] .. t[r*(i+1)+ini-1]); 
 fhacer 
 // calcula la mediana de las medianas 
 retorna select(medGrupo, 0, nGrupos-1,nGrupos/2) 
} //hay que modificar reorganiza para que utilice esta función. 
14 
15 
Dados los enteros positivos a y n, se trata de calcular an. 
 
Solución ingenua: 
 
función pot0(a,n:entero) devuelve entero 
 variables r,i:entero 
 principio 
 r:=1; 
 para i:=1 hasta n hacer 
 r:=r*a 
 fpara; 
 devuelve r; 
 Fin 
 
16 
 Si “r:=r*a” se considera “operación elemental”, el 
coste está en O(n). 
Pero NO es así (p.e., 1517 no cabe en 8 bytes). 
 
 Como “r:=r*a” no es elemental, el inconveniente de 
esta solución es su coste (el bucle se ejecuta n veces). 
Si se quiere aplicar a un entero a grande (de m cifras), 
el coste es prohibitivo. 
 
17 
18 
 
 Sean a y n 2 enteros. Si m es el tamaño de a, 
la operación an, 
 
 Si se utiliza el algoritmo clásico de la 
multiplicación el coste es polinómico: 
O(m2n2) 
 
 Usando el algoritmo divide y vencerás, el 
coste se reduce a: O(mlog3n2) 
19 
 
 cada x por un 1 y cada 1 por un 0, se 
obtiene la secuencia de bits 11001 (expresión 
binaria de 25). 
 
 En otras palabras, 
 
 x25=x24x ; x24=(x12)2; etc. 
 
20 
21 
22 
 
 Sean A y B dos matrices de tamaño n x n, se 
desea calcular su producto aplicando el método de 
divide y vencerás. 
 
 Dos aproximaciones: 
 
-Cuando n es potencia de 2 
-Cuando n no es potencia de 2: Añadir filas 
y columnas de ceros hasta que lo sea. 
 
23 
24 
25 
26 
27 
28 
29 
30 
Identificación del problema con el esquema: 
 
 División: El problema se puede descomponer en 
subproblemas de menor tamaño (k = 4). 
 Conquistar: Los submatrices se siguen 
dividiendo hasta alcanzar un tamaño 1. 
 Combinar: sumar los resultados intermedios. 
 
31 
32 
33 
34 
35 
36 
Según algunos estudios