it-swarm-pt.tech

complexidade de tempo do algoritmo de multiplicação de matrizes

Eu vim com esse algoritmo para multiplicação de matrizes. Li em algum lugar que a multiplicação de matrizes tem uma complexidade de tempo de o (n ^ 2). Mas acho que meu algoritmo dará o (n ^ 3). Não sei como calcular a complexidade do tempo de loops aninhados. Então, por favor me corrija.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]
19
zedai

O algoritmo ingênuo, que é o que você obtém após corrigi-lo, conforme observado nos comentários, é O (n ^ 3).

Existem algoritmos que reduzem um pouco isso, mas é improvável que você encontre uma implementação O (n ^ 2). Acredito que a questão da implementação mais eficiente ainda esteja aberta.

Veja este artigo da Wikipedia em Multiplicação de matrizes para obter mais informações.

19
Don Roby

Usando álgebra linear, existem algoritmos que alcançam uma complexidade melhor que o O ingênuo (n3) O algoritmo Solvay Strassen atinge uma complexidade de O (n2,807) reduzindo o número de multiplicações necessárias para cada sub-matriz 2x2 de 8 para 7.

O algoritmo de multiplicação de matriz conhecido mais rápido é o algoritmo Coppersmith-Winograd com uma complexidade de O (n2,3737) A menos que a matriz seja enorme, esses algoritmos não resultam em uma grande diferença no tempo de computação. Na prática, é mais fácil e rápido usar algoritmos paralelos para multiplicação de matrizes.

41
viswanathgs

A maneira padrão de multiplicar uma matriz m por n por uma matriz n por p tem complexidade O (mnp). Se tudo isso é "n" para você, é O (n ^ 3), não O (n ^ 2). EDIT: não será O (n ^ 2) no caso geral. Mas existem algoritmos mais rápidos para tipos específicos de matrizes - se você souber mais, poderá fazer melhor.

10
Sean Owen

Na multiplicação de matrizes existem 3 para loop, estamos usando, pois a execução de cada loop requer complexidade de tempo O(n). Então, por três loops, torna-se O(n^3)

1
user2024721