7장: 분할 정복 - 2 (180p ~ 194p)

<도입>

 

1. 예제: 병합 정렬과 퀵 정렬

• 병합 정렬은 둘로 나누는 과정에서 O(1)의 시간 복잡도가, 분할 한 수열을 다시 합 칠 때 O(n)의 고정된 계산을 하므로 시간 복잡도는 O(nlgn)이다.
• 퀵 정렬은 partition을 기준으로 나누는 과정에서 partition이 가운데가 된다는 것을 가정하면 O(nlgn)인 것이 알려져이다.
• 책에는 없지만 고정적으로 시간 복잡도가 O(nlgnl)인 병합 정렬을 사용하는 것이 조금 더 안정적이지 않을까 싶다.

2. 예제: 카라츠바의 빠른 곱셈 알고리즘

• 기본적인 사칙연산으로 곱셈을 구현할 경우 \(O(n^{2})\)의 시간 복잡도를 나타내게 된다. 그러나 이를 분할 정복을 이용한 카라츠바 알고리즘을 사용하면 \(O(n^{lg3})\)으로 계산을 줄일 수 있다.

3. 문제: 쿼드 트리 뒤집기 (문제ID: QUADTREE, 난이도: 하)

• 4등분 한 것을 뒤집은 것을 뒤집으면 된다.