백준 1629번을 통하여 알아낸 것



결론적으로 위와같이 나누기를 하여도 값은 동일하다.
그리고 분할정복을 할 때 아래와 같은 트리의 형태로 볼 수 있다.
몇단계까지 분할될지는 어떻게 알 수 있을까?
아래의 트리는 4단계로 나누어져있다.
만약 최상위 루트 N이 16이라면 간단히 logN으로 단계를 구할 수 있다.
.

0단계: 1 * O(N)
1단계: 2 * O(N/2)
2단계: 4 * O(N/4)
m단계: 2^m * O(N/(2^m)) = O(N)
그리고 위에서 말했듯이 단계를 구하는 식은 O(logN)
이를 곱해서 O(NlogN)이라는 시간복잡도를 구할 수 있다.
'알고리즘 메모 > 분할 정복 헷갈렸던 부분' 카테고리의 다른 글
| 이분탐색 시 헷갈렸던 부분 (0) | 2023.05.28 |
|---|---|
| 등차수열 (0) | 2022.11.28 |