[JS 알고리즘&자료구조] 로그와 이제까지의 요약

로그를 학습해야만 하는 이유는 어떤 알고리즘들은 앞서 배웠던 O(1), O(n), O(n²)처럼 Big O가 간단하지 않기 때문이다. 😒 몇 가지 Big O 표기법들은 이와는 다르게 좀 더 어렵거나 흔하지 않은 수학 공식이 포함된 경우도 있다. 그 중 자주 나오는 개념이 로그이다. 

우선 로그란 뭘까? 로그함수는 지수 함수의 역함이다. 나눗셈과 곱셈이 짝인 것처럼 로그 함수와 지수 함수는 짝이다. 아래의 수학식을 보자.

log₂(8) = 3

위의 식은 "2의 몇승이 8이 되나요?"를 묻는다. 

log₂(값) = 지수

위의 로그 함를 정리하면 '2를 밑으로 하는 어떤 값의 로그는 어떤 지수값과 같다"라고 할 수 있다. 예시를 이진 로그로 들었다고 해서 항상 2가 들어가는 것은 아니다. 어떤 숫자든 들어갈 수 있다. 이진 로그가 가장 흔하긴 해도 말이다. 

어쨌든 앞에서 반복적으로 얘기해왔듯이 우리는 큰 그림만을 보기 때문에 로그 함수의 밑에 깔리는 숫자는 무시하겠다. 이진 로그의 '2'를 무시하겠다는 말이다. 즉 앞으로 log₂는 그냥 log라고 봐도 된다. 

로그 함수의 간단한 규칙을 설명하면 어떤 이진 로그를 대략 계산하기 위해서는 그 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수이다. 무슨 말인지 이해하기 위해 아래 그림을 보자.

나눠지는 횟수가 지수가 된다

규칙은 알았으나 사실 구체적인 계산이 그렇게 중요하지는 않다. 우리에게 중요한 것은 추세이다. 화면에 그래프로 어떻게 보여지는 지 보도록 하자. 

출처 : Thomas J Cortina from Carnegie Mellon University

위의 그래프를 보면 로그 시간 복잡도, O(log n)은 처음에는 조금 가파르지만 서서히 경사가 완만해진다.이는 정말 좋은 시간 복잡도를 가졌다는 것을 나타내며 만약 알고리즘이 로그 시간 복잡도를 가졌다면 훌륭하다고 볼 수 있다. n이 커진다고 해도 시간이 그렇게 크게 늘어나지 않기 때문이다.

여기까지 요약하자면 알고리즘의 성능을 분석하기 위해서는 Big O 표기법을 사용한다. 입력의 크기가 늘어날수록 전체적인 추세와 연관이 있으며 시간 복잡도나 공간 복잡도가 어떻게 증가하는지를 보는 것이 중요하다. 정확도보다는 추세가 중요하며 하드웨어의 사양은 복잡도와는 전혀 무관하다. 그리고 마지막으로 Big O 표기법은 어디에나 적용될 수 있다!