Algorithm Analysis 1 (Big-θ, Big-O, Big-Ω Notation)

우리는 알고리즘의 성능을 분석하기 위해 해당 알고리즘의 수행시간을 구하여 직접 비교할 수 있다. 하지만 알고리즘의 정확한 수행시간은 보통 알아내기 힘들뿐더러, 설사 알아낼 수 있다고 하더라도 일반적으로 굳이 시간을 계산할 수고를 할 필요가 없다. 그 이유는 입력이 충분히 커진다면 특정 수행시간에서 상수 계수와 상대적인 저차항은 입력의 크기에 묻혀버리기 때문이다. 그럼 우리가 알고리즘의 성능을 분석하기 위해 사용할 수 있는 개념에는 어떤 것이 있을까?

---

점근적 표기법 (Asymptotic notation)

 

일반적으로 알고리즘의 수행시간을 나타낸다고 할 때는 입력의 크기가 매우 큰 경우에 대해 알아보려는 것이다. 즉, 점근적 표기란 입력의 크기가 \(n\)일 때, \(n\rightarrow\infty\)인 경우 수행시간을 간단하게 나타내기 위한 표기를 말한다. 대표적으로 Big-\(\Theta\) 표기법, Big-\(O\) 표기법, Big-\(\Omega\) 표기법 등이 있다.

---

Big-\(\Theta\) Notation

"빅-세타 표기"라고 읽는 이 표기법은 알고리즘의 최선의 경우와 최악의 경우의 중간 정도의 상황을 고려한 표기이다.

 

- 정의: \(\Theta(g(n)) = \{ f(n)\): 모든 \(n\geq n_{0}\)에 대해 \(0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n)\)인 양의 상수 \(c_{1}, c_{2}, n_{0}\) 가 존재한다.}

 

이러한 정의를 이해하기 쉽게 아래의 그래프와 같이 나타낼 수 있는데,

이때 g(n)을 f(n)에 대한 asymptotically tight bound라고 한다.

---

Big-\(O\) Notation

"빅-오 표기"라고 읽는 이 표기법은 알고리즘의 최악의 경우를 고려한 표기이다. 점근적 상한과 점근적 하한 중에서 점근적 상한만을 알고 있다면 빅-세타 표기법 대신 빅-오 표기법을 사용하면 된다.

 

- 정의: \(O(g(n)) = \{ f(n)\): 모든 \(n\geq n_{0}\)에 대해 \(0\leq f(n)\leq cg(n)\)인 양의 상수 \(c, n_{0}\) 가 존재한다.}

이때 g(n)을 f(n)에 대한 asymptotically upper bound라고 한다.

---

Big-\(\Omega\) Notation

"빅-오메가 표기"라고 읽는 이 표기법은 알고리즘의 최선의 경우를 고려한 표기이다. 하지만 일반적으로 어떤 알고리즘을 실행할 때 최선의 경우는 잘 일어나지 않을 뿐더러, 최선의 경우를 기준으로 알고리즘을 짠다면 이외의 경우일 때 수행시간이 얼마나 증가할지 모르기 때문에 실질적으로 거의 사용하지 않는 표기법이다.

 

- 정의: \(\Omega(g(n)) = \{ f(n)\): 모든 \(n\geq n_{0}\)에 대해 \(0 \leq cg(n) \leq f(n)\)인 양의 상수 \(c, n_{0}\) 가 존재한다.}

이때 g(n)을 f(n)에 대한 asymptotically lower bound라고 한다.

---

지금까지 알아본 표기법들의 성질을 토대로 아래와 같은 정리 1을 유도할 수 있다.

 

정리 1) 임의의 두 함수 \(f(n)\)과 \(g(n)\)에 대해  \(f(n)=\Theta(g(n))\)이면, \(f(n)=O(g(n)), f(n)=\Omega(g(n))\)이고 그 역도 성립한다.

 

이 정리는 주로 임의의 알고리즘의 점근적 상한과 점근적 하한을 알고 있을 때, 점근적으로 정확한 한계를 증명하는 데에 사용한다.

 

 

다음글에서는 \(o\) notation과 \(\omega\) notation, 그리고 5가지 표기법들에 대한 성질들을 알아보도록 하겠다.

ps. 글에 추가하면 좋을만한 내용 혹은 잘못된 내용이 있다면 댓글로 자유롭게 남겨주세요 ㅎㅎ