Ec. de Recurrencia

Julio A. Fuentealba Vivallo
___________________________________________________________________
Guía de ecuaciones de recurrencia
___________________________________________________________________

1.- El siguiente algoritmo ordena un conjunto de elementos. Calcule su eficiencia en función de sus comparaciones

void CH(arreglo a, int izq, int der )
{
int i,j,v ;
if (der > izq )
{v = a[der] ; i = izq-1 ; j = der ;
for (;;)
{
while (a[++i] v ) ;
if ( i >= j ) break ;
intercambia(a,i,j);
}
intercambia(a,i,der);
CH(a,izq,i-1);
CH(a,i+1,der);
}
}
solucion
este algoritmo es QuickSort

2.- El ordenamiento de selección cuadrática, divide los n elementos de un conjunto S en k grupos donde
k = raíz(n), encuentra el elementomás grande de cada grupo y lo lleva a un arreglo A, encuentre al mayor elemento del arreglo auxiliar y llévelo a la ultima casilla disponible de un arreglo O, luego reemplace en A el elemento extraído por el mayor del grupo del cual proviene, repita el proceso hasta que O contenga a S ordenado.

¿ cual es la eficiencia de este algoritmo ?
¿ que pasa con los datos repetidos ?

solucion
secontaran comparaciones entre elementos del conjunto
a- subdividir en raiz(n) elementos ------------------ costo 0
b- sacar el mayor de un grupo ------------------- raiz(n) – 1
c- sacar el mayor de todos los grupos ------------- raiz(n) *( raiz(n) – 1)
d- sacar el mayor de A y llevarlo a O ------------------- raiz(n) – 1

e- reemplazar el elemento extraido de A-------------------raiz(n) – 1
f- repetir los pasos c,d y e n veces------------------- n * (2*( raiz(n) – 1))
g- costo total se obtiene de sumar 3 y 6 ---- raiz(n) *( raiz(n) – 1) + n * (2*( raiz(n) – 1))






3.- Considere el algoritmo siguiente
dado el Conjunto S, todos sus elementos son insertados en un ABB
el ABB es recorrido en inorden, guardando la secuencia obtenida
se retorna elconjunto ordenado.
solucion
insertar 1 dato en un ABB  de orden(log(n))
insertar n elementos en un ABB  de orden(n*log(n))
recorrer en inorden  de orden(n)

orden del algoritmo  de orden(n *log(n))

4.- Para el siguiente programa calcule el costo y el orden de la función “costo” .

#include
int contador ;
int costo (int i )
{
int k, respuesta = 0 ; printf ( “ … %d“,contador ++ );
if ( i < 2 )
return 1 ;
else
for ( k = 1 ; k < i ; k++ )
respuesta = respuesta + costo ( i - k );
return respuesta ;
}
main ()
{ int j ;
for ( j = 0 ; j < 15 ; j++ )
{ contador =0 ;
costo (j);
getch(); printf(“\n-------------------------------\n”);}
}

solucion
se contaran sumas de la expresión respuesta = respuesta + costo ( i - k );
como es un alg recursivo se usara una ecuación de recurrencia



0 si n < 1

T(n) =
1 +T(1) + T(2) + T(3) + … + T(n-k)


t(n) = 1 + sumatoria(t(i)) para i desde 1 hasta n-k, (1)
hacemos la expresiónpara n-1
t(n-1) = 1 + sumatoria(t(i)) para i desde 1 hasta n-1-k, (2)

restamos (1) menos (2) y nos da
t(n) – t(n-1) = 0 + t(n-1)
lo que da

t(n) – 2*t(n-1) = 0

como esta es una ecuación homogénea, lineal y de coeficientes constantes

se usara el método de la ecuación característica.

xn – 2xn-1= 0
ecuación característica es x – 2= 0 lo que resulta en x = 2
luego t(n)= cte * 2n

5.- Se desean colocar 8 reinas en un tablero de ajedrez de manera que ninguna en una sola movida, pueda comerse a otra. La estrategia más común es que usted, ponga una reina en un casillero (una reina en cada fila y en cada columna), verifique que no provoca conflicto e intente la siguiente, si provoca conflicto entonces, cambia la posición actual, si luego de intentar las 8...