큰 행렬 곱셈의 복잡도

큰 행렬을 곱하기 위해 알려진 가장 빠른 알고리즘의 시간 복잡도는 얼마입니까?큰 행렬 곱셈의 복잡도

도달 할 수있는 이론적 최적 시간 복잡도는 어떻습니까?

2014-09-22 Joseph K

SO에 관한 질문을 게시하기 전에 먼저 조사를 해 보는 것이 중요합니다. 위키 백과를 사용해 보셨습니까? https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication –

이것은 활발한 연구 분야이므로이 답변은 곧 유효 기간이 만료 될 수 있습니다. :-)

현재 가장 빠른 매트릭스 곱셈 알고리즘은 시간 O (n ^2.373), due to a result by Virginia Williams에서 실행됩니다. 이 알고리즘은 실제로 알고리즘의 큰 계열로서 전체 시간 제한을 제공하는 복잡한 비선형 시스템 방정식을 발생시킵니다. 실제로 더 나은 솔루션을 찾아 경계를 개선하는 방법을 연구하는 사람들이 있습니다. 그 방정식에. 나는이 알고리즘이 단지 이론적 인 관심이라고 생각한다.

행렬 곱셈의 성배는 O (n) - 시간 행렬 곱셈 알고리즘이며 그러한 알고리즘이 존재하는지 여부는 여전히 열려있는 문제입니다. o (n) 시간 알고리즘은 곱하기 위해 행렬의 모든 항목을 읽을 수 없기 때문에 이것은 이론적 한계입니다.

희망이 도움이됩니다.

출처

2014-09-22 20:11:11 templatetypedef

예. 제가 알고있는 가장 합리적인 사람들은 행렬 곱셈이 O (n^2 + ε)라고 생각합니다. O (n^2)는 아주 놀랄 것입니다. –

참고해 주셔서 감사합니다! – Codor

큰 행렬 곱셈의 복잡도

답변

관련 문제