-
[Algoritm] logn, nlogn은 어떻게 도출할까programing/Algorithm 2019. 9. 13. 18:54
시간복잡도를 보다보면 $O(n\log n)$의 시간복잡도를 가지는 알고리즘들이 많습니다.
이 $n\log n$이란 값은 어떻게 도출되는걸까 생각을 해봤습니다.
간단하게 이진탐색을 예로 들어봅시다.
주어진 데이터는 $n$입니다.
이진탐색은 주어진 데이터를 반씩 쪼개서 둘 중의 한 부분에서 원하는 값을 찾습니다.
최악의 경우, 남은 데이터의 개수가 1이 될 때 까지 반씩 쪼개는 작업을 반복해야 합니다.
그렇다면 다음과 같은 수열을 유추할 수 있습니다.
$$n : 1, n/2 : 2, n/4 : 3, ..., 1 : x$$
이때, 연산의 횟수를 $x$라고 가정했을 때, $n$이 1일 경우 $x$는 무슨 값일까요?
1에서 2를 $x$번 곱해야 $n$이 되므로, $n = 1 \times 2^{x}$라는 방성식을 세울 수 있습니다.
여기서 $x$를 구하기 위해 $\log_{2}$를 양변에 취합니다.
그러면 $\log_{2} n = x\log_{2} 2$가 되며, 다시 풀면 $\log_{2} n = x$이 됩니다.
여기서 흔히 보이는 $\log n$이 나타납니다.
그런데 이건 $n\log n$과는 다릅니다.
이번에는 합병 정렬을 예로 들어봅시다.
병합정렬 합병 정렬은 반으로 나누는 과정은 똑같지만, 둘중 하나를 취사선택하던 이진탐색과 달리 둘 다 선택합니다.
즉, 남은 데이터의 개수가 1이 될 때 까지의 쪼갠 횟수를 $x$라고 했을 때, 쪼개진 데이터 그룹의 개수는 $n$이 됩니다.
따라서, 그룹의 개수 $n$을 곱하면 $n\log_{2} n$이 됩니다.
여기서 보통 밑을 생략해서 흔히 아는 $n\log n$이 나오게 됩니다.
(틀린 부분이 있다면 지적부탁드립니다..)
'programing > Algorithm' 카테고리의 다른 글
[BJ] 2309 - 일곱 난쟁이 (0) 2019.10.05 [BJ] 11724 - 연결 요소의 개수 (0) 2019.09.28 [Algorithm] 정렬 알고리즘에 대하여 3 (0) 2019.07.13 [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 4 (0) 2019.07.12 [Algorithm] 연속구간의 최대 합을 구하는 알고리즘 (0) 2019.07.09 댓글