Big O Notation(빅오 표기법) #6

💡 **[Colt Steele](https://www.udemy.com/user/coltsteele/) 의 JavaScript Algorithms and Data Structures Masterclass의 강의를 참고하여 정리한 글입니다.**

6. 로그와 시간 복잡도

로그란?

---

로그는 간단히 말해 지수(n^2, 2^n 등)의 역수이다.

간단한 이해를 돕는 예제로 log2(8) 은 3 이다. 즉, 2^3=8 이라는 말과 같다.

일반적으로 log2(n)은 그냥 log(n) 으로 첨자 처럼 생략된다.

로그의 시간 복잡도

---

O(log n) 의 시간 복잡도

다음에서 보듯 O(log n)의 시간 복잡도는 처음엔 가파르지만 점점 가파른 정도가 줄어든다라는 것을 알 수 있다.

즉, n 의 값이 커지면 커질 수록 시간 복잡도에서 큰 차이를 내지 않고 점점 일정해지는 듯한 차이를 보인다는 것이다.

O(nlog n) 의 시간 복잡도

O(log n) 과는 반대로 O(nlog n) 의 시간 복잡도는 n 의 크기가 적더라도 시간 복잡도의 상승폭이 크다는 것을 볼 수 있다.

물론 O(n^2) 처럼 지수함수 보다 낫겠으나 좋은 의미를 지니는 것은 아니란 것을 알 수 있다.

3.에서 보았듯이 로그는 다음과 같은 특정 알고리즘에서 등장하게된다.

💡 1. O(log n) : 이진트리 2. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort) 3. 검색 알고리즘 4. 재귀 알고리즘(공간 복잡도에서 효율을 보임)