ps (1) 썸네일형 리스트형 Deterministic Verification of Integer Matrix Multiplication in Quadratic Time 세 개의 $n \times n$ 크기의 정수 행렬 $A, B, C$에 대해 $AB == C$인지 $O(N^2)$에 판별하는 알고리즘을 알아보자.PS에서 보통 사용되는 $O(KN^2)$의 Freivalds' algorithm을 개선한 버전으로 생각할 수도 있지만, 이 알고리즘은 PS에선 쓰이지 않는다. 먼저, naive하게 $AB$를 계산하고 $C$와 비교하는 알고리즘의 시간복잡도는 $O(N^3)$이다. $AB$의 계산에서 $n \times n$ 크기의 두 행렬을 곱해야 하므로 $O(N^3)$의 계산이 필요하고, 계산된 결과가 $C$와 일치하는지 확인하는 데에 $O(N^2)$의 비교가 필요하기 때문이다. 조금 더 효율적인 방법이 없을까? $AB=C$라면 임의의 $n \times 1$ 열벡터 $x$에 대.. 이전 1 다음