logn과 nlogn

1. logn

이진 탐색 일때 => 반으로 쪼개면서 둘 중에 한 부분에서 원하는 값을 찾음.
예. 8 --> 4 & 4 --> 2&2 / 2&2 --> 1&1/1&1 // 1&1/1&1
👉 한 부분만 보는거니까 총 3번, 즉 $\log_{2}{8}$으로, O($\log_{}{n}$)이라고 할 수 있다.

2. nlogn

그러나, 이진 탐색이 아닌 머지소트일때는 둘 중에 한 부분이 아니 모든 부분을 탐색해야 한다. 그러므로, 3 * 8 즉, $\log_{2}{8}$ 곱하기 8을 해야한다. 즉 , O(nlogn)이라고 할 수 있다.

정리 : O($\log_{}{n}$)은 한 번 쪼갠 횟수만 계산하는 것, O(nlogn)은 쪼갠 횟수의 모든 그룹을 계산하는 것

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