[Algoritm] logn, nlogn은 어떻게 도출할까

시간복잡도를 보다보면 $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$이 나오게 됩니다.

 

(틀린 부분이 있다면 지적부탁드립니다..)