위키득계정 ↗
기술

세타 표기법

세타 표기법기술
영문명
Theta notation
기호
Θ(g(n))
주요 의미
점근적으로 꼭 맞는 경계
필요 경계
양의 상수배에 의한 위와 아래
세타 표기법 Θ(g(n))은 함수가 충분히 큰 입력에서 g(n)의 양의 상수배 사이에 놓인다는 뜻이다. 점근적 상한과 하한을 함께 주므로 증가율을 같은 차수로 묶는다.

두 부등식

음이 아닌 함수 f에 대해 양의 상수 c₁, c₂와 기준 n₀가 있어서 n≥n₀이면 c₁g(n)≤f(n)≤c₂g(n)이 성립할 때 f(n)=Θ(g(n))이다. 상수들은 n에 따라 바뀌지 않아야 한다.

이차 함수의 예

n≥1에서 3n²≤3n²+7≤10n²이므로 3n²+7은 Θ(n²)이다. 실제 함수값이 n²과 같다는 뜻은 아니며 상수배 차이를 허용한 증가율이 같다는 뜻이다.

빅오와의 차이

3n²+7은 O(n³)이라고도 쓸 수 있지만 Θ(n³)은 아니다. 충분히 큰 n에서 어떤 양의 상수배 n³보다도 작아지므로 그 차수의 하한을 유지할 수 없기 때문이다. 빅오의 상한 하나보다 세타의 조건이 강하다.

분석하는 비용의 종류

한 알고리즘의 최선 비용이 Θ(1)이고 최악 비용이 Θ(n)일 수 있다. 두 표현은 모순이 아니라 서로 다른 비용 함수를 설명한다. 세타 표기만으로 평균이나 최악 중 무엇을 뜻하는지 자동으로 결정되지는 않는다.

관련 문서

빅오 표기법 / 시간 복잡도 / 공간 복잡도 / 함수 / 다항함수 / 선형 탐색 / 알고리즘