- Divide and Conquer의 기본은 Binary search를 예로 들 수 있다(시간복잡도와 call-by-value)
- Merge sort 또한 Divide and conquer(계속 반으로 갈라서 한 개가 되면 크기 비교하며 합치기)
- online은 실시간으로 넣는것(hash), offline은 input 다 넣고 처리
- inplace sort는 배열 제자리에서 처리하는가, stable은 같은 값들을 위치 조정하지 않는가
- stable은 특히 주의 깊게 보기(stable이 좋긴 하지만 실제 제약과 소모값이 있어서 unstable이 빠르긴함)
- quick sort 또한 Divide and conquer(pivot 기준으로 ++와 -- 하면서 비교하기)
- quick sort가 빠른 이유는 register에 피벗 하나만 올리고 다음 값들과 비교하기 때문이다
- quick의 함수 stack이 많이 쌓이는 문제 해결하기 위해 범위가 작은 피벗 부분부터 먼저 처리(random 처리도 가능)
- Strassen's Matrix Multiplication 은 기존 mult 8/ add 4 에서 mult 7/ add 18 로 mult를 줄일 수 있었다
- arithmatic with large integers 문제
'Archived(CSE) > 알고리즘' 카테고리의 다른 글
기말 정리 (0) | 2019.06.10 |
---|---|
Chap 4. Greedy Approach (0) | 2019.04.18 |
Chap 3. Dynamic Programming (0) | 2019.04.18 |