07 분할정복

시간복잡도:

fastsum()과 recursivesum()이 종료하는 데 걸리는 시간은 함수 호출 횟수에 비례.

즉, recursivesum()은 n번의 함수호출

fastsum()은 호출될때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.

따라서 두 값의 상한은 모두 logn이므로 O(logn)!

부적절한 경우) 절반으로 나누는 알고리즘이 큰 효율 저하 불러오는 이유:

여러 번 중복되어 계산되면서 시간 소모 (=overlapping subproblems)

(→ 이런 경우는 8장 동적계획법으로 해결)

대표적 예제) 병합 정렬 Merge Sort

Merge Sort (평균/최악:O(nlogn)

7.2 문제: 쿼드 트리 뒤집기(QUADTREE, 하)

algospot.com :: QUADTREE

쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다.

https://algospot.com/judge/problem/read/QUADTREE

7.4 문제: 울타리 잘라내기 (FENCE, 중)

7.6 문제: 팬미팅 (FANMEETING, 상)

비교) Quick Sort (평균:O(nlogn)/최악:O(n^2)

Uploaded by Notion2Tistory v1.1.0