Ho appena risolto questo problema, ma voglio conoscere un modo più efficiente di fare moltiplicazione di matrici
M :
------
1 1 0
0 0 5
3 2 0
f [n] = M ^ n
Ho implementato utilizzando Exponentiation_by_squaring
C'è più efficienza di questo?
Ho appena risolto questo problema, ma voglio conoscere un modo più efficiente di fare moltiplicazione di matrici
M :
------
1 1 0
0 0 5
3 2 0
f [n] = M ^ n
Ho implementato utilizzando Exponentiation_by_squaring
C'è più efficienza di questo?
Poiché N può essere grande come 10 ^ 12, dovrebbe essere chiaro che iterare da 1 a N non è la soluzione desiderata. L'intuizione chiave è che la ricorsione può essere riscritta come V (i) = M * V (i-1), dove
V(i) = [RR(i), MM(i), PP(i)] (a column vector)
così
V(0) = [ 3 1 0 ]
e
M = | 1 0 3 |
| 1 0 2 |
| 0 5 0 |
Ora V (N) = M ^ N * V (0)
Possiamo calcolare M ^ N nel tempo log (N) da ripetutamente a squadro :
M^2 = M * M
M^4 = M^2 * M^2
...
Esegui tutti i calcoli mod 100000006 per evitare di accumulare numeri grandi.
Per arrivare a questa soluzione, aiuta ad avere una familiarità di base con l'algebra lineare.
Leggi altre domande sui tag java dynamic-programming process-improvement