728x90
Matrix Multiplication
nxn 행렬 두개를 곱하면 계산할 값 = n^2개
하나 계산하는 데에 n개의 계산
=> 덧셈말고 곱셈만 고려했을 때 O(n^3)
같은 값이 곱해지는 경우가 없다! 더 빨리할 수 있는가?
실용적이진 않지만 특이한 방법
원래 행렬끼리 곱하듯이 재귀로 => 그냥 곱하는 것보다 느림
원래 n^3인데 분할정복해도 n^3?
더하기도 계산할 수 있지만 곱하기만 세겠다.
R: 1
S: 1
T: 1
U: 1
V: 1
W: 1
X: 1
변수가 7개x곱하기 1번씩
곱하기8번 => 곱하기7번이 된다.
이 정도 차이가 의미가 있냐?
웬만하면 의미가 없지만 웬만하지 않은 곳이 많다. ex) 물리..과학 계산..
n^2보다 빠르게는 못한다.
입력, 출력사이즈가 n^2이기 떄문에.
n^3보다는 빠르다.
n^2.807
더 빠른걸 만들었다.
90년대 초 논문
n^2.376
2014년 논문
n^2.372873