[Algorithm] O(logN) == O(log₂N)

아주아주 오랜만에 묵혀두었던 기초 CS 꺼내보기..! ( ·•︡_•︠) 

---

 

CS에서 시간 복잡도 얘기할 때 자주 듣는 "O(logN)"이라는 표현, 들어봤지? 여기서 궁금할 수도 있는데, O(logN)과 O(log₂N)이 같은 거라는 걸 알아두면 좋아. 쉽게 말하면, O(logN)은 O(log₂N)의 줄임말이야. 왜냐면 컴퓨터 과학에서 로그의 밑(base)은 보통 2로 취급되거든. 그래서 "logN"이라고만 써도 사실은 "log₂N"을 의미하는 거야. 

 

 

 

 

 

 

그러니까, O(logN)과 O(log₂N)은 같은 의미를 가진다는 거지. 실제로 시간 복잡도를 따질 때, 로그의 밑이 무엇이냐는 크게 상관없어. 밑이 달라진다고 해서 O(log₂N)이 O(log₃N)처럼 다른 표기가 되진 않아. 왜냐면 로그의 밑을 바꾸더라도 전체 시간 복잡도에 크게 영향을 주지 않기 때문에, 빅오 표기법에서는 로그의 밑을 무시하고 그냥 O(logN)으로 간단하게 쓰는 거야.

그래서 어떤 알고리즘이 O(logN) 시간 복잡도를 가진다고 하면, 데이터 원소가 N개일 때 그 알고리즘이 몇 단계나 걸릴지 생각해 볼 수 있는 거지. 예를 들어, 원소가 8개 있을 때 log₂8은 3이니까, 이 알고리즘은 총 3단계가 걸린다는 의미가 되는 거야. 이 방식으로 작동하는 대표적인 알고리즘이 바로 이진 검색(Binary Search)이고, 데이터가 많아도 굉장히 빠르게 찾을 수 있는 이유도 여기에 있어.

결론적으로, O(logN)과 O(log₂N)이 같은 의미라는 걸 이해하는 게 중요해. 이걸 알고 있으면 시간 복잡도를 더 정확하게 이해하고, 빅오 표기법에 익숙해지는 데 도움이 될 거야!