Big-θ (빅 세타) 표기법
ko.khanacademy.org
*이 글은 위 링크의 글을 개인 공부를 목적으로 필사하거나 요약한 글입니다.
선형 탐색 예제를 통한 빅 세타의 이해
var doLinearSearch = function(array, targetValue) {
for (var guess = 0; guess < array.length; guess++) {
if (array[guess] === targetValue) {
return guess; // 찾은 경우
}
}
return -1; // 찾지 못한 경우
};*예제코드는 자바스크립트
우선 배열의 크기(array.length)를 n이라고 합니다. for문은 최대 n번 반복됩니다. 최대 n번 반복되는 최악의 경우는 배열에 찾는 값이 존재하지 않을 때 발생합니다
for문이 수행될 때마다 아래가 실행돼야 합니다.
- guess와 array.length를 비교합니다. (guess < array.length;)
- array [guess]와 targetValue를 비교합니다. (array [guess] == targetValue)
- 가능하다면 guess의 값을 반환합니다. (return guess)
- guess를 증가시킵니다. (guess++)
각각의 계산은 실행하는 데에 어떤 상수만큼의 시간이 걸립니다. for 문을 n번 반복하면 총계산에 걸리는 시간은 c1*n입니다. c1은 반복 한 번에 걸리는 시간을 나타냅니다. 여기서 c1의 값은 알 수 없습니다. c1은 컴퓨터, 사용한 언어, 컴파일러, 인터프리터 같은 것들에 영향을 받기 때문입니다.
예제 코드에서 guess를 0으로 초기화하고, 필요할 때 -1을 반환하는 것처럼, for문을 만드는 데도 추가적인 시간이 필요합니다. 이 추가적인 시간을 c2라고 하겠습니다. c2도 c1과 마찬가지로 상수입니다. 따라서 위 선형 검색 예제 코드에서 최악의 경우 선형 검색에 걸리는 시간은 c1*n+c2라고 표현할 수 있습니다.
이전 글에서 설명했듯 상수 인자인 c1과 c2의 정확한 값을 안다고 해서 실행 시간이 커지는 비율을 알 수는 없습니다. 중요한 것은 선형 검색의 최악의 경우, 실행 시간은 배열 크기인 n에 따라 커진다는 것입니다. 여기서 실행시간을 표시하기 위해 사용하는 표기법이 세타(n)입니다. 이는 그리스어로 "세타", "n의 빅 세타" 또는 그냥 "n의 세타" 라고 읽습니다.
만약 특정 실행 시간이 세타(n)이라면 이는 n이 충분히 크다면 실행시간이 상수 k1과 k2에 대하여 최소 k1*n이며 최대 k2*n이라는 뜻입니다. 아래 그림을 참고하세요.
그리고 차트를 살펴보면 n이 작은 값일 경우에 k1*n과 k2*n의 실행 시간이 어떻게 다른지는 고려하지 않습니다. 하지만 n값이 충분히 커진다면 실행 시간은 반드시 k1*n과 k2*n의 사이에 있게 됩니다. 만약 k1과 k2라는 상수가 있다면 실행 시간은 세타(n)라고 할 수 있습니다.
big-세타 표기법은 단지 n의 경우로 제한되지 않습니다. n제곱, n log2 n같이 n에 관한 어떤 함수에서나 이를 이용할 수 있습니다. 아래그림을 보면 함수f(n)에 대해 실행시간이 세타(f(n))이 무슨 의미인지 알 수 있습니다.
위 그림도 마찬가지입니다. n값이 충분히 커지기 시작하면 실행시간은 k1*f(n)과 k2*f(n)사이에 있게 됩니다.
빅세타 표기법의 사용
보통 상수 인자와 낮은 차원의 항목은 생략하고 사용합니다. 빅세타 표기법을 사용하는 또 다른 이점은 시간 단위를 고려할 필요가 없다는 것입니다. 예를 들어 실행시간이 6n2 + 100n + 300us라고 가정해봅니다. 빅세타에서는 이를 언급하지 않습니다. 제인 고차원항목은 n2의 계수 6을 생략하고, 나머지 저차원 항목인 100n + 300us도 생략합니다. 그냥 실행 시간이 세타(n제곱)이라고 할 수 있습니다.
빅세타 표기법을 사용할 때
이 표기법은 실행 시간에 대해 점근적으로 근접한 한계값이 있다고 표현합니다.
"점근적으로"라는 말을 쓰는 이유는 큰 값의 n에 대해서만 적용되기 때문입니다. "근접한 한계값"이라는 말은 위 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 의미입니다.
이상 빅세타 표기법에 대한 내용을 마칩니다.