SoloCodigo
Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: luciocontreras en Martes 11 de Octubre de 2005, 17:47
-
Tengo este ejercicio que creo tengo resulta la primera parte, deseo que alguien me ayude a terminarlo dice asi:
Considere un algoritmo de búsqueda ternaria que utiliza la técnica de Divide y Vencerás que primero analice el elemento en la posición n/3 y luego, posiblemente chequee al elemento en la posición 2n/3 hasta que encuentre al elemento que busca o reduzca la dimensión del conjunto donde buscar a 1/3 de la original.
a) Escriba el algoritmo utilizado en el seudo lenguaje.
b) Analice si se puede hablar de mejor y peor casos y calcule la complejidad temporal en cada caso.
Mi respuesta:
Parámetros utilizados.
Búsqueda ternaria en un Arreglo A
inicio, valor del índice inicio del arreglo A
fin, valor del índice final del arreglo A
X es el valor que se quiere encontrar en el arreglo A
@return, devuelve un entero con el resultado de la búsqueda, si no lo encuentra, devuelve -1;
tercio es una variable entera.
PROCEDURE BusquedaTernaria(A,inicio,fin,X)
int tercio;
if(inicio>=fin)
return -1;
else
tercio=(fin-inicio+1)/3; //Se calcula el tercio del arreglo
//si es igual al primer tercio.
if(X=A[tercio+inicio])
return A[tercio+inicio];
else{
//si es menos que el primer tercio.
if(X<A[tercio+inicio])
return BusquedaTernaria(A,inicio,tercio+inicio,X);
else
//si es igual al segundo tercio.
if(X=A[fin-tercio])
return A[fin-tercio];
else
//si es menor que el segundo tercio.
if(X<A[fin-tercio])
return busquedaTernaria(A,inicio+tercio+1,fin-tercio,X);
else
//si es mayos que el segundo tercio.
return busquedaTernaria(A,fin-tercio+1,fin,X)
b) Me falta
Me podran ayudar?
-
Hola, que tal.
Por lo que veo tienes un algoritmo recursivo, una forma fácil de ver su complejidad es que expandas su árbol, de aqui puedes ver cuales serían su mejor y peor caso.
La otra forma seria que derives una fórmula a partir de lo que tienes, por lo que veo creo que tendrias que dessarrollar T(n/3 + c).
Espero te sirva.
Hasta luego.