지수와 로그 단원을 학습하면서 가장 먼저 생긴 의문은 로그는 밑에 따라 값이 분명히 달라지는데, 왜 알고리즘에서는 이를 자주 그냥 log n이라고 쓰는가였다. 교과서에서 $\log_2 8=3$, $\log_{10}100=2$처럼 밑이 바뀌면 결과가 달라진다는 사실을 배웠으므로, 처음에는 밑 차이가 있으면 계산 결과뿐 아니라 해석 자체도 크게 달라질 것이라고 생각했다. 그런데 컴퓨터공학 관련 자료를 읽다 보면 이진 탐색, 트리 탐색, 분할 정복 알고리즘의 성능을 설명할 때 밑을 엄격히 구분하지 않고 $O(\log n)$으로 표현하는 경우가 많았다. 이 차이가 단순한 표기 편의인지, 아니면 수학적으로 이유가 있는지 확인하고 싶었다.

특히 진로가 컴퓨터공학이기 때문에, 알고리즘의 성능을 수학적으로 읽는 능력이 중요하다고 판단했다. 검색 엔진, 데이터베이스, 추천 시스템처럼 많은 데이터를 빠르게 처리해야 하는 기술에서는 탐색 시간이 핵심 변인이다. 예를 들어 데이터 개수를 $n$개라 할 때, 선형 탐색은 최악의 경우 약 $n$번 비교가 필요하지만, 이진 탐색은 탐색 범위를 절반씩 줄이므로 단계 수가 로그와 연결된다. 가령 $n=1{,}024$일 때 선형 탐색은 최대 1,024회 비교가 가능하지만, 이진 탐색은 $\log_2 1024=10$단계 수준으로 해석된다. 이처럼 큰 수를 직접 다루기보다 몇 번의 절반 나누기가 필요한가로 바꾸어 읽는 과정에서 로그가 핵심 언어가 된다는 점이 흥미로웠다.

또한 데이터 크기가 커질수록 로그의 의미가 더 분명해진다. 가상의 비교 예시로 $n=10^3,10^6,10^9$를 두면 선형 탐색의 단계 수는 각각 1천, 100만, 10억으로 급격히 늘어난다. 반면 이진 탐색의 단계 수는 $\log_2 n$ 기준으로 약 10, 20, 30 단계 정도로 증가 폭이 매우 완만하다. 즉, 매우 큰 입력을 효율적으로 해석하려면 로그의 증가 성질을 이해해야 한다는 필요성이 드러난다. 이때 같은 $n$에 대해서도 $\log_2 n$과 $\log_{10} n$은 값이 다르므로, 이 차이가 실제 알고리즘 분석에서 어느 정도 중요한지 탐구할 필요가 생겼다.

따라서 이번 탐구의 중심 질문은 다음과 같이 구체화하였다.

이 질문에 답하기 위해 먼저 교과서에서 배운 로그의 정의, 밑의 의미, 증가 성질, 밑 변화 공식을 정리하고, 이후 이진 탐색의 단계 수와 연결하여 해석해 보고자 한다. 즉, 수학 교과 개념이 컴퓨터공학의 알고리즘 언어로 어떻게 확장되는지를 확인하는 것이 본 탐구의 출발점이다.

섹션 1에서 제기한 의문을 해명하기 위해 먼저 교과서의 기본 개념을 정리하였다. 로그는 지수 관계를 거꾸로 읽는 표현으로, 밑 $a$가 양수이고 $a\neq 1$일 때

로 정의된다. 여기서 $a$는 밑, $N$은 진수, $x$는 로그값이다. 이 정의는 큰 수를 단순한 수치가 아니라 '밑 $a$를 몇 번 곱해야 만드는가'라는 단계 수의 관점으로 해석하게 해 준다. 예를 들어 $2^5=32$이므로 $\log_2 32=5$이고, 이는 32를 2의 곱셈 단계 5번으로 읽을 수 있다는 뜻이다.

같은 진수 $N$이라도 밑이 달라지면 로그값이 달라진다. 예를 들어 $N=1{,}000$일 때

이다. 즉, 1,000은 10을 세 번 곱해 얻을 수 있지만 2를 기준으로 보면 약 10번의 곱셈 단계가 필요하다고 해석된다. 이 차이는 밑이 무엇이냐에 따라 한 단계에서 묶는 크기가 달라지기 때문이다. 밑이 크면 같은 수를 더 적은 단계로 표현하고, 밑이 작으면 더 많은 단계가 필요하다. 따라서 로그의 밑은 단순한 기호가 아니라, 수를 읽는 기준 단위를 정하는 역할을 한다.

또한 교과서에서 밑 $a>1$일 때 로그함수 $y=\log_a x$는 증가함수임을 배운다. 즉, $x$가 커질수록 $\log_a x$도 커지지만, 그 증가 속도는 직선 함수처럼 빠르지 않고 매우 완만하다. 가상의 확인값으로 $x=10,100,1000,10000$일 때 $\log_{10}x$는 각각 1, 2, 3, 4로 증가한다. 입력값은 10배씩 커졌는데 로그값은 1씩만 증가하므로, 로그는 큰 수를 압축하여 해석하는 데 적합하다는 점을 알 수 있다. 이 성질은 이후 이진 탐색처럼 데이터가 빠르게 줄어드는 구조를 설명하는 데 직접 연결된다.

가장 중요한 성질은 밑 변화 공식이다. 밑이 서로 다른 로그는 다음과 같이 연결된다.

여기서 $a,b,n>0$, $a\neq 1$, $b\neq 1$이다. 이 식은 서로 다른 밑의 로그가 완전히 다른 함수가 아니라, 상수배 관계에 있음을 보여 준다. 예를 들어

이므로 두 로그는 값은 다르지만 일정한 비율로 연결된다. 이는 섹션 1에서 제기한 '밑이 다른데 왜 비슷하게 쓰이는가'라는 질문의 핵심 단서가 된다.

정리하면, 로그의 정의는 수를 곱셈 단계 수로 읽게 하고, 밑의 차이는 그 단계의 기준을 바꾸며, 증가 성질은 큰 입력을 압축해서 해석하게 한다. 특히 밑 변화 공식은 서로 다른 로그가 상수배로 이어진다는 사실을 제공하므로, 이후 섹션 3에서 이진 탐색 단계 수를 $\log_2 n$으로 해석하고, 섹션 4에서 $\log_2 n$, $\log_{10} n$, $\log n$을 복잡도 관점에서 비교하는 직접적인 근거가 된다.

섹션 1에서 제기한 문제의식과 섹션 2에서 정리한 로그의 정의를 바탕으로, 이번에는 이진 탐색의 단계 수가 왜 로그로 표현되는지를 1:1로 연결해 보았다. 이진 탐색은 정렬된 데이터에서 가운데 값을 기준으로 범위를 절반씩 줄이는 방법이다. 처음 데이터 수를 $n$개라 하면, 한 번 비교한 뒤 남는 후보 수는 최대 $n/2$, 두 번 비교하면 $n/4$, 세 번 비교하면 $n/8$이 된다. 따라서 $k$번 비교 후 남는 범위는 다음과 같이 나타낼 수 있다.

이 수열 구조 자체가 '절반으로 나누는 과정을 몇 번 반복하는가'를 묻고 있으므로, 로그와 자연스럽게 연결된다.

탐색이 끝나는 시점은 후보가 1개 이하가 되는 순간으로 볼 수 있다. 이를 식으로 쓰면

이다. 양변에 $2^k$를 곱하면

이 되고, 다시 지수와 로그의 관계를 이용하면 필요한 단계 수 $k$는 $\log_2 n$과 연결된다. 즉, 2를 몇 번 곱해야 $n$ 이상이 되는가가 곧 이진 탐색의 비교 횟수 해석이 된다. 이는 섹션 2에서 정리한 $a^x=N \Leftrightarrow \log_a N=x$를 알고리즘 상황에 적용한 사례라고 볼 수 있다.

구체적인 값으로 확인하면 더 분명하다. $n=8=2^3$이면 $8\to 4\to 2\to 1$로 줄어들어 정확히 3단계가 필요하므로 $\log_2 8=3$과 일치한다. $n=16=2^4$이면 4단계, $n=1024=2^{10}$이면 10단계가 필요하다. 반면 $n=1000$처럼 2의 거듭제곱이 아닌 경우에는 정확히 나누어떨어지지 않으므로 최대 단계 수를

로 해석하는 것이 적절하다. 실제로 $\log_2 1000\approx 9.97$이므로 최대 10단계로 본다. 이처럼 이진 탐색의 단계 수는 정확한 값으로는 올림 기호와 연결되지만, 전체 구조는 분명히 $\log_2 n$의 성장 방식에 따른다^[1].

이 과정에서 한 가지 연구 공백도 드러났다. 이진 탐색 자체는 데이터를 2분할하므로 실제 단계 수 해석에는 $\log_2 n$이 가장 직접적이다. 그러나 알고리즘 복잡도 설명에서는 종종 $\log n$처럼 밑을 생략한 표기가 등장한다. 교과서의 로그 정의만으로는 왜 실제 단계 수는 2를 밑으로 하는데, 성장률 표기에서는 밑 차이를 크게 문제 삼지 않는지 충분히 설명되지 않는다. 즉, 실제 비교 횟수의 계산과 복잡도 표기의 추상화 사이에 해석 차이가 존재한다.

따라서 다음 섹션에서는 섹션 2의 밑 변화 공식과 이번 섹션의 이진 탐색 단계 수 해석을 결합하여, $\log_2 n$, $\log_{10} n$, $\log n$이 값에서는 다르지만 왜 복잡도 해석에서는 같은 성장 구조로 묶이는지 심화 분석하고자 한다^[1].