본문 바로가기

알고리즘/Approximation1

Freivald's algorithm 개요 Approximation, 확률론 A×B=C를 O(kN^2)에 해결하기 접근 기존의 행렬곱 일반적인 상황은 아니지만, 두 행렬의 곱이 다른 행렬과 같은지 확인해야 하는 상황이 있다. A×B=C를 검증한다고 가정하자. 만약 A,B,C의 크기가 각각 [p,m], [m,q], [p,q] 라면 곱셈 연산을 하는데 p×m×q번의 연산이 필요하고, 정수행렬 C를 만들기 위해 p×q×4 만큼의 메모리가 필요하다. 왜냐? 일반적으로 행렬곱 계산은 아래와 같이 해주기 때문이다. for (i = 0~p) for (j = 0~q) for (k = 0~m) C[i][j]+=A[i][k]*B[k][j] 크기가 100×100정도라면 큰 문제가 아니다. 하지만 1000이면 1e9번의 연산을 해야하고, 시간을 1분을 주지 않는.. 2023. 3. 12.

티스토리툴바