반응형
1. Matrix Multiplication
N*N 배열 두개를 곱하는 과정은 O(N^3)이 소요된다.
한칸만드는데 O(N) * n^2개 칸 존재
여기서도 Divide and Conquer 를 사용할 수 있다.
이렇게 되면 식이 아래와같이 된다.
T(N) = 8T(n/2) = 2^3 T(n/2) = 2^6T(n/2) = ... =(2^3)^logn
2. Strassen Alg
3. Karatsuba Alg
n bit 곱하기 n bit 는O(n^2)에 할 수 있다.
하지만 Karatsuba Alg를 사용하면 n에 가깝게 수행할수있다.
반응형
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ]Dynamic Programming : Select Working Days , Path counting (0) | 2022.10.18 |
|---|---|
| [ 알고리즘 ] Dynamic Programming : Fibonacci Number (0) | 2022.10.18 |
| [ 알고리즘 ] Convex Hull : CCW, Brute-Force-ish, Package Wrapping, Graham Scan, Plane Sweeping, Divide and Conquer, Farthest Point (2) | 2022.10.18 |
| [ 알고리즘 ] Closest pair (0) | 2022.10.17 |
| [ 알고리즘 ] Median Problem (0) | 2022.10.17 |