Big-O (빅 오) 표기법
ko.khanacademy.org
*이 글은 위 링크의 내용을 필사하거나 요약한 글입니다.
빅 세타 표기법을 대체할 수 있는 빅 오 표기법
Big-Θ(빅 세타)표기법은 실행 시간에 대하여 위아래에 점근적으로 근접한 한계가 있습니다. 이와 다르게 한계를 위에만 둘 때도 있습니다.
예를 들어 보겠습니다. 이진 검색 실행 시간의 최악의 경우는 Θ(log2n)입니다. 하지만 이진 검색이 모든 경우에 Θ(log2n)일것이라 말할순 없습니다. 만약 찾고자 하는 값을 첫번째 추측만에 찾아버리면 이 경우에 실행 시간은 Θ(1)입니다. 이진 검색의 실행시간은 절대 Θ(log2n) 이상이진 않지만 이보다 더 좋은 경우도 있습니다.
"실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"라는 의미인 점근적 표기법 형태를 사용하는 것이 더 편리할수도 있습니다. 이런 경우를 위해 '빅 오' 표기법을 사용합니다.
실행 시간이 O(f(n))이라면 충분히 큰 값인 n와 상수 k에 대해 실행 시간은 최대 k*f(n)이 됩니다. 아래의 그래프를 참고하면 이해할 수 있습니다.
위 그래프의 실행시간은 "f(n)의 big-O" 혹은 그냥 "f(n)의 O"라고 표현하기도합니다. 점근적 상한선에 대해서는 big-O 표기법을 사용하는데 이는 충분히 큰 입력 크기에 대하여 실행 시간에 상한값을 두고 제한하기 때문입니다.
이진검색의 실행 시간에 대한 모든 표기법
지금까지 배운 '빅 세타'와 '빅 오'표기법을 통해 모든 경우의 이진 검색의 실행 시간을 알아낼 수 있습니다. 이진 검색의 실행 시간은 항상 O(log2n)라고 할 수 있습니다. 최악의 경우까지 포함시킨다면 Θ(log2n)라고 표현하면됩니다.
하지만 일반적으로 모든 경우를 포괄하는 표현으로 O(log2n)를 사용합니다. 빅 오 표기법이 가장 상세한 표현입니다.
빅 세타와 빅 오 표기법의 공통부분
빅세타의 정의를 다시 보면 실행 시간에서 상한과 하한 둘 다 존재하는 것을 제외하면 빅오 표기법과 매우 닮아있습니다. 만약 특정 함수의 실행 시간이 세타(f(n))이라면 이는 또한 O(f(n)로 표현할 수 있습니다.
하지만 반대의 경우는 항상 참이 아닙니다. 어떤 특정함수를 O(f(n))으로 표현할수있다고 해서 세타(f(n)이 참이 되는 건 아닙니다.