점근적 표기법

지금까지 선형 검색과 이진 검색법을 추측에 필요한 최대 횟수를 세는 것으로 분석해 보았습니다. 그런데 정말 알고 싶은 부분은 이 알고리즘이 얼마나 오래 걸리느냐 는 것이죠. 몇 번 인지보다는 실제 소요 시간 이 중요합니다. 선형 검색과 이진 검색의 실행 시간은 추측을 하고, 그 추측을 확인하는 시간도 관련 있지만 그 외에 고려해야 할 것도 있습니다.

알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존합니다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있습니다.

알고리즘의 실행 시간에 대해 두 부분으로 나누어 생각해 봅시다. 우선, 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다. 이건 직관적으로 이해가 될겁니다. 배열의 크기가 커지면 선형 검색과 이진 검색의 최대 추측 횟수가 함께 증가한다는 사실은 이미 확인했습니다. GPS를 생각해 봅시다. GPS가 만일 모든 골목길이 아니라 고속도로만 찾으면 길을 훨씬 금방 찾을 수 있을겁니다. 이처럼 입력값의 크기에 대한 함수 로 알고리즘 실행 시간을 생각할 수 있습니다.

두 번째는 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것입니다. 이것은 실행 시간의 성장률(rate of growth)이라고 부릅니다. 프로그램을 쉽게 유지할 수 있도록 불필요한 부분은 버리고 가장 중요한 부분만 추려내서 함수를 간소화해야 합니다. 예를 들어 입력값 크기가 $n$‍인 알고리즘이 $6n^2+100n+300$‍이라는 기계 명령을 받는다고 가정해 보겠습니다. $n$‍값이 어느 정도 커지면(이 경우는 20), $6n^2$‍은 나머지 항목인 $100n+300$‍보다 커집니다. 아래 차트에서 $n$‍값이 0부터 100일 때의 $6n^2$‍과 $100n+300$‍의 값을 볼 수 있습니다.

계수인 6과 나머지 항목인 $100n+300$‍을 빼고 생각하면 이 알고리즘의 실행 시간은 $n^2$‍으로 기하급수적으로 커지는 것을 볼 수 있습니다. 여기서 계수는 별로 중요하지 않습니다. $a>0$‍, $b$‍, $c$‍에서 실행 시간이 $a{n}^2+bn+c$‍라면 $a{n}^2$‍이 $bn+c$‍보다 크며, $n$‍이 커질수록 그 차이가 커지는 $n$‍의 값은 항상 존재합니다. 예를 들어, $0.6n^2$‍와 $1000n+3000$‍의 차트를 살펴봅시다. $n^2$‍의 계수는 10으로 나눴으며 나머지 항목의 두 상수의 값을 10배로 만들었습니다.

$0.6n^2$‍이 $1000n+3000$‍ 보다 클 때 $n$‍의 값은 증가했지만, 상수 값이 무엇이든 간에 이런 교차점은 반드시 존재합니다.

중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘의 실행 시간에서 중요한 부분인 성장률에 집중할 수 있습니다. 상수 계수와 중요하지 않은 항목을 제거한 것은 점근적 표기법(asymptotic notation)이라 합니다. 이제 점근적 표기법의 세 가지 형태를 살펴봅시다. 바로 big-$\mathrm{\Theta }$‍ 표기법, big-O 표기법, and big-$\mathrm{\Omega }$‍ 표기법입니다.

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