점근적 표기법 형태의 함수

입력 크기인 n에 관하여 알고리즘 실행 시간이 커지는 비율을 표현하기 위해 점근적 표기법을 사용할 경우에는 몇 가지를 알아 두어야 합니다.
쉬운 것부터 시작합시다. 알고리즘이 입력 크기와 상관없이 일정한 시간이 소요된다고 가정합시다. 예를 들어 오름차순으로 이미 정렬된 배열이 있고 여기서 최솟값을 찾아야 한다면 최솟값이 인덱스 0에 있을것이므로 일정한 시간이 소요될 것입니다. n의 함수를 점근적 표기법으로 사용하기로 하면 이 알고리즘은 Θ(n0) \Theta(n^0) 시간에 실행된다고 할 수 있습니다. 왜일까요? n, start superscript, 0, end superscript, equals, 1이기 때문입니다. 그러므로 알고리즘의 실행 시간은 상수값인 1 이내가 됩니다. 실제로 Θ(n0) \Theta(n^0) 라고 쓰지는 않고 Θ(1) \Theta(1) 라고 씁니다.
알고리즘에 Θ(log10n) \Theta(\log_{10} n) 시간이 소요된다고 가정해 봅시다. 알고리즘이 Θ(lgn) \Theta(\lg n) 시간(즉 Θ(log2n) \Theta(\log_2 n) 시간)이 걸린다고 할 수도 있습니다. 로그의 밑이 상수라면 점근적 표기법에서 어떤 밑 값을 사용하는지는 문제가 되지 않습니다. 왜 안될까요? 다음과 같은 수학 공식이 있기 때문입니다.
log, start subscript, a, end subscript, n, equals, start fraction, log, start subscript, b, end subscript, n, divided by, log, start subscript, b, end subscript, a, end fraction
이는 모든 양수인 a, b, n에 대해 성립합니다. 그러므로 만일 ab가 상수라면 log, start subscript, a, end subscript, nlog, start subscript, b, end subscript, nlog, start subscript, b, end subscript, a에 의해서만 달라지고 이는 점근적 표기법에서 무시할 수 있는 상수 값입니다.
그러므로 이진 검색의 최악의 경우의 실행 시간은 모든 양수값인 a에 대하여 Θ(logan) \Theta(\log_a n) 이라고 말할 수 있습니다. 왜일까요? 추측되는 횟수는 최대 lgn+1 \lg n + 1 인데 추측을 하고 테스트하는 과정에는 일정 시간이 소요되고 또한 초기화 작업과 리턴 과정도 일정한 시간이 걸리기 때문입니다. 현장에서 이진 검색은 Θ(lgn) \Theta(\lg n) 시간이 걸린다고 합니다. 컴퓨터공학자들은 2의 제곱으로 생각하길 좋아하기 때문입니다(게다가 Θ(log2n) \Theta(\log_2 n) 라고 쓰는 것보다 짧게 쓸 수 있기도 합니다.)
점근적 표기법을 사용하여 알고리즘을 분석할 때 종종 사용하는 함수들의 순서가 있습니다. ab가 상수이고 a, is less than, b라면 Θ(na) \Theta(n^a) 의 실행 시간은 Θ(nb) \Theta(n^b) 의 실행 시간보다 천천히 커집니다. 예를 들어 Θ(n) \Theta(n) , 즉 Θ(n1) \Theta(n^1) 의 실행 시간은 Θ(n2) \Theta(n^2) 의 실행 시간보다 천천히 커집니다. 지수가 정수일 필요도 없습니다. 예를 들어 Θ(n2) \Theta(n^2) Θ(n2n) \Theta(n^2 \sqrt{n}) , 즉 Θ(n2.5) \Theta(n^{2.5}) 의 실행 시간보다 천천히 커집니다.
Logarithms grow more slowly than polynomials. That is, Θ(lgn) \Theta(\lg n) grows more slowly than Θ(na) \Theta(n^a) for any positive constant a. But since the value of lgn \lg n increases as n increases, Θ(lgn) \Theta(\lg n) grows faster than Θ(1) \Theta(1) .
아래 리스트는 알고리즘을 분석할 때 자주 보게 되는 점근적 표기법의 함수들입니다. 커지는 속도가 느린 것부터 빠른 순서대로 표기했습니다. 이 리스트가 다는 아닙니다. 수많은 알고리즘은 아래에 적은 실행 시간 외의 실행 시간을 가질 수 있습니다.
  1. Θ(1) \Theta(1)
  2. Θ(lgn) \Theta(\lg n)
  3. Θ(n) \Theta(n)
  4. Θ(nlgn) \Theta(n \lg n)
  5. Θ(n2) \Theta(n^2)
  6. Θ(n2lgn) \Theta(n^2 \lg n)
  7. Θ(n3) \Theta(n^3)
  8. Θ(2n) \Theta(2^n)
a, is greater than, 1일 때 지수 함수 a, start superscript, n, end superscriptb가 상수인 모든 다항식 함수 n, start superscript, b, end superscript보다 빨리 커진다는 것을 주목하십시오.

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