Array: [62, 31, 10, 47, 8, 75, 2, 3, 61]
Problema: encontrar el mínimo entre posiciones i, j
Sol trivial: Calcular cada vez
Costo de consulta (q): O(n)
Costo de preprocesamiento (p): O(1)
Una vez que tengo la matriz, el costo de consulta (q) es O(1)
Costo de preprocesamiento (p): O(n^3)
Me creo la diagonal con el número consigo mismo, y de ahí comparo el primero de la diagonal con el segundo, y el menor lo pongo arriba del segundo de la diagonal. Lo mismo con el segundo y el tercero, y el mínimo lo pongo arriba del tercero. Así, me creo una segunda diagonal. Vuelvo a repetir el proceso con la segunda diagonal y así.
Costo de preprocesamiento: O(n^2)
Costo de consulta q: O(1)
Divido en bloques, por ej de a 3 (b=3):
[28, 71, 49] [36, 51, 11] [19, 3, 99] [64, 12, 55]
Costo de preprocesamiento: O(n)
Costo de consulta: O( (n/b) + 2b)
Cuál b me vonviene usar? Derivo dq/db = -n/b^2 + 1 = 0 → n/b^2 = 1 → n = b^2 → b = sqrt(n)