[알고리즘] 시간복잡도 logN, N*logN 이해하기 (스크랩)

시간복잡도 logN 관련하여 잘 정리되어있는 블로그가 있어 스크랩한다.

원본 출처 블로그에 가면 더 자세한 설명이 있다.

 

---

시간복잡도를 보다보면 O(nlogn)의 시간복잡도를 가지는 알고리즘들이 많습니다.

이 nlogn이란 값은 어떻게 도출되는걸까 생각을 해봤습니다.

 

간단하게 이진탐색을 예로 들어봅시다.

주어진 데이터는 n입니다.

이진탐색은 주어진 데이터를 반씩 쪼개서 둘 중의 한 부분에서 원하는 값을 찾습니다.

최악의 경우, 남은 데이터의 개수가 1이 될 때 까지 반씩 쪼개는 작업을 반복해야 합니다.

그렇다면 다음과 같은 수열을 유추할 수 있습니다.

 

n:1,n/2:2,n/4:3,...,1:x

이때, 연산의 횟수를 x라고 가정했을 때, n이 1일 경우 x는 무슨 값일까요?

 

1에서 2를 x번 곱해야 n이 되므로, n=1×2^x=1×2라는 방성식을 세울 수 있습니다.

여기서 x를 구하기 위해 log2를 양변에 취합니다.

그러면 log_2 n=xlog_2 2가 되며, 다시 풀면 log_2 n=x 이 됩니다.

여기서 흔히 보이는 log n이 나타납니다.

 

그런데 이건 n log n과는 다릅니다.

 

합병 정렬은 반으로 나누는 과정은 똑같지만, 둘중 하나를 취사선택하던 이진탐색과 달리 둘 다 선택합니다.

즉, 남은 데이터의 개수가 1이 될 때 까지의 쪼갠 횟수를 x라고 했을 때, 쪼개진 데이터 그룹의 개수는 n이 됩니다.

따라서, 그룹의 개수 n을 곱하면 n log_2 n이 됩니다.

여기서 보통 밑을 생략해서 흔히 아는 n log n이 나오게 됩니다.

 

---

출처  - https://kjwsx23.tistory.com/339

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

---

다시 말해서, 자식 노드의 수가 m개인 트리로 N개의 자료에서 원하는 값을 탐색하는 알고리즘의 시간 복잡도는 log_m(N)이 된다.

 

출처 - https://neos518.tistory.com/145

logN의 시간 복잡도가 나오는 이유