Clase Auxiliar 08/09/2000
Problema 1: Calcule el tiempo utilizado por el siguiente algoritmo:
int elevado(x,n){
/* caso base */
if (n == 0) {
return 1;
}
/* caso recursivo impar*/
else (n es impar) {
return x * elevado(x,n-1);
}
/* caso recursivo par*/
else (n es par) {
return elevado(x*x,n/2);
}
}
Problema 2: Calcule el tiempo utilizado por el siguiente algoritmo:
int sumaLista (lista l){
if l.largo = 0
return 0
else l.largo = 1
return l.primerElemento
else sumaLista (l.mitadDerecha) + sumaLista
(l.mitadIzquierda);
}
Supuestos:
lista Qsort(lista l){
if l.length < 2
return l
else{
pivote = l.elemDelMedio
redistribuir los elementos
de l de modo que los menores queden a la derecha del pivote y los mayores
a la izquierda
lDer= Qsort(l.derechaPivote);
lIzq= Qsort(l.izquierdaPivote);
return lDer.concatena(lIzq);
}
}
Supuestos:
f0 = 0
f1 = 1
a.Planteando el polinomio característico
b.Adivinando la serie, y demostrando su validez
Problema 5: Resuelva la ecuación de recurrencia fn = fn-1 - fn-2 planteando su polinomio característico.
f0 = 0
f1 = 1
Problema 6: Resuelva la ecuación de recurrencia T(n) = 2T(n/2) - 3T(n/4) + 7
T(1) = 1
T(2) = 2
Hint: realice un cambio de variables, elimine el termino constante y
resuelva el polinomio característico.