지금까지 선형 검색과 이진 검색법에 대해 추측할 수 있는 최대 횟수를 세어 분석하였습니다. 그런데 정말 알고 싶은 부분은 이 알고리즘이 얼마나 오래 걸리느냐 는 것이죠. 몇 번 인지보다는 실제 소요 시간 이 중요합니다. 선형 검색과 이진 검색의 실행 시간은 추측을 하고, 그 추측을 확인하는 시간도 관련있지만 그 외에 시간도 고려해야 합니다.
알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존합니다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있습니다.
알고리즘의 실행 시간에 대해 두 부분으로 나누어 생각해 봅시다. 우선, 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다. 이건 직관적으로 이해가 될겁니다. 배열의 크기가 커지면 선형 검색과 이진 검색의 최대 추측 횟수가 함께 증가한다는 사실은 이미 확인했습니다. GPS를 생각해 봅시다. GPS가 만일 모든 골목길이 아니라 고속도로만 찾으면 길을 훨씬 금방 찾을 수 있을겁니다. 이처럼 입력값의 크기에 대한 함수 로 알고리즘 실행 시간을 생각할 수 있습니다.
두 번째는 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것입니다. 이것은 실행 시간의 성장률(rate of growth)이라고 부릅니다. 프로그램을 쉽게 유지할 수 있도록 불필요한 부분은 버리고 가장 중요한 부분만 추려내서 함수를 간소화해야 합니다. 예를 들어 입력값 크기가 n인 알고리즘이 6, n, start superscript, 2, end superscript, plus, 100, n, plus, 300이라는 기계 명령을 받는다고 가정해 보겠습니다. n값이 어느 정도 커지면(이 경우는 20), 6, n, start superscript, 2, end superscript은 나머지 항목인 100, n, plus, 300보다 커집니다. 아래 차트에서 n값이 0부터 100일 때의 6, n, start superscript, 2, end superscript100, n, plus, 300의 값을 볼 수 있습니다.
6n^2 vs 100n+300
계수인 6과 나머지 항목인 100, n, plus, 300을 빼고 생각하면 이 알고리즘의 실행 시간은 n, start superscript, 2, end superscript으로 기하급수적으로 커지는 것을 볼 수 있습니다. 여기서 계수는 별로 중요하지 않습니다. a, is greater than, 0, b, c에서 실행 시간이 a, n, start superscript, 2, end superscript, plus, b, n, plus, c라면 a, n, start superscript, 2, end superscriptb, n, plus, c보다 크며, n이 커질수록 그 차이가 커지는 n의 값은 항상 존재합니다. 예를 들어, 0, point, 6, n, start superscript, 2, end superscript1000, n, plus, 3000의 차트를 살펴봅시다. n, start superscript, 2, end superscript의 계수는 10으로 나눴으며 나머지 항목의 두 상수의 값을 10배로 만들었습니다.
6n^2 vs 100n+300
0, point, 6, n, start superscript, 2, end superscript1000, n, plus, 3000 보다 클 때 n 의값은 증가했지만, 상수 값이 무엇이든 간에 이런 교차점은 반드시 존재합니다.
중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘의 실행 시간에서 중요한 부분인 성장률에 집중할 수 있습니다. 상수 계수와 중요하지 않은 항목을 제거하면 점근적 표기법(asymptotic notation)을 사용합니다. 이제 점근적 표기법의 세 가지 형태를 살펴봅시다. 바로 big-Θ \Theta 표기법, big-O 표기법, and big-Ω \Omega 표기법입니다.

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