선형 검색을 구현한 간단한 예를 살펴봅시다:
var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // 찾은 경우
    }
  }
  return -1;  // 찾지 못한 경우
};
배열의 크기(array.length)를 n n 이라 합니다. for 문은 최대 n n 번 반복될 수 있고, 이런 최악의 경우는 배열에 찾는 값이 존재하지 않을 때 발생합니다.
for 반복문을 수행할 때마다 다음이 실행되어야 합니다:
  • guessarray.length를 비교합니다
  • array[guess]targetValue를 비교합니다
  • 가능하다면 guess의 값을 반환합니다
  • guess를 증가시킵니다
각각의 계산은 실행하는 데에 어떤 상수만큼의 시간이 걸립니다. for 문을 n n 번 반복하면 총 계산에 걸리는 시간은 c1n c_1 \cdot n 으로, c1 c_1 은 반복 한 번에 걸리는 시간을 나타냅니다. 여기서 c1 c_1 의 값은 알 수 없습니다. 컴퓨터, 사용한 언어, 소스 프로그램을 실행 가능한 코드로 바꾸는 컴파일러나 인터프리터 같은 것들에 영향을 받기 때문입니다.
이 코드에는 guess를 0으로 초기화하고, 필요할 때 -1을 반환하는 것처럼, for 문을 만드는 데에도 추가적으로 시간이 필요합니다. 이 추가적인 시간을 c2 c_2 라고 하겠습니다. 이 또한 상수입니다. 따라서 최악의 경우 선형 검색에 걸리는 시간은 c1n+c2 c_1 \cdot n + c_2 입니다.
이제까지 설명했듯이 상수 인자인 c1 c_1 c2 c_2 을 안다고 해서 실행 시간이 커지는 비율을 알 수는 없습니다. 중요한 것은 선형 검색의 최악의 경우의 실행 시간은 배열 크기인 n n 에 따라 커진다는 것입니다. 여기서 실행시간을 표시하기 위해 사용하는 표기법은 Θ(n) \Theta(n) 입니다. 이는 그리스어인 "세타"로 "n n 의 빅 세타 " 또는 그냥 "n n 의 세타"라고 읽습니다.
특정 실행 시간이 Θ(n) \Theta(n) 이라고 하는 것은 n n 이 충분히 크다면 실행 시간이 어떤 상수 k1 k_1 k2 k_2 에 대하여 최소 k1n k_1 \cdot n 이며 최대 k2n k_2 \cdot n 이 된다는 뜻입니다. 아래 그림을 보면 Θ(n) \Theta(n) 에 대해 이해할 수 있습니다.
n n 의 작은 값에 대해서는 k1n k_1 \cdot n k2n k_2 \cdot n 의 실행 시간을 어떻게 다른지는 고려하지 않습니다. 그렇지만 n n 값이 충분히 커지면 점선에서 오른쪽 실행 시간은 반드시 k1n k_1 \cdot n k2n k_2 \cdot n 사이에 있게 됩니다. k1 k_1 k2 k_2 라는 상수가 있다면 실행 시간은 Θ(n) \Theta(n) 라고 할 수 있습니다.
big-Θ 표기법이 단지 n n 에만 제한되지는 않습니다. n2 n^2 이나 nlog2n n \log_2 n 같이 n n 에 관한 어떤 함수에서나 이를 이용할 수 있습니다. 아래 그림을 보면 어떤 함수 f(n) f(n) 에 대하여 실행 시간이 Θ(f(n)) \Theta(f(n)) 이라는 의미가 무엇인지 알 수 있습니다:
n n 값이 충분히 커지면 실행 시간은 k1f(n) k_1 \cdot f(n) k2f(n) k_2 \cdot f(n) 사이에 있게 됩니다.
보통 상수 인자와 낮은 차원의 항목은 생략하고 사용합니다. big-Θ 표기법을 사용하는 또다른 이점은 시간 단위를 고려할 필요가 없다는 것입니다. 예를 들어 실행시간이 6n2+100n+300 6n^2 + 100n + 300 μs라고 가정해 봅시다. 아니면 ms일 수도 있을겁니다. big-Θ 표기법에서는 이를 언급하지 않습니다. 또한 계수인 6과 저차원 항목인 100n+300 100n + 300 을 생략하고 그냥 실행 시간이 Θ(n2) \Theta(n^2) 라고 할 수 있습니다.
big-Θ표기법을 사용하는 것은 실행 시간에 대해 점근적으로 근접한 한계값이 있다고 표현하는 것입니다. "점근적으로"라는 말을 쓰는 이유는 큰 값의 n n 에 대해서만 적용되기 때문입니다. "근접한 한계값"이라는 말은 위, 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 뜻입니다.

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