Análisis y Diseño de Algoritmos

Lenguajes y Ciencias
de la Computación

E.T.S.I. Informática

1
¿Qué vamos a hacer? - Guia
❑ “Estudiar como se estudia” la complejidad de los
algoritmos.
⚫ ¿Cómo?
⚫ Ejemplos y problemas

❑ Aplicaremos lo que aprendamos a las distintas técnicas

de diseño a lo largo del curso.
❑ Y también a las clases de complejidad que veremos en
la última parte de este tema
Organización de este tema

❑ Algoritmia elemental.

❑ Notación asintótica.

❑ Ecuaciones de recurrencia.

❑ Clases de complejidad
Algoritmia Elemental
❑ Recursos que requiere un algoritmo.

E/S

ALGORITMO
Una ó más Una ó más
entradas salidas
Algoritmia Elemental
❑ Diferentes algoritmos para un mismo problema. ¿Cual utilizar?
❑ Factores: facilidad de programación, claridad, robustez, .... , y por
supuesto el criterio empresarial de eficiencia: relación entre los
recursos consumidos y los productos conseguidos.
Algoritmo Recursos (Var a: vector [1..n] de
< tipo_elemento>; x : entero);
Var i: entero; ¿cuántos recursos de
Inicio tiempo y memoria
i:= 0; consume este algoritmo?
a[n]:= x;
repetir ¿qué hace este
i:= i + 1; algoritmo?
hasta a[i] = x;
Devolver (i);
Fin
Algoritmia Elemental
❑ Factores de los que dependen los recursos necesarios:
⚫ Internos:
✓ Tamaño de la entrada.
✓ Naturaleza de los datos de entrada.
⚫ Externos:
✓ Tipo de ordenador.
✓ Lenguaje de programación.
✓ Implementación

❑ Los factores externos no aportan información sobre el algoritmo.

Algoritmia Elemental
❑ Necesitamos una medida para cuantificar el tiempo.
⚫ Segundos, milisegundos ...
⚫ Operación elemental.
❑ Definición. Una operación elemental es aquella operación mínima
posible cuyo tiempo de ejecución se puede acotar superiormente por
una constante que solamente dependerá de la implementación
particular usada: los factores externos. De esta manera la constante
no dependerá ni del tamaño, ni de la naturaleza de los datos de
entrada del ejemplar que se esté considerando.
❑ Sólo el número de operaciones elementales ejecutadas importará en
el análisis, y no el tiempo exacto requerido por cada una de ellas.
⚫ Que será dependiente de los factores externos
❑ Ejemplos de operaciones elementales: operaciones aritméticas,
asignación, acceso a arrays, ... .
Algoritmia Elemental

❑ Principio de Invarianza. Dos implementaciones distintas de un mismo

algoritmo no diferirán en su eficiencia en más de una constante
multiplicativa.

❑ Dicho de otra manera, el principio de Invarianza quiere decir que si

dos implementaciones de un mismo algoritmo para resolver un
problema de tamaño n tardan respectivamente t1(n) y t2(n), entonces
siempre van a existir unas constantes positivas c y d tales que: t1(n)
≤ ct2(n) y t2(n) ≤ dt1(n), para todo n>n0.
Algoritmia Elemental
❑ Eficiencia de un algoritmo en función de la naturaleza de los datos
de entrada.
⚫ Análisis en el Peor de los Casos.
✓ Máximo coste de aplicar el algoritmo a un problema de tamaño n.
⚫ Análisis en el Caso Medio.
✓ Media (calculada en función de la probabilidad de la ocurrencia de las
entradas) de las complejidades del algoritmo con todas las entrada/s de
tamaño n
⚫ Análisis en el Mejor de los Casos.
✓ Mínimo coste de aplicar el algoritmo a un problema de tamaño n.
Algoritmia Elemental
❑ Eficiencia.
⚫ Diferentes algoritmos para un problema.
⚫ Enfoque empírico: Mide exactamente el tiempo de ejecución. A posteriori.
⚫ Enfoque teórico. A priori. Calcula una función que determina el tiempo
de ejecución en función del tamaño de los datos de entrada y el valor de
los mismos.
Algoritmia Elemental
❑ Supongamos un algoritmo que resuelve un problema haciendo uso de
2n operaciones elementales.
❑ Supongamos otro algoritmo que resuelve el mismo problema en n3
operaciones elementales.
❑ Supongamos tres ordenadores distintos
⚫ Computador 1 realiza 100 o.e/seg (10-2)
⚫ Computador 2 realiza 10k o.e/seg (10-4)
⚫ Computador 3 realiza 1M o.e/seg (10-6)
Algoritmia Elemental
Para un problema de tamaño 20
❑ Algoritmia frente a hardware. el algoritmo tardaría 10-4220 
104.85 (cerca de 2 minutos).
 Con una máquina 100 veces más
rápida. Problema de tamaño 39
Algoritmia Elemental tardaría 407’2 días.

❑ Algoritmia frente a hardware.

Algoritmia Elemental
❑ Algoritmia frente a hardware.
Con la máquina más lenta. Con
un año de computo podríamos
alcanzar un tamaño de 350.
Notación Asintótica
❑ El análisis asintótico pone de manifiesto cómo aumenta en el límite el
tiempo de ejecución, en función del aumento del tamaño de la
entrada.

⚫ Es decir “lo deprisa que crece el tiempo de ejecución necesario cuando

aumenta el tamaño de los datos de entrada”

❑ Realiza una simplificación.

❑ Se denomina notación asintótica porque trata acerca del
comportamiento de funciones en el límite de n→∞, es decir, para
valores suficientemente grandes de su parámetro.
❑ La notación asintótica clasifica las funciones de tiempo de los
algoritmos para que puedan ser comparadas.
Notación Asintótica.
❑Cota superior. Notación O.
❑ Tiene sentido en el análisis del peor caso
❑ Es la encargada de determinar las acotaciones superiores lo más exactamente
posible para valores crecientes de la entrada.
❑ Definición. Sea f:  →[0,), se define el conjunto de funciones de orden
O de f como:

O(f) ={g:  → [0,) /  c  , c > 0,  n0, de manera que, g(n) cf(n)

 n  n0}

❑ Diremos que una función g:  → [0,) es de orden O de f si gO(f).

gO(f) indica que g está acotada superiormente por algún múltiplo de f.

Big O

¿g ∈ 𝑂 𝑓 ?
Notación Asintótica
❑ Ejemplo. Comprobar que t(n) = 3n2 + 2n –5 es de orden de O(n2).
⚫ Para ello tenemos que comprobar que 3n2 + 2n –5  c n2 .
⚫ Solución. 3n2 + 2n –5  5 n2. Entonces diremos que t(n) es de O(n2).
❑ Gráficamente.

¿t(n) ∈ 𝑂 𝑛3 ?
Notación Asintótica
❑ Propiedades de O.

⚫ Para cualquier función f se tiene que f  O(f).

⚫ f  O(g) O(f)  O(g).
⚫ O(f) = O(g)  f  O(g) y g  O(f).
⚫ Si f  O(g) y g  O(h) f  O(h).
⚫ Regla de la Suma: Si f1  O(g) y f2  O(h) f1 + f2 O(max(g, h)).
⚫ Regla del Producto: Si f1  O(g) y f2  O(h) f1  f2 O(g h).
⚫ Si lim f(n)/g(n)  + cuando n → entonces O(f) = O(g).
⚫ Si lim f(n)/g(n) = 0 cuando n → entonces O(f)  O(g).
Notación Asintótica
❑ Propiedades de O. f (n) = n; g (n) = n 2 ; h(n) = n3

⚫ Para cualquier función f se tiene que f  O(f).

⚫ f  O(g) O(f)  O(g).
⚫ O(f) = O(g)  f  O(g) y g  O(f).
⚫ Si f  O(g) y g  O(h) f  O(h).
⚫ Regla de la Suma: Si f1  O(g) y f2  O(h) f1 + f2 O(max(g, h)).
⚫ Regla del Producto: Si f1  O(g) y f2  O(h) f1  f2 O(g h).
⚫ Si lim f(n)/g(n)  + cuando n → entonces O(f) = O(g).
⚫ Si lim f(n)/g(n) = 0 cuando n → entonces O(f)  O(g).
Conteo de operaciones
❑ Reglas para operar con O.
⚫ Operaciones elementales O(1).
✓ Operaciones aritméticas, de comparación, de acceso a memoria, etc.
⚫ Regla de la suma.
⚫ Bucle Para.
Para índice = expresión1 To expresión2 By expresión3 Do Cuerpo

æê expresión - expresión ú ö
t ( n) = t ( expresión1 ) + ( t ( expresión 2 ) + t ( expresión3 ) + t ( cuerpo)) × ççê 2 1
ú +1÷÷
èë expresión 3 û ø

⚫ Ejemplo: for (i=1;i<=n;i++) printf(“%d”,i);

⚫ Respuesta: t(for)=1+(1+2+1)*(((n-1)/1)+1)=1+4*n
Conteo de operaciones
⚫ Los bucles Mientras y Repite se tratan de forma similar.
Mientras expresión1 do cuerpo;

t (n) = (t (expresión 1 ) + t (cuerpo))  H + t (expresión 1 )

H=nº de veces que se ejecuta el bucle

⚫ Llamada a procecimientos no recursivos.

t (n) = t ( procedure) + 1

⚫ Llamada a procedimientos recursivos. Ecuaciones de recurrencia.

𝑡 𝑛 =𝑡 𝑛−3 +1
Notación Asintótica
❑Cota Inferior. Notación .
❑ Tiene sentido en el análisis del mejor caso
❑ Es la cota que determina acotaciones inferiores lo más exactamente
posibles para valores crecientes de la entrada.
❑ Definición. Sea f: →[0,), se define el conjunto de funciones de
orden  de f como:
 (f) ={g:  →[0,) /  c, c > 0,  n0, de manera que,
g(n)  cf(n)  n  n0}
❑ Diremos que una función g:  →[0,) es de orden  de f si g   (f).
g   (f) indica que g está acotada inferiormente por algún
múltiplo de f.
Notación Asintótica
❑ Propiedades de . f ( n) = n 3 ; g ( n) = n 2 ; h( n) = n

⚫ Para cualquier función f se tiene que f   (f).

⚫ f   (g)  (f)   (g).
⚫  (f) =  (g)  f   (g) y g   (f).
⚫ Si f   (g) y g   (h) f   (h).
⚫ Regla de la Suma: Si f1   (g) y f2   (h) f1 + f2  (max(g,h)).

⚫ Regla del Producto: Si f1   (g) y f2   (h) f1  f2  (g h).

⚫ Si lim f(n)/g(n)  + cuando n → entonces  (f) =  (g).
⚫ Si lim f(n)/g(n) = 0 cuando n → entonces  (g)  (f).
Notación Asintótica
❑Orden Exacto. Notación .
❑ Es común que cuando se analiza un algoritmo nos encontremos que
su tiempo de ejecución está acotado tanto superior como
inferiormente mediante múltiplos reales positivos, posiblemente
distintos, de una misma función. Este hecho se denomina orden
exacto.
❑ Definición. Sea f:  →[0,), se define el conjunto de funciones de
orden  de f como:
(f) = O(f)   (f)
❑ Diremos que una función g:  →[0,) es de orden  de f si g (f).
g(f) indica que g está acotada tanto superior como
inferiormente por múltiplos de f, es decir que g y f crecen de
la misma forma.
Notación Asintótica
❑ Propiedades de . f (n) = 2n 2 ; g (n) = n 2 + n; h(n) = 45 n 2

⚫ Para cualquier función f se tiene que f  (f).

⚫  (f) =  (g)  f   (g) y g   (f).
⚫ Si f   (g) y g   (h) f   (h).
⚫ Regla de la Suma: Si f1   (g) y f2   (h) f1 + f2   (max(g,h)).

⚫ Regla del Producto: Si f1   (g) y f2   (h) f1  f2   (g h).

⚫ Si lim f(n)/g(n)  + cuando n → entonces  (f) =  (g).
Complejidad: comparando las complejidades
Notación Asintótica: propiedades
Complejidad en el caso peor y mejor de la Búsqueda
Secuencial
public class BusqSecuencial {
/**
* Búsqueda secuencial en un array de enteros
* @param a : array de elementos en el que buscar
* @param x : elemento buscado
* @return la posición del elemento en el array,
* si está, ó -1, si el elemento no está
*/
public static int busqSec(int[] a,int x){
int i = 0;
while (i<[Link] && a[i]!=x){
i++;
}
if (i<[Link]) return i;
else return -1;
}
}

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
6 2 8 3 5 7 9 0 1 4 6 2 8 3 5 7 9 0 1 4

6 4
¿Exáctamente? Peor caso
public class BusqSecuencial {
/**
* Búsqueda secuencial en un array de enteros
* @param a : array de elementos en el que buscar
* @param x : elemento buscado
* @return la posición del elemento en el array,
* si está, ó -1, si el elemento no está
*/
public static int busqSec(int[] a,int x){
int i = 0;
while (i<[Link] && a[i]!=x){
i++;
}
if (i<[Link]) return i;
else return -1;
}}

𝑇 𝑛 = 1 + 5 + 2 𝑛 + 1 = 7𝑛 + 2
Análisis de algoritmos no recursivos:
Ordenación por inserción
0 1 2 3 4 5 6
/** 6 2 8 3 5 7 9
*
* @param a array de enteros a
* ordenar por insercion 0 1 2 3 4 5 6
*/ 2 6 8 3 5 7 9
public static void insercion(int[] a){
for (int i = 1; i<[Link]; i++){ 0 1 2 3 4 5 6
// a[0..i-1] está ordenado
int j = i-1; 2 6 8 3 5 7 9
int x = a[i];
// insertamos a[i] en a[0..i-1] 0 1 2 3 4 5 6
// para que a[0..i] quede ordenado
2 3 6 8 5 7 9
while (j>=0 && a[j]>x) {
a[j+1]= a[j];
j--; 0 1 2 3 4 5 6
}
2 3 5 6 8 7 9
a[j+1]=x;
}
} 0 1 2 3 4 5 6
2 3 5 6 7 8 9

0 1 2 3 4 5 6
2 3 5 6 7 8 9
Análisis de algoritmos no recursivos:
Ordenación por inserción
❑ Tamaño de la entrada: longitud del array a ordenar n.
❑ Caso mejor: el array está ordenado
⚫ El cuerpo del bucle anidado no se ejecuta nunca

/**
*
* @param a array de enteros a
* ordenar por insercion
*/
public static void insercion(int[] a){
for (int i = 1; i<[Link]; i++){
// a[0..i-1] está ordenado
int j = i-1;
0 1 2 3 4 5 6
int x = a[i];
// insertamos a[i] en a[0..i-1] 2 3 5 6 7 8 9
// para que a[0..i] quede ordenado
while (j>=0 && a[j]>x) {
a[j+1]= a[j];
j--;
}
a[j+1]=x;

}
}
t (n )  (n )
Análisis de algoritmos no recursivos:
Ordenación por inserción
❑ Caso peor: el array está
ordenado de forma decreciente
⚫ El cuerpo del bucle anidado se
ejecuta siempre
0 1 2 3 4 5 6
/** 9 8 7 5 3 2 0
*
* @param a array de enteros a
* ordenar por insercion
*/
public static void insercion(int[] a){
for (int i = 1; i<[Link]; i++){
// a[0..i-1] está ordenado
int j = i-1;
int x = a[i];
// insertamos a[i] en a[0..i-1]
// para que a[0..i] quede ordenado
while (j>=0 && a[j]>x) {
a[j+1]= a[j];
j--;
}

}
}
a[j+1]=x;
( )
t (n )   n 2
Ordenación por inserción, peor caso. ¿Exactamente?
/** 𝑛−1 𝑖−1
*
* @param a array de enteros a 𝑇 𝑛 = 1 + ෍ (2 + 2 + 2 + 2 + ෍ 4 + 4 + 2 + 3) =
* ordenar por insercion 𝑖=1 𝑗=0
*/ 𝑛−1 𝑖−1
public static void insercion(int[] a){
for (int i = 1; i<[Link]; i++){ 1 + ෍ 11 + ෍ 10 =
// a[0..i-1] está ordenado 𝑖=1 𝑗=0
int j = i-1; 𝑛−1 𝑛−1
int x = a[i];
// insertamos a[i] en a[0..i-1] 1 + ෍ 11 + 10i = 1+ 11(n-1)+10 ෍ 𝑖 =
// para que a[0..i] quede ordenado 𝑖=1 𝑖=1
while (j>=0 && a[j]>x) { 𝑛−2 𝑛
a[j+1]= a[j]; 11𝑛 − 10 + 10 = 5𝑛2 + 𝑛 − 10
j--; 2
}
a[j+1]=x;
}
}
Análisis de algoritmos no recursivos:
Ordenación por selección
0 1 2 3 4 5 6
/** 6 2 8 3 5 9 7
* @param a array de enteros
* a ordenar por selección
*/ 0 1 2 3 4 5 6
public static void seleccion(int[] a){ 2 6 8 3 5 9 7
for (int i = 0; i<[Link]-1; i++){
// a[0..i-1] está ordenado
int min = i; 0 1 2 3 4 5 6
for (int j=i+1;j<[Link];j++) { 2 3 8 6 5 9 7
// min es el menor elemento
// del array a[i..j-1]
if (a[j]< a[min]) min = j; 0 1 2 3 4 5 6
} 2 3 5 6 8 9 7
//intercambiamos a[i] y a[min]
int temp = a[i];
a[i] = a[min]; 0 1 2 3 4 5 6
a[min] = temp; 2 3 5 6 8 9 7
}
}
0 1 2 3 4 5 6
2 3 5 6 7 9 8

0 1 2 3 4 5 6
2 3 5 6 7 8 9
Análisis de algoritmos no recursivos:
Ordenación por selección
/**
* @param a array de enteros
* a ordenar por selección
*/
public static void seleccion(int[] a){
for (int i = 0; i<[Link]-1; i++){
// a[0..i-1] está ordenado
int min = i; ¿Orden?
for (int j=i+1;j<[Link];j++) {
// min es el menor elemento
// del array a[i..j-1]
t(n) ÎQ(n ) 2

if (a[j]< a[min]) min = j;

}
//intercambiamos a[i] y a[min]
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
Ejemplo 1
//@ pre: n>=0
public static void misterio (int n) { n
n  (n + 1) (2n + 1)
int s = 0;
HOME
i2 =
i =1 6
int i, j, k;
for ( i = 1; i <= n-1; i++ )
n −1
n (n −1) (2n −1)
for ( j = i+1; j <= n; j++ )
i2 = 6
i=1
for ( k = 1; k <= j; k++ )
s += 2;
}

Mejor, peor caso?
public static void muyImpar (int n) {
❑ Los distintos casos se int x = 0, y = 0;
estudian con respecto a la int i, j, k;
NATURALEZA, NO con for ( i = 1; i <= n; i++ ) {
respecto al tamaño. if (( i % 2 ) == 0 ) {
for ( j = 1; j <= n; j++ ) {
❑ Es decir, con respecto al
valor de n x++;
❑ O por la lógica del }
algoritmo for ( k = 1; k <= i; k++ ) {

y++;
}
¿Orden? }

}
}
Mejor, peor caso? Caso medio?
public static void muyImpar (int n) {
❑ Los distintos casos se int x = 0, y = 0;
estudian con respecto a la int i=n, j, k;
NATURALEZA, NO con if (( i % 2 ) == 0 ) {
respecto al tamaño. for ( j = 1; j <= n; j++ ) {
❑ Es decir, con respecto a n x++;
❑ O por la lógica del }
algoritmo for ( k = 1; k <= i; k++ ) {

y++;
}
}

}
Ejemplo

/**
* @param n número natural
* @return n! = 1*...*n
*/
public static int factorial(int n){
if (n<0) throw
new IllegalArgumentException(“número no válido");
if (n == 0) return 1;
else return n*factorial(n-1);
}
Ecuaciones de Recurrencia
Ecuaciones de Recurrencia
❑ A menudo es la etapa final en el análisis de algoritmos
(recursivos).
❑ Es normal que un procedimiento se base en
procedimientos auxiliares, haga llamadas recursivas para
tamaños menores o reduzcan el tamaño del problema
progresivamente.
❑ El tiempo t(n) del algoritmo original se expresa en función
del tiempo para el mismo algoritmo pero para problemas
de menor tamaño con lo que obtenemos una ecuación en
recurrencia.
⚫ Ejm para el alg factorial: t(n)=t(n-1)+5
Tipos de ecuaciones de recurrencias

❑ Lineales a0 tn + a1 tn-1 +...+ ak tn-k = 0

1. Homogéneas
2. No-homogéneas
❑ No lineales

a0 tn + a1 tn-1 +...+ ak tn-k = bn p(n)

e.g. T(n) = Tk (n/2k) + k

Ecuaciones Homogéneas
❑ Se trata de resolver ecuaciones de la forma:

aot (n ) + a1t (n − 1) + ... + ak t (n − k ) = 0 con a0  0 y 0  i  k ; ai  .

Cuya ecuación característica se define como:

ao x n + a1 x n−1 + ... + ak x n−k = 0

❑ Si eliminamos las soluciones triviales:

x n−k
(a x
o
k
+ a1 x k −1
)
+ ... + a k = 0
❑ La ecuación característica tiene la forma:

ao x k + a1 x k −1 + ... + a k = 0
Raíces Reales Distintas
❑ Solución.
k
t (n ) =  ci ri n donde ri son las distintas
raíces (soluciones) a la
i =1
ecuación característica

❑ Ejemplo. Resolver la ecuación de la sucesión de Fibonacci.

t n = t n−1 + t n−2 , n  2
t 0 = 0, t1 = 1
Solución al Ejercicio

❑ Ecuación Característica. x2 − x −1= 0

1− 5 1+ 5
❑ Raíces: r1 = y r2 =
2 2 ¿Orden?

❑ Solución: tn = c1r1n
+ n
c 2 r2 .
c1 + c 2 = 0 1 1
❑ Constantes:  c1 = − , c2 = .
c r +
 11 2 2c r = 1 5 5


Solución al Ejercicio
/** /**
* @param n número natural * @param n número natural
* @return el n-ésimo elemento de fibonacci * @return el n-ésimo elemento de fibonacci
* Implementación ineficiente * Implementación eficiente
*/ */
public static int fibonacci(int n){ public static int fibonacciNoRec(int n){
//n >=0 if (n==0) return 0;
if (n==0) return 0; else {
if (n==1) return 1; int fibAnt = 0;
else return fibonacci(n-1)+fibonacci(n-2); int fibAct = 1;
} for (int i = 1; i<n; i++){
int fibInt = fibAnt;
fibAnt = fibAct;
fibAct = fibInt + fibAnt;
}
5 return fibAct;
4 3 }
}
3 2 2 1

2 1 1 0 1 0

1 0 La Complejidad de la versión no recursiva

es lineal

La mayoría de las operaciones se repiten

¿cuál es MEJOR? ¿cuál es más EFICIENTE?
muchas veces
Raíces Reales No Distintas
❑ Si todas las raíces no son distintas, entonces asumiendo que existen l
raíces distintas r1, r2, ... rl cuyas multiplicidades son mi para cada ri:
❑ Solución
l mi −1
t n =   cij n j ri n
i =1 j = 0

❑ Ejemplo. Resolver la siguiente recurrencia.

t 0 = 0

t n = 5t n−1 − 8t n−2 + 4t n−3 , t1 = 1
t = 2
2
Solución al Ejercicio
❑ Ecuación característica:

ì x1 =1 con multiplicidad 1
x - 5x + 8x - 4 = 0 Þ ( x -1) ( x - 2) = 0 Þ í
3 2 2

î x2 = 2 con multiplicidad 2

❑ Solución:
t n = C1 (1) + C 2 (2 ) + C3 n(2 ) .
n n n

❑ Constantes:
 C1 + C2 = 0,
 1
 C1 + 2C2 + 2C3 = 1,  C1 = −2, C2 = 2, C3 = −
C + 4C + 8C = 2, 2
 1 2 3

n +1 n −1
❑ Solución final: tn = 2 − n2 −2
Ecuaciones no Homogéneas (método 1)
❑ Vamos a suponer la siguiente ecuación:
t (n) − 2t (n − 1) = 3 n

❑ Cogemos la ecuación para n+1

n +1
t (n + 1) − 2t (n) = 3
❑ Multipliquemos por 3 la primera ecuación
n +1
3t (n) − 6t (n − 1) = 3
❑ Y restamos las dos últimas ecuaciones…OK. Pero…y si no es nuestro
mejor día…
Ecuaciones No Homogéneas
❑ Son de la forma:

aot (n ) + a1t (n − 1) + ... + ak t (n − k ) = f (n )

k s

❑ Forma general:  a t (n − i ) =  b p (n),

i =0
i
i =1
i
n
i

❑ Ecuación Característica:

 k  s
d i +1 
  ai x   (x − bi )  = 0 con d i el grado del polinomio p i (n)
k −i

 i =0  i =1 
Y a continuación se procede de la misma forma que con las ecuaciones homogéneas
Ecuaciones no Homogéneas
❑ Ejemplo:

𝑡(𝑛) = 2𝑡(𝑛 − 1) + 𝑛 + 2𝑛 ;
𝑡 𝑛 − 2𝑡 𝑛 − 1 = 𝑏1𝑛 𝑝1 𝑛 + 𝑏1𝑛 𝑝2 𝑛 ;
𝑡 𝑛 − 2𝑡 𝑛 − 1 = 1𝑛 𝑛 + 2𝑛 1;
Ec. caract → (x − 2) 𝑥 − 1 2
𝑥−2 =0

t (n) = C1 2 + C2 n2 + C3 + C4 n
n n

¿Podemos afirmar directamente que es de orden n2n?

Notas adicionales
❑ ¿Como se hace el caso en el que las raices sean
complejas de multiplicidad 1?
⚫ Exactamente igual que en el caso de raices reales de multiplicidad
1
⚫ Con las reducciones posibles cuando se estén tratando con
números imaginarios (ejm. i*i=-1).
❑ No vamos a ver el caso en el que las raices sean
complejas de multiplicidad mayor que 1.
❑ Las raices de la ecuación característica de una ecuación
de recurrencia no pueden ser 0.
Expansión de Recurrencias
❑ Este método se basa en aplicar varias veces la formula recurrente
hasta encontrar alguna regularidad.

❑ Ejemplo. Supongamos que el número de operaciones elementales del

algoritmo recursivo para calcular el factorial viene dado por la
siguiente ecuación:
1 n 1
t (n ) = 
t (n − 1) + 5 en otro caso

❑ Si expandimos entonces:
n −1
t (n) = 5 + t (n − 1) = 5 + 5 + t (n − 2) = ... =  5 + t (1) = 5n − 4
i =1
 Análisis de Algoritmos Recursivos
Las torres de Hanoi
/**
*
* @param n numero de discos
* @param a varilla origen
* @param b varilla intermedia
* @param c varilla destino
*/

public static void hanoi(int n, char a,char b,char c){

// n >=1
if (n>0){
hanoi(n-1,a,c,b);
[Link]("Pasar un disco de "+a+" a "+c);
hanoi(n-1,b,a,c);
}

A B C }

Tamaño de la entrada: número de discos

Operación primitiva: pasar un disco de una varilla a otra
Ecuación de recurrencia:
Expansión de Recurrencias
❑ Ejemplo. El número de movimientos para el problema de las torres de
Hanoi viene dado por la siguiente ecuación:

0 n=0
t (n ) = 
2t (n − 1) + 1 en otro caso

❑ Si expandimos entonces:
n −1 n −1
t (n ) = 2t (n − 1) + 1 = 2 t (n − 2 ) + 2 + 1 = ... ... = 2 t (n − n ) +  2 =  2i  2n
2 n n i

i =0 i =0
Tipos de ecuaciones de recurrencias

❑ Lineales
1. Homogéneas
2. No-homogéneas
❑ No lineales

e.g. T(n) = Tk (n/2k) + k

Cambio de Variable
❑ Esta técnica se aplica cuando n es potencia de un número real a, esto
es, n=ak.
❑ Ejemplo:
t (n ) = 4t (n 3) + n 2
❑ Solución. Realizar un cambio de variable.

⚫ Cambio de variable. n = 3k ( ) ( )
t 3k = 4t 3k −1 + 9k
⚫ Ecuación conocida. t k = 4t k −1 + 9 k
𝑡𝑘 = 𝑐1 4𝑘 𝑐2 9𝑘
⚫ Deshacemos el cambio de variable:

𝑡 𝑛 = 𝑐1 4log3 𝑛 𝑐2 9log3 𝑛 = 𝑐1 𝑛log3 4 𝑐2 𝑛2

Cambio de Rango
❑ Son de la forma:

t (n ) = nt (n 2), t (1) =
2 1
3
❑ Solución. En este caso se toman logaritmos:
2
⚫ Primero un cambio de variable. 𝑡𝑘 = 2𝑘 𝑡𝑘−1
⚫ Cambio de Rango. Tomamos logaritmos en ambos lados y renombramos:

𝑣𝑘 = log 2 𝑡𝑘
⚫ Ecuación conocida.

𝑣𝑘 = 𝑘 + 2𝑣𝑘−1
𝐸𝑐 → 𝑥 − 2 𝑥 − 1 2 =0
Cambio de Rango
t (n ) = nt (n 2), t (1) =
2 1
𝑣𝑘 = 𝑐1 2𝑘 + 𝑐2 +𝑐3 𝑘 De aquí extraemos que:
3
𝑐1 2𝑘 +𝑐2 +𝑐3 𝑘
𝑡𝑘 = 2 t 2 = 2𝑡 2 1 =
2
9

𝑡(𝑛) = 2𝑐1 𝑛+𝑐2 +𝑐3 log 𝑛

16
t 4 = 2𝑡 2 2 =
81

1
= 2𝑐1 +𝑐2
3
2/9 = 22𝑐1+𝑐2+𝑐3
16/81 = 24𝑐1+𝑐2+2𝑐3

Ya sólo queda resolver

Análisis de algoritmos recursivos
El teorema maestro (versión general)
Análisis de algoritmos recursivos
El teorema maestro (versión general)
Análisis de algoritmos recursivos
El teorema maestro (ejemplos)
Análisis de algoritmos recursivos
El teorema maestro (versión reducida)

/**
* @param l lista de números a sumar
* @param min y max, índices máximo y mínimo a suma
* @return Suma de los elementos de la lista
* Implmentación recursiva
*/
public static int suma(List<Integer> l,int min,int max){
if (max < min) return 0;
if (max == min) return [Link](min);
else {
int s1 = suma(l, min,(min+max)/2);
int s2 = suma(l, (min+max)/2+1,max);
return s1+s2;
}
}
Análisis de algoritmos recursivos
Búsqueda binaria
izda medio dcha
/**
* @param a array en el que se busca x = 4
* suponemos que está ordenado
0 1 2 3 4 5 6 7
* @param x elemento buscado
* @return posición en la que aparece x, si 2 3 5 6 7 8 8 9
* está, o -1, si no está izda medio dcha
*/
public static int busqBinaria(int[] a,int x){ 0 1 2 3 4 5 6 7
int izda = 0,dcha = [Link]-1; 2 3 5 6 7 8 8 9
int medio = (izda + dcha)/2;
while (izda <= dcha && a[medio]!=x){
if (a[medio]>x) dcha = medio - 1;
izda medio
dcha
else izda = medio + 1;
0 1 2 3 4 5 6 7
medio = (izda + dcha)/2;
} 2 3 5 6 7 8 8 9
if (izda <= dcha) return medio;
else return -1;
}

Tamaño de la entrada: longitud del array n

Operación elemental: comparación de claves
Hay que distinguir entre caso mejor y peor
Análisis de algoritmos recursivos
Búsqueda binaria
/**
* @param a array en el que se busca
* suponemos que está ordenado
* @param x elemento buscado
* @return posición en la que aparece x, si
* está, o -1, si no está
*/
public static int busqBinaria(int[] a,int x){
int izda = 0,dcha = [Link]-1;
int medio = (izda + dcha)/2;
while (izda <= dcha && a[medio]!=x){
if (a[medio]>x) dcha = medio - 1;
else izda = medio + 1;
medio = (izda + dcha)/2;
}
if (izda <= dcha) return medio;
else return -1;
}

El algoritmo Búsqueda Binario es uno de los pocos que no

tienen que analizar toda la entrada para encontrar la solución
Clases de Complejidad
❑ De manera informal, la Complejidad Computacional se puede describir
como el coste requerido para encontrar la solución a un problema en
términos de recursos computacionales: tiempo o memoria.

❑ La complejidad de un problema vendrá determinada por la

complejidad del algoritmo más eficiente que lo resuelve.

❑ La teoría de la Complejidad Computacional plantea los problemas

como casos de decisión para los cuales su solución corresponde a una
respuesta Si/NO.
⚫ ¿Es la solución satisfactible?
Clases de complejidad
Complejidad temporal
❑ Clase P. Problemas resolubles en tiempo polinómico.
⚫ Son tratables porque pueden ser abordados en la práctica. Los
problemas que no pertenecen a la clase P se denominan problemas
intratables.

❑ Clase NP. Problemas intratables pero donde existe un

algoritmo polinómico que indica si una solución dada es
válida o no.
⚫ Se utilizan heurísticas, y en un tiempo polinómico se calcula la validez
de la solución obtenida (No-deterministas polinómicos).

❑ Clase EXP. Problemas resolubles en tiempo

exponencial.
Clases de complejidad
Problemas NP-completos
❑ Supongamos la existencia de una relación entre problemas, denotada
por ≥, que permita indicar qué un problema es más complejo que
otro.
❑ Los problemas NP-completos son los más complejos dentro de la
clase NP. Si se encuentra un algoritmo de clase P para solucionar uno
de ellos, entonces se pueden resolver todos. Y entonces se cumpliría
P=NP (un problema sin resolver. Literalmente, el problema del millón
de dólares)
❑ Un problema C se dice completo para NP respecto a la relación ≤
(NP-completo) si cumple:
1. 𝐶 ∈ 𝑁𝑃
2. ∀𝐿 ∈ 𝑁𝑃: 𝐿 ≤ 𝐶
Clases de complejidad
Problemas NP-duros
❑ Un problema D se dice NP-difícil (NP-hard) si cumple:
∀𝐿 ∈ 𝑁𝑃: 𝐿 ≤ 𝐷

⚫ Son al menos tan complejos como los NP-completos

Clases de complejidad
Complejidad espacial
❑ La complejidad espacial se encarga de estudiar el coste de memoria
principal que los algoritmos necesitan para su funcionamiento.
⚫ El coste de almacenar la entrada es ignorado, puesto que será el mismo para todos
los algoritmos que resuelvan el mismo problema.

❑ El acceso a bases de datos o datos en memoria secundaria dependerá

de la cantidad de esa información que se guarda en memoria
principal.

❑ Clase L. Problemas resolubles utilizando espacio

logarítmico respecto a la entrada.

❑ Clase PSPACE. Problemas resolubles utilizando

espacio polinómico.
Clases de complejidad
Tiempo vs Espacio
❑ Supongamos que para resolver problemas en nuestro sistema
tenemos un recurso ilimitado, tiempo o espacio, pero nuestro
algoritmos deben ceñirse a alguna de las siguientes limitaciones:
⚫ Una complejidad temporal de O(n).
⚫ Una complejidad espacial de O(n).

❑ ¿Qué restricción nos permitirá definir algoritmos para resolver

problemas más complejos?

❑ El espacio es reutilizable, el tiempo no.

❑ El problema de la satisfacibilidad se resuelve con algoritmos O(2n) de

complejidad temporal y O(n) de complejidad espacial.
Complejidad temporal
Tiempo vs Espacio
❑ En general, si disponemos de espacio O(f(n)), el número de
configuraciones distintas por las que puede pasar el algoritmo es 2f(n).

❑ Si el algoritmo acaba, no puede repetir configuración (pues sino

entraría en un bucle infinito); entonces su tiempo de cómputo es
O(2f(n)).

❑ Con espacio O(log(n)), se pueden resolver

todos los problemas de complejidad temporal
O(n).

❑ Con espacio O(n), se pueden abordar

problemas de complejidad temporal O(2n).
Apéndice
❑ Algunas nociones matemáticas utilizadas en este tema
Nociones Básicas de Matemáticas

❑ Límites:
⚫ Definición. Se dice que la función f(n) tiende al límite a cuando n
tiende a infinito, si para todo número real positivo δ,
independientemente de lo pequeño que sea, f(n) dista de a en
una cantidad menor que δ para todos los valores de n
suficientemente grandes.

⚫ Definición. Se dice que la función f(n) tiende a +  si para todo

número , independientemente de lo grande que sea, f(n) es
mayor que  para todos los valores de n suficientemente grandes.
Nociones Básicas de Matemáticas

❑ Límites:
⚫ Proposición. Cuando f(n) no tiende a un límite, ni tampoco a +
o -, diremos que f(n) oscila cuando n tiende a infinito. Si es
posible encontrar una constante k tal que –k < f(n) < k para
todos los valores de n, diremos que f(n) oscila de forma finita, en
caso contrario, f(n) oscila de forma infinita. P.e. (-1)n y (-1)n n.

⚫ Proposición. Si dos funciones f(n) y g(n) tienden respectivamente

a los límites a y b cuando n tiende a infinito, entonces f(n)+ g(n)
tienden al límite a + b.
Nociones Básicas de Matemáticas

❑ Límites:
⚫ Proposición. Si dos funciones f(n) y g(n) tienden respectivamente
a los límites a y b cuando n tiende a infinito, entonces f(n)  g(n)
tiende al límite a  b.

⚫ Proposición. Si dos funciones f(n) y g(n) tienden respectivamente

a los límites a y b cuando n tiende a infinito, y b no es cero,
entonces f(n) / g(n) tiende al límite a / b.

⚫ Proposición. Si dos funciones f(n) y g(n) tienden respectivamente

a los límites a y b cuando n tiende a infinito, y si f(n)  g(n) para
todo n suficientemente grande, entonces a  b.
Nociones Básicas de Matemáticas

❑ Series:
⚫ Proposición. (Serie aritmética) Sea Sn la suma de los n primeros términos
de la serie aritmética a, a + d, a + 2d, … . Entonces:

n  (n − 1)  d
Sn = a  n +
2
⚫ Proposición. (Serie geométrica) Sea Sn la suma de los n primeros
términos de la serie geométrica a, ar, ar2, … (caso especial: Si r = 1,

( )
entonces Sn = an). Entonces:
a  1− r n
Sn =
(1 − r )
Nociones Básicas de Matemáticas

❑ Series:
⚫ Proposición. Para cualquier entero k  0 tenemos que:

n
n  (n + 1)(n + k + 1)
 (i  (i + 1)(i + k )) =
i =1 k +2

n
n  (n + 1)
⚫

i =1
i=
2
Nociones Básicas de Matemáticas

❑ Series:
⚫ Proposición.
n
n  (n + 1) (2n + 1)

i =1
i = 2

6
⚫ Sea r cualquier entero positivo. Entonces
n r +1
n

i=1
i r
=
( r + 1)
+ pr ( n)

En donde pr (n) es un polinomio de grado no mayor que r.