Ho una lista enorme di matrici i.e A = {M0, M1, M2 .. Mn}. Ho un compito di trovare il prodotto di tutte le matrici in un determinato intervallo {x, y} cioè M x * M x + 1 * M x + 2 ... * M y .
Vorrei sapere se esistono algoritmi o strutture di dati che potrebbero calcolare efficacemente questa query.
Ho provato a creare una matrice 2D di tutte le possibili combinazioni di gamma, ma poiché la mia matrice iniziale è molto grande, questa non sembra una soluzione pratica.
Anziché precompilare tutte le combinazioni possibili, è sufficiente precalcolare i livelli di potenza di 2.
Quindi prima sarebbe M0_1 = M0 * M1, M2_3 = M2 * M3, M4_5 = M4 * M5, ...
Il secondo sarebbe M0_3 = M0 * M1 * M2 * M3, M4_7 = M4 * M5 * M6 * M7, ...
E così via, fino a quando la potenza maggiore di 2 è minore di n. Questo richiederà solo 2 volte più memoria.
Quindi, puoi scegliere di suddividere l'intervallo in modo che i blocchi più grandi facciano parte del calcolo. Ad esempio, per l'intervallo {1,8} moltiplicheresti M1 * M2_3 * M4_7 * M8. Questo è solo 3 moltiplicazioni invece di 8. In generale, nel caso peggiore la quantità di moltiplicazioni è la funzione logaritmica della lunghezza dell'intervallo.
Inoltre, la scelta dei sottointervalli appropriati potrebbe essere ottimizzata usando una logica binaria intelligente. Quindi quella parte ha una complessità temporale costante.
Leggi altre domande sui tag data-structures algorithms trees