complejidad de la multiplicación de matrices

Question

Para $n\times n$ matrices dimensionales, se sabe que el cálculo de $\operatorname{tr}\{AB\}$ necesita $n^2$ multiplicaciones escalares. ¿Cuántas multiplicaciones escalares se necesitan para calcular $\operatorname{tr}\{ABCD\}$ ? Tenga en cuenta que $\operatorname{tr}$ significa la traza de una matriz.

Answer 1

Como usted dice, la evaluación de un rastro es el orden $n^2$ -Tienes $n$ términos diagonales, cada uno de los cuales toma $n$ multiplica y $n$ añade para evaluar. El final $n$ se dominan las adiciones. Para hacer la traza $ABCD$ No veo nada mejor que el primer hallazgo $AB$ y $CD$ cada uno de los cuales es $n^3$ operaciones, o, si eres más inteligente $n^{2.373}$ . A continuación, utilice su $n^2$ cálculo de trazos, dando la orden $n^3$ o $n^{2.373}$ . Esto funcionará para cualquier número de Puede haber algo más inteligente por ahí.