[Section 1] 알고리즘의 분석 _ 세타 표기법

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

상한, 하한, 최고 상태, 최악 상태의 관계를 명확히 이해하기 위해서는 세타 표기법에 대해 알아야 한다. 평균 런타임을 의미하는 세타 표기법을 알아보고, 알고리즘의 분석 메커니즘을 파악하자.

1. 세타 표기법의 정의

세타 표기법의 수학적 정의는 다음과 같다.

 

"Θ(f(n)) = {g(n): 양의 정수 c₁, c₂와 n₀가 존재하여,

0 ≤ c₁f(n) ≤ g(n) ≤ c₂f(n) 을 만족하는 경우에 대해서 모든 n은 n₀ 보다 크거나 같다}"

 

빅-오메가 표기법과 빅-오 표기법의 정의를 알고 있다면, 위의 c₁과 c₂ 가 무엇을 의미하는지 눈치챌 수 있을 것이다. 세타 표기법의 의의는 수학적으로 평균값의 정리와 아주 밀접한 특징을 가지고 있다. 예를 들어, 다음의 함수 g(n)을 알고리즘 함수라고 가정해 보자. 

 

"g(n) = 2n²+3n+1" 

 

g(n)을 빅-오 표기법과 빅-오메가 표기법으로 나타내면 다음과 같다.

 

"O(n²))=cn²) _ c=3, n₀ =4"

 

"Ω(n²))=cn²) _ c=2,n₀ =1"

하한과 상한 예시

 

그리고 세타 표기법은 다음과 같이 나타낸다. 

 

" Θ(n²) = g(n) _ c₁=2 , c₂=3, n₀=1"

 

2. 세타 표기법의 의미 _ 평균 런타임(Average runtime)

프로그램의 최고 상태와 최악의 상태를 판가름하는 것은 개발자의 마음이나, 통상적으로 빅-오와 빅-오메가 표기법을 이용하여 상한 과 하한으로 그 상태를 판가름한다. 그리고 그 사이에 존재하는 평균적인 함숫값을 세타 표기법으로 나타내고 알고리즘을 분석할 수 있는 것이다. 따라서 세타 표기법은 어떤 알고리즘의 평균적 런타임을 의미하게 된다. 

 

* 결과적으로 Θ(f(n))은 상한, 하한, 그리고 그 평균 함수를 모두 포괄하고 있다. 이러한 이유로 하한에 대해서는 굳이 알 필요가 없지만, 단계적으로 이해하는데 큰 도움을 줄 것이다.