| P | Q | Memoria | |
|---|---|---|---|
| Sol 1 | |||
| Trivial | 1 | n | 1 |
| Sol 2 | |||
| Precomputo todo | n^2 | 1 | n^2 |
| Sol 3 | |||
| Bloques | n | sqrt(n) | sqrt(n) |
| Sol 4 | |||
| Tabla dispersa | n log n | 1 | n log(n) |
| Sol 5 | |||
| Híbrida: tabla dispersa SB/Nada B | n | log(n) | n/log(n) |
| sol 6 (abajo) | |||
| Híbrida: tabla dispersa SB y B | n log(log n) | 1 |
$$ Cn = (1/(n+1) ) * (2n (nCr) n) $$
B1 = [1, 2, 3, 4]
B2 = [10, 20, 30, 40]
Son isomorfos
#Cant de bloques de tamaño b distintos (morfología distinta) = Cb
Es un método para optimizar algoritmos en donde se usa una lookup table (dict) en donde dos partes del problema tengan la misma solución → mapear un problema a un bitmap
(Parecido a un heap)
Es un árbol que:
Ejemplos