Matematické Fórum

Jde o to najít efektivní způsob, jak násobit matice.

Zkus si to představit na sčítání čísel. Pokud bych měl n-krát sečíst nějaké stejné číslo (bez použití násobení), pak jistě nebudu provádět sčítání opravdu n-krát - sečtu třeba v prvním kroku první dvě čísla a zbylá čísla (příp. až na jedno, je-li počet původních sčítanců lichý) nahradím součtem těch dvou prvních čísel (využívám toho, že sčítaná čísla jsou všechna stejná, a asociativity sčítání) - najdeš analogii s mocněním matice?

↑ pizet:

Přesně tak. ; ))

(to je teda myšleno jako schválení postupu, ne, že bys byl hlupák : D )

Pozn: Je třeba počítat s nejhorší možností - že ti po každém takovémto zjednodušení zbude jedna matice, která nemá pár, a musí se to s ní vždy dodatečně násobit - avšak vzhledem k tomu, že těchto zjednodušení provedeš logaritmicky mnoho a po každém zjednodušení ti zbude navíc nejvýše jedna matice, tak nejhorší odhad je (log n + log n) násobení - což je samozřejmě pořád O(log n).