점근적 표기법 형태의 함수

입력 크기인 $n$‍에 따라 알고리즘 실행 시간의 성장률을 표현할 때 점근적 표기법을 사용할 경우에는 몇 가지를 알아 두어야 합니다.

쉬운 것부터 시작합시다. 알고리즘이 입력 크기와 상관없이 일정한 시간이 소요된다고 가정합시다. 예를 들어 오름차순으로 정렬한 배열이 있고 여기서 최솟값을 찾아야 한다면 최솟값이 인덱스 0에 있으므로 일정한 시간이 소요될 것입니다. $n$‍의 함수를 점근적 표기법으로 사용하기로 하면 이 알고리즘은 $\mathrm{\Theta }(n^0)$‍ 시간에 실행된다고 할 수 있습니다. 왜일까요? $n^0=1$‍이기 때문입니다. 그러므로 알고리즘의 실행 시간은 상수값인 1 이내가 됩니다. 실제로 $\mathrm{\Theta }(n^0)$‍라고 쓰지는 않고 $\mathrm{\Theta }(1)$‍라고 씁니다.

알고리즘에 $\mathrm{\Theta }({\log }_{10}n)$‍ 시간이 소요된다고 가정해 봅시다. 알고리즘이 $\mathrm{\Theta }({\log }_{2}n)$‍이 걸린다고 할 수도 있습니다. 로그의 밑이 상수라면 점근적 표기법에서 어떤 밑 값을 사용하는지는 문제가 되지 않습니다. 왜 그럴까요? 다음과 같은 수학 공식이 있기 때문입니다.

이는 모든 양수인 $a$‍, $b$‍, $n$‍에 대해 성립합니다. 그러므로 만일 $a$‍와 $b$‍가 상수라면 ${\log }_{a}n$‍과 ${\log }_{b}n$‍은 ${\log }_{b}a$‍에 의해서만 달라지고 이는 점근적 표기법에서 무시할 수 있는 상수 값입니다.

그러므로 이진 검색의 최대 실행 시간은 모든 양수 값인 $a$‍에 대하여 $\mathrm{\Theta }({\log }_{a}n)$‍이라고 말할 수 있습니다. 왜 그럴까요? 추측 횟수는 최대 ${\log }_{2}n+1$‍번인데 추측을 하고 테스트하는 과정, 반복문을 설정하고 반환하는 시간은 상수이기 때문입니다. 보통 이진 검색은 $\mathrm{\Theta }({\log }_{2}n)$‍ 시간이 걸린다고 쓰는데, 이는 대부분 컴퓨터공학자들이 2의 제곱으로 수를 세는 것을 좋아하기 때문입니다.

점근적 표기법을 사용하여 알고리즘을 분석할 때 종종 사용하는 함수들의 순서가 있습니다. $a$‍와 $b$‍가 상수이고 $a<b$‍라면 $\mathrm{\Theta }(n^a)$‍의 실행 시간은 $\mathrm{\Theta }(n^b)$‍의 실행 시간보다 천천히 커집니다. 예를 들어 $\mathrm{\Theta }(n)$‍, 즉 $\mathrm{\Theta }(n^1)$‍의 실행 시간은 $\mathrm{\Theta }(n^2)$‍의 실행 시간보다 천천히 커집니다. 지수가 정수일 필요도 없습니다. 예를 들어 $\mathrm{\Theta }(n^2)$‍는 $\mathrm{\Theta }(n^2\sqrt{n})$‍, 즉 $\mathrm{\Theta }(n^{2.5})$‍의 실행 시간보다 천천히 커집니다.

다음 그래프는 $n$‍, $n^2$‍, $n^{2.5}$‍이 증가하는 정도를 비교합니다:

로그 함수는 다항식보다 천천히 증가합니다. 즉 $\mathrm{\Theta }({\log }_{2}n)$‍은 $모든$‍ 양수 a 에 대하여 $\mathrm{\Theta }(n^a)$‍보다 천천히 증가하게 됩니다. 그렇지만 $n$‍ 이 커지면 ${\log }_{2}n$‍의 값도 커지기 때문에 $\mathrm{\Theta }({\log }_{2}n)$‍은 $\mathrm{\Theta }(1)$‍보다는 빨리 커지게 됩니다.

다음 그래프는 $1$‍, $n$‍, ${\log }_{2}n$‍이 증가하는 정도를 비교하는 그래프입니다:

다음은 알고리즘을 분석할 때 자주 보게 되는 함수를 점근적 표기법으로 쓰고, 커지는 속도가 느린 것부터 나열한 것입니다.

$a>1$‍일 때 지수 함수 $a^n$‍는 $b$‍가 상수인 모든 다항식 함수 $n^b$‍보다 빨리 커집니다.

위에 있는 것이 함수의 전부는 아니지만, 공부를 하다 보면 만나게 될 겁니다!

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.