COP SD D

Los factores externos no aportan información sobre el algoritmo

Solo el no de operaciones elementales ejecutadas importará en el análisis (no el tiempo exacto

L operaciones aritméticas
, return , Llamada Función
acceso a
arrays
, a

Principio de invarianza : t, (n)(Ct, (n) y dt , (n) > ty(n)

Eficiencia

Enfoque empírico (A posteriori) : mide exactamente el tiempo

Enfoque teórico (A priori) : Calcula una función en Función del tamaño de la entrada su naturaleza
y

Notación asintótica : Trata sobre el comportamiento de funciones en el lim ne a

Cota Superior
+ 0
ge0(f) si g(ulcF(n)

t(u) = 3n2 + 2n - 5 des orden 0(n2 ) ?

3m2 + 2n-SCh + In + 2n-55n2 por lo que t(u) es de O(r(

fe0(g) =
) 0(f) = 0(g)
O(f) = O(g)(t) feo(g) ygE0(F)

feo(g) yge 0(h) = FEO(h)

Si fe0(g) y FztO(k) = F, + fztO(max (g , u))

Si F, eOlg) y FzE0(k) = Fi fze 0(g h) .

Lim F(u)/g(n) E IR cuando n +co entonces O(F) = 0(g)

Lim F(u)/g(u) = 0 cuando n + o entonces O(F) (O(g)

⑦ pag 18 el ejemplo
Para índice = expresión , to expresión By expresión Do cuerpo

Cota inferior +en g(ul(F(n)

Fer(g) ) r(f)
= =m(g)

- (f) = r(g)(=) f -r(g) yg = r(f)

few(g)yge r(h) = ) fer(h)

Si Fiel(g) y Fer(h) = Fi + Fz t r (max (g , u))

Si F, Eng) y FzEr(k) = Fi F2 El(g h) · .

Lim F(u)/g(n) E IR cuando n e co entonces r(F) = e(g)

Lim F(u)/g(u) = 0 cuando n + o entonces e(f) ((g)

Orden exacto e Elf) = O(f)n(f)

O(f) = 0(g) (=) fef(g) yg O(f)

feo(g)ygt f(k) = fc O(h)

f, ff(g) y fztf(h) ) f , + fz
=
&(g) y f ,
+ fz O(h)

f, cf(g) y fzt0(k) = ) fi fy to(g h) .

Si limf(u)/g(n)EIR" cuando nes o entonces (f) = f(g)

L'Hopital Formula de stirling

= im n(E" para valores de n

grandes
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 estudiaremos las clases de complejidad (P,NP,
etc.)
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 la eficiencia: recursos consumidos para obtener la solución.

Algoritmo Recursos (Var a: vector [1..n] de

< tipo_elemento>; x : entero);
Var i: entero; ¿cuántos recursos de tiempo
Inicio y memoria adicional
i:= 0; consume este algoritmo?
a[n]:= x; ¿qué hace este algoritmo?
repetir
i:= i + 1;
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 (memoria), return, llamada a una función.
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
 Pueden existir diferentes algoritmos para un problema.
 ¿Cómo calculamos la eficiencia?. ↑e
depende de los factores externos y los dificulta
ver el tiempo que tarda

 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 la
naturaleza de los mismos.

vs
Teórico Empírico
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).

Velocidad equipo

Velocidad algoritmo

Un ordenador 100 veces más

lento tardaría 25 segs menos con
otro algoritmo.
Notación Asintótica
 El análisis asintótico (en esta asignatura) 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 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. la máximo
es la cota superior, es que puede llegar
 Tiene sentido en el análisis del peor caso
pa
E

 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} f
ful = n2 todas las funciones menores o iguales que
-
O(f) = In , n2 ,
2nt , in , Y

 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 ∈ 𝑂 𝑓 ?
No
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) ∈ 𝑂 𝑛 ?
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
Comprobar con este ejemplo

 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(u)[0(nz)

 O(f) = O(g)  f  O(g) y g  O(f).

 Si f  O(g) y g  O(h) f  O(h).
0(n3
0(nz) n2 e 0(n3) = o(max (nr , 23) =
nE

 Regla de la Suma: Si f1  O(g) y f2  O(h) f1 + f2 O(max(g, h)). 12 0(23)

 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
un
mas
n  entonces O(f)  O(g).
Lento
Conteo de operaciones exacto
 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
l
 expresión - expresión  
n

t ( n) = t ( expresión1 ) + ( t ( expresión 2 ) + t ( expresión3 ) + t ( cuerpo))   2 1

 +1
1  expresión 3  
comparación
=

l
1
2

mi
 Ejemplo: for (i=1;i<=n;i++) printf(“%d”,i);
 Respuesta: t(for)=1+(1+2+1)*(((n-1)/1)+1)=1+4*n

Aunque ese sea el desarrollo matemático teórico, se ve

intuitivamente que el bucle se ejecutará n veces, que i=1
es una asignación que sólo es necesario realizar una vez, y
que las operaciones i>=n y i++ se realizarán, como ocurre
con el printf, en cada iteración del bucle.
Conteo de operaciones exacto
 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 )

15 + 2n + 5
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.

𝑡 𝑛 =𝑡 𝑛−1 +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   (g) y f1 + f2  
(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 {
/** complejidad
mejor
* 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á -l
*/
public static int busqSec(int[] a,int x){ expresion
cuerpo expresion
int i = 0; 14 asignación , expre + T
while (i<a.length && a[i]!=x){ t(u) = (y + 2) n + 2 + 1
11 l 1 l
-
M peor
complejidad
cuerpo e i++; - (n) = (t(exp(i) + +
}
11
(evet)x ++ + t(expr ) ,

l R l
if (i<a.length) return i;
else return -1;
J
l
}
}
1 + (y + 2)n + 2+ 2 + 4

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 14
¿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){
19 int i = 0; 1
expresión
while (i<a.length && a[i]!=x){
i++; cuerpo
}
if (i<a.length) return i;
else return -1;
p?
}}

To
sexprtcuerpo
𝑇 𝑛 = 1 + 5 + 2 𝑛 + 2 + 1 = 7𝑛 + 4
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<a.length; 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){
1 "
for (int i = 1; i<a.length; i++){ +(ul t(expr ,(+
1

// a[0..i-1] está ordenado

1
=
(((exp(z)
++(exp(3) +
t(erpd)))
int j = i-1;
1 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
/E 1)
l l
1 + (1 + 2 + 3 + (3 + 3)
l
while (j>=0
1 1
&&
1
a[j]>x) { t (n) = .
n +
3) . +

a[j+1]= a[j]; + (n) = 1 +

j--;
11
(9 + 8n) n .

} M 1 t(n) 1 + 9n + 8n2
=

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<a.length; 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?
/** ? &
*
* @param a array de enteros a
* ordenar por insercion
8
𝑇 𝑛 =1+ (2 + 2 + 2 + 2 + 4 + 4 + 2 + 3) =
*/
public static void insercion(int[] a){
1 1
for (int i = 1; i<a.length; i++){
2
1+ 11 + 10 =
// a[0..i-1] está ordenado 10(i -
1)
int j = i-1;
1 1
-10?
int x = a[i];
1+ 11 + 10i = 1+ 11(n−1)+10 𝑖 =
-
&

// insertamos a[i] en a[0..i-1] --

// para que a[0..i] quede ordenado
I
while 1(j>=0
1
1 l l
&&e a[j]>x) { -𝑛−1 𝑛
l
a[j+1]= a[j]; 11𝑛 − 10 + 10 = 5𝑛 + 6𝑛 − 10
j--;
~
2
11 L
}
?
1 1 1

a[j+1]=x;
}
}
 1 1 1
1

1 1 1

1 1
1

t(n 11 + 1
t(u)
-

t (u) = t(u - 11 + 1
 + v, 0, 15)
.
1
5
S 4 .
2 .
15/2 0
8

medio = + =

33 .
. 5 .
5 .
7 7 .

v[7] == 7 ! No 345 -+

+ 2
7
+ 2

! No 07 13 ? No
7 ==0
= =
(v , 8 , 15)
(v, 0
, 7) medio =
(15-8)/2 + 8 =
Dis
-
VIll] =: 11 ? No
↓ -

11 = 8 ? 011 == 15 ? No
=

medio = 7/2 =B '5 (V , 8, 11) (v , 12 , 15)

v[3] = = 3 ? No
medio = s medio = 13

3 == 0 ? 0 3 = = 7 ? No -
v[9] = = 9 ? No
-
v213] = = 13 ? No
13 = = 127813 :: 15
(v, 4 7) 8 ? 09 : : /1 ? No ?
C = = No
(v , 0 , 3)
-

, (v , 12 , 13) (r , 14 , 19
medio ( , 8 9) (v , 10, 11) (
medio = 312 =
DS S ,
=
medio = 12 medio : 14
-
v(5) = = 5 ? No
medio
v[1] =: 1 ? No 5 = =
4485 = = 7 ? No
= s medio = 10

1 = = 0 ? 0 1 =: 3 ? No (v , 4 5)
-
vi8] == 8 ? do VE10) =: 10
? No
, (v , 6 , 7)
8= 8! Si 10 = 10 ?
medio. y medio 6 Si
(v , 0, 11 (v , 2 , 3) -

V[4] =: < ? No
=
i -
=

i -
=
-
VI6] =: 6 ? No

medio = 2-4
= :4 : Si 6 : Si
6
medio = o
-
=:

i =
- 1 i =

= 1
-

v[0] = = 0 ? No
-
v[2] = = 2 ? No
2 == 2 ? Si
0? Si
-

-
0= =

i =
=
1 i =-

Y
m
21 ,,, 3 Os) ,

medio =
(j -i)/2 + i

zie edio
O
expected :
zig] >
-

v[2] 2 ? Si

reos o
= =

O 1

[1 1) ,

medio =

v[1] = = 1 ? Si

[1]
medio = O
no coincide =j
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<a.length-1; i++){
// a[0..i-1] está ordenado
int min = i; 0 1 2 3 4 5 6
for (int j=i+1;j<a.length;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<a.length-1; i++){
// a[0..i-1] está ordenado
int min = i; ¿Orden?
for (int j=i+1;j<a.length;j++) {
2
// min es el menor elemento
// del array a[i..j-1]
t(n) Î Q(n )
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++ ) {

x++;
}
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++ ) {

x++;
}
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

 A menudo es la etapa final en el análisis de algoritmos

(recursivos).
 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
Ejm. t(n)=2t(n-1)+t(n-2)
 No lineales

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

Ejm. t(n)=2t(n-1)+4n

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

Ejm. t(n)=2t(n/2)+n
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 siguiente ecuación.

crecimiento linea

𝑡 𝑛 = 6𝑡 𝑛 − 1 − 8𝑡 𝑛 − 2
t(0)=0 y t(1)=1

𝑊𝐴𝑅𝑁𝐼𝑁𝐺: 𝑇 𝑛 , 𝑡 𝑛 , 𝑡 , 𝑇 , tiene el mismo significado. El tiempo de ejecución de

un algoritmo ante una entrada de datos de tamaño n
Solución al Ejercicio

 Ecuación Característica. 𝑥 − 6𝑥 + 8 = 0

 Raíces: 𝑟 = 2; 𝑟 = 4
t(n) =
c ,
2 + cyh
n n
 Solución: tn  c1r1  c 2 r2 .
perteneen la
puede
no

 Constantes: 𝑐 +𝑐 =0 𝑐 =− ;𝑐 = a
2𝑐 + 4𝑐 = 1 tul
copuede sere
a

estofueranes dice
el
si
me
si me he equivocado en

V algo

𝑡 =− 2 + 4 ¿Orden?
Raíces Reales Distintas

 Otro 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?
exponencial
n n
 Solución: tn  c1r1  c 2 r2 .
c1  c 2  0 1 1
 Constantes:  c1   , c2  .
c r  c
 1 1 2 2 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 (raíces repetidas; es decir, de
multiplicidad>1), entonces asumiendo que existen l raíces distintas r1,
r2, ... rl cuya multiplicidad es mi para ri:
ejemplo
 Solución l mi 1
t n    cij n r
r = 2
j +z 3 ; rz 3
j n
= =

i t(n) = C ,. 2 + (2 3+ Cz
. . n . zu
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:

2 ì x1 = 1 con multiplicidad 1
x - 5x + 8x - 4 = 0 ↵ ( x - 1) ( x - 2) = 0 ↵ í
3 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
 Son de la forma:

aot n   a1t n  1  ...  ak t n  k   f n 

[biplu)
t() = zt(n -
1) + n
k s

 Forma general:  ait n  i    bin pi n, t(n) 2t(n 11 = 5 + u

- -

(X 2)(X 5)(x 1)
i 0 i 1 = 0
-
- -

 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: k s

i
a t n  i    i pi n,
b n

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

t (n)  C1 2  C2 n2  C3  C4 n
n n

¿Podemos afirmar directamente que es de orden n2n?

 k k i  d i 1 
s
  ai x   x  bi    0 con d i el grado del polinomio p i (n)
 i 0  i 1 
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.
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
 Se asume n potencia de un número real a, esto es, n=ak.
 Ejemplo:
t n   4t n 3  n 2

3 : 3=
 Solución. Realizar un cambio de variable.
e3/z
=

 Cambio de variable. n  3k    
t 3k  4t 3k 1  9k
L t k  4t k 1  9 k
cambio de dominio

 Ecuación conocida.

𝑡 =𝑐 4 +𝑐 9

-algs
lga
 Deshacemos el cambio de variable: = C

𝑡 𝑛 =𝑐 4 +𝑐 9 =𝑐 𝑛 +𝑐 𝑛
Cambio de Rango
 Son de la forma: mirar en casa !
1
t n   nt n 2, t 1 
2

3
 Solución. En este caso se toman logaritmos log na = a .

logn

 Primero un cambio de variable.

𝑡 =2 𝑡
 Porque sabemos que log ab= log a + log b

𝑣 = log 𝑡
 Cambio de Rango. Tomamos logaritmos en ambos lados y renombramos:

𝑣 = 𝑘 + 2𝑣
 Ecuación conocida.
𝐸𝑐 → 𝑥 − 2 𝑥 − 1 =0
Cambio de Rango
1
t n   nt n 2, t 1 
2

𝑣 = 𝑐 2 + 𝑐 +𝑐 𝑘 De aquí extraemos que:

3

𝑡 =2 + t 2 = 2𝑡 1 =

𝑡(𝑛) = 2 + t 4 = 2𝑡 2 =

1
=2
3
2/9 = 2
8/81 = 2

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)

a b f(u) ,
log = Z

E
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 l.get(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 = a.length-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 = a.length-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

 Sus soluciones no son verificables de manera eficiente.
 No tienen porque ser problemas de decisión
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.

 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.

⑥ ejempl pag 27

mirar
pag 28 yo
11 11
32
pag

Ecuaciones homogéneas

t(n) = St(n-1) -
8t(n -
2)
e t(ul=isoluciones de la ec.

4x >
- r =2
0x + 8 =
04rz
-

= 4

En = c
, r + cyr
c 0

&
+
, cz =

C
-=
=
=

2c + 4c = 1

tr =
-

12 +
Lu
draices No distintas?
En nor
tn = 5tn-1-8tn-z + 4tn 3
-

x = 1
,

x2 = 2 e multiplicidad 2
tu = c, (1)" + ((2)" +
Cn(2)"
C,

&
+ C2 = 0

c. + 2 +
24 = 1 = c , = -
2(2 = 2 (= -
C, + u(z + 8Cz = 2

+ +
tn = 2V -
nzn -
2

Ecuaciones No homogéneas aot(u) + a , +(n-1) +...

taxt(n -
k) = F(u)

Rag 49

② pag 53