Big-Θ 표기법은 실행 시간에 대하여 위아래에 점근적으로 근접한 한계가 있습니다. 하지만 한계를 위에만 둘 때도 있습니다.
예를 들어 이진 검색 실행 시간 최악의 경우는 Θ(log2n) \Theta(\log_2 n) 이지만, 이진 검색이 모든 경우에 Θ(log2n) \Theta(\log_2 n) 이라고 할 수는 없습니다. 찾고자 하는 값을 첫 번째 추측에 찾으면 어떻게 될까요? 그러면 그 경우 실행 시간은 Θ(1) \Theta(1) 입니다. 이진 검색의 실행 시간은 절대 Θ(log2n) \Theta(\log_2 n) 이상이진 않지만 더 좋을 때도 있습니다.
"실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미인 점근적 표기법 형태를 사용하는 것이 편리할 수도 있습니다. 이런 경우를 위해 "big-O" 표기법을 사용합니다.
실행 시간이 O(f(n)) O(f(n)) 이라면 충분히 큰 값인 n n 와 상수 k k 에 대해 실행 시간은 최대 kf(n) k \cdot f(n) 가 됩니다. 실행 시간이 O(f(n)) O(f(n)) 인 경우에 대해 이렇게 생각할 수 있습니다:
여기서는 실행 시간이 "f(n) f(n) 의 big-O"거나, 그냥 "f(n) f(n) 의 O"라고 표현합니다. 점근적 상한선에 대해서는 big-O 표기법을 사용하는데 이는 충분히 큰 입력 크기에 대하여 실행 시간에 상한값을 두고 제한하기 때문입니다.
이제 모든 경우에 대해 이진 검색의 실행 시간을 알아낼 수 있는 방법이 생겼습니다. 이진 검색의 실행 시간은 항상 O(log2n) O(\log_2 n) 라고 할 수 있습니다. 최악의 경우의 실행 시간에 대해는 더욱 상세한 식을 만들 수도 있습니다. 바로 Θ(log2n) \Theta(\log_2 n) 이죠. 그렇지만 모든 경우를 포괄하는 일반적 표현으로는 이진 검색이 O(log2n) O(\log_2 n) 시간 내에 실행된다고 하는 것이 가장 상세한 표현입니다.
big-Θ의 정의를 다시 보면 실행 시간에서 상한과 하한 둘 다 존재한다는 것을 제외하고 big-O 표기법과 상당히 비슷하다는 것을 알 수 있을 것입니다. 특정 상황에서 실행 시간이 Θ(f(n)) \Theta(f(n)) 이라면, 이는 또한 O(f(n)) O(f(n)) 이기도 합니다. 예를 들어 이진 검색의 최악의 실행 시간은 Θ(log2n) \Theta(\log_2 n) 이기 때문에 O(log2n) O(\log_2 n) 이라고도 할 수 있습니다.
그 반대가 항상 참이 되지는 않습니다. 앞에서도 봤듯이, 이진 검색이 항상 O(log2n) O(\log_2 n) 시간 안에 실행된다고 할 수는 있지만, 항상 Θ(log2n) \Theta(\log_2 n) 시간에 실행되는 것은 아닙니다.
big-O 표기법이 점근적 상한선만 제공하고 점근적으로 근접한 한계를 주지 않기 때문에, 처음에는 틀린 것 같지만 따져보면 맞는 상황들이 있습니다. 예를 들면, 이진 검색의 실행 시간이 O(n) O(n) 이라고 하는 것은 옳습니다. 실행 시간이 n n 에 상수를 곱한 것보다 느리게 커지기는 하기 때문입니다.
이렇게 생각해 보세요. 10달러를 가지고 있는데, 친구에게 가서 "내 주머니에 돈이 있는데 확실히 100만 달러보다는 적게 있어" 라고 말한다면, 정확하다고는 할 수 없지만 명백한 사실이긴 합니다.
100만 달러가 10달러의 상한선인 것처럼, O(n) O(n) 도 이진 검색 실행 시간의 상한선입니다. 다른 정확하지 않은 상한선에는 O(n2) O(n^2) , O(n3) O(n^3) , O(2n) O(2^n) 등이 있을 수 있습니다. 하지만 Θ(n) \Theta(n) , Θ(n2) \Theta(n^2) , Θ(n3) \Theta(n^3) , Θ(2n) \Theta(2^n) 은 이진 검색의 어떤 경우도 정확히 묘사하지 않습니다.

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