[알고리즘] 시간 복잡도의 점근적 표기 이해(Big-O,Big-Omega,Big-Theta)

대표적인 점근적 표기

---

대표적인 점근적 표기

대표적인 점근적 표기는 위와 같다. 사실, 말로는 이해하기 너무 어렵다. 점근적 표기에 대해서 더 알아보자.

O(Big-O)-표기 (최악의 시간 복잡도)

---

O(Big-O)-표기

- O(Big-O) 표기의 정의

    모든 n >= n0에 대해서 cg(n) >= f(n)인 양의 상수 n0와 c가 존재한다면, f(n) = O(g(n))이다.

 

- O(Big-O) 표기의 의미

    n0와 같거나 큰 모든 n에 대해서 f(n)은 cg(n)보다 크지 않다는 의미이다.

   즉, f(n)은 cg(n)에 절대 미치지 못하며, 이때 g(n)을 f(n)의 상한이라고 한다.

 

- f(n) = O(g(n))의 의미

   n이 증가함에 따라 g(n)은 f(n)이 절대 미치지 못하는 점근적 상한이다.

 

- Big-O 표기법을 찾는 방법

   다항식에서 계수를 제거한 최고 차수 항만 남기면 g(n)이다.

O(Big-Omega)-표기 (최선의 시간 복잡도)

---

Ω (Big-Omega)-표기

- Ω (Big-Omega) 표기의 정의

    모든 n >= n0에 대해서 f(n) >= cg(n)이 성립하는 양의 상수 n0와 c가 존재한다면, f(n) = Ω(g(n))이다.

 

- Ω (Big-Omega)  표기의 의미

    n0와 같거나 큰 모든 n에 대해서 f(n)은 cg(n)보다 작지 않다는 의미이다.

   즉, cg(n)은 f(n)에 절대 미치지 못하며, 이때 g(n)을 f(n)의 하한이라고 한다.

 

- f(n) = Ω(g(n))의 의미

   n이 증가함에 따라 g(n)은 f(n)에 절대 미치지 못하는 점근적 하한이다.

 

Θ(Big-Theta)-표기 (평균의 시간 복잡도)

---

Θ(Big-Theta)-표기

- Θ(Big-Theta) 표기의 정의

    모든 n >= n0에 대해서  c1g(n) <= f(n) <= c2g(n)이 성립하는 양의 상수 n0와 c1, c2가 존재한다면, f(n) = Θ(g(n))이다.

 

- Θ(Big-Theta) 표기의 의미

    Big-O 표기와 Big-Omega가의 표기가 같을 때 사용한다. 즉, Big-theta는 동일한 증가율을 의미한다. 예를 들자면, 다음과 같다.

   

Big-theta의 의미

- f(n) = Θ(g(n))의 의미

   n0보다 큰 모든 n에 대해서 f(n)은 g(n)의 하한과 상한을 동시에 만족한다.

 

시간 복잡도 분류 관점에서 점근적 표기 바라보기

---

1. 최악의 경우 시간 복잡도 = Big-O
2. 최선의 경우 시간 복잡도 = Big-Omega
3. 평균의 경우 시간 복잡도 = Big-Theta

ans = []
n = int(input())
for i in range(1,n):
    for j in range(1,n):
        ans.append(i*j)

for i in range(n):
    print(ans[i], end=' ')

다음 코드를 점근적으로 분석해서 복잡도 함수 f(n)을 도출하면, f(n) = n^2 + n 이다. 즉, 입력 크기가 충분히 클 때 복잡도 함수가 f(n) = n^2 + n 이라는 말이다. 이제는 이 복잡도 함수 f(n)을 점근적 표기를 이용해 최악, 최선, 평균의 경우로 시간 복잡도로 나타내자.

 

1. f(n)의 상한인 g(n)은 f(n)보다 항상 복잡도가 더 크기에 g(n)은 최악의 경우 시간 복잡도, 즉, O(g(n)) 이다.

2. f(n)의 하한인 g(n)은 f(n)보다 항상 복잡도가 더 작기에 g(n)은 최선의 경우 시간 복잡도, 즉, Ω(g(n)) 이다.

3. f(n)의 상한, 하한 만족하는 g(n)은 f(n)과 유사한 증가율을 가지고 있기에 평균의 시간 복잡도, 즉, Θ(g(n)) 이다.