Para la función count, en funcion potencial lo mejor es contrar el numero de bits en 1.
El costo amortizado de todos los valores .
Truco del conteo
más facil que potencial
-suponemos un valor para t (TAO)
Analisis de recurrencias:
-Conjetura inteligente: intuicion del analista y experiencia.
1. se calculan los primeros valores de la recurrencia
2. Buscar una regularidad o patrón. Podemos expandir la función: despues del cambio de variable, y de ahí intentamos encontrar un patron, como una funcion
3. Hacemos la formula
4. Prueba matemática(no lo hacemos en el curso)
Recurrencia homogenea(lineal homogenea con coeficientes constantes):
tn son incognitas y los ak son constantes. (De ambos hay k.)
3 apellidos:
1. Da cero
2. Es lineal
3. Coeficientes constantes
REPASAR LAS ETAPAS:
a. ecuacion caracteristica
b. ecuacion caracteristica polinomial
c. Obtener raíces
d. solucion general (raices por constante)
e. sacar las soluciones con lo que ya tenemos(sistema ecuaciones)
f. solucion a la recurrencia original
k soluciones.
