[알고리즘] CHAP 0. Time Complexity - Order Function ( O(n), Ω(n), θ(n) )

2학기가 끝난 기념(?)으로 가장 중요한 과목이었던 알고리즘을 정리해보려고 한다. 더 미뤄서 머리에서 사라지기 전에..!

자료구조랑 겹치는 부분은 최대한 배제하겠지만 어느정도의 교집합은 어쩔 수 없는 거 같다. 그럼 시작-!

 

이번 챕터에서는 첫 주에 배웠던 order function을 정리해 볼 예정이다.

 

---

1. order function의 종류

우리는 알고리즘의 time complexity, 즉 시간복잡도를 함수를 이용해 표현한다. 사용하는 함수는 크게 7가지이다.

•  lg n
•  n (linear)
•  n lg n
•  n^2 (quadratic)
•  n^3 (cubic)
•  2^n (exponential)
•  n! (combinatorial)

세로선을 그었을 때 그래프와의 교점이 아래에 있을수록 시간이 짧게 걸리는 함수라고 할 수 있다. 

growth rates of Complexity Functions

 

인수가 작을 때에는 별 차이가 없을 수 있지만, 인수의 크기가 커질수록 러닝타임의 차이는 기하급수적으로 커진다. 그렇기에 우리는 최대한 좋은 성능을 낼 수 있는 함수가 나오게 알고리즘을 설계해야 한다.

 

---

2. 시간 복잡도의 표현

자료구조론에서는 Big-O만을 다루었지만, 이번 알고리즘 수업에서는 다양한 표현을 다루었다. 한개한개 확인 해보자.

 

2-1. Big O (Asymptotic Upper Bound)

이 표현은 최악의 상황을 가정할 때 쓰는 표현이고, 함수로 나타내면 g(n) <= c f(n) 으로 쓴다.

이는 음수가 아닌 n이 존재하고,  양수인 c가 존재할 때, 이에 대해 f(n)은 한 번 g(n)보다 커지면, g(n)의 영원한 upper bound(상한선) 역할을 하게 됨을 이른다. 즉 f(n)은 g(n)에 대한 최악의 경우라고 할 수 있고, 쉽게 말하면 g(n)은 적어도 f(n)보다 좋은 알고리즘이라는 뜻이다.

예시를 들면 아래처럼 쓸 수 있다.

 

Ex1) 성립하는 경우 - n^2 + 10n ∈ O(n^2)

이는 n^2+ 10n <= c n^2을 보이면 되는데, c = 11, N = 1 일 때 가능하므로 성립한다. 즉,  n^2 + 10n은 적어도 n^2보다 빠른 러닝타임을 갖는다.

 

Ex2) 성립하는 경우 - n ∈ O(n^2)

이는 n <= c n^2을 보이면 되는데, 단순하게 c = 1, N = 1 일 때 가능하므로 성립한다. 

 

Ex3) 성립하지 않는 경우 - n^3 ∈ O(n^2)

이는 n^3 <= c n^2을 보이면 되는데, 양변을 n^2으로 나누면 n <= c가 된다. 하지만 이때는 충분히 큰 '변수'인 n보다 큰 상수 c가 존재할 수 없기 때문에 이는 성립하지 않는다.

 

O(n^2)에 포함되는 함수들

 

2-2. Ω (Asymptotic Lower Bound)

이 표현은 O와 반대로 최선의 경우를 나타내는 표현법이고, 함수로 나타내면 g(n) >= c f(n) 으로 쓴다.

이는 음수가 아닌 n이 존재하고,  양수인 c가 존재할 때, 이에 대해 f(n)은 한 번 g(n)보다 작아지면, g(n)의 영원한 lower bound(하한선) 역할을 하게 됨을 이른다. 즉 f(n)은 g(n)에 대한 최선의 경우라고 할 수 있고, 쉽게 말하면 g(n)은 아무리 빨라도 f(n)보다 빠를 수 없는 알고리즘이라는 뜻이다.

예를 들어보자

 

Ex1) 성립하는 경우 - n^2 + 10n ∈ Ω(n^2)

이는 n^2+ 10n >= c n^2을 보이면 되는데, c = 1, N = 0 일 때 가능하므로 성립한다. 

 

Ex2) 성립하는 경우 - n^3 ∈ Ω(n^2)

이는 n^3 >= c n^2을 보이면 되는데, c = 1이 되면 n^3 >= n^2이므로 성립한다. 

 

Ex3) 성립하지 않는 경우 - n ∈ Ω(n^2)

이는 n >= c n^2을 보이면 되는데, 양변을 cn으로 나누면 1/c >= n이 된다. 하지만 n은 충분히 큰 양수인 '변수'이고, c는 0이 아닌 정수이기 때문에 이는 성립하지 않는다.

Ω(n^2)에 포함되는 함수들

 

 

2-3. θ (Asymptotic Tight Bound)

이 표현은 위 두가지 표현보다 좀 더 타이트한 표현으로 쉽게 이야기하면 둘의 교집합이라고 할 수 있다. 함수로 나타내면  c f(n) <= g(n) <= d f(n) 으로 쓴다.

이는 음수가 아닌n이 존재하고,  양수인 c,d가 존재할 때 성립한다.

예를 들어보면

 

Ex) 성립하는 경우 - 5n^2 ∈ Ω(n^2)

이는 c n^2 <= 5n^2 <= d n^2을 보이면 되는데, c = 4, d = 6일 때 가능하므로 성립한다. 

 

사실 Ω(n^2) ∩ O(n^2) 만 기억하면 됨!

 

---

큼직한 정리는 여기까지! 수업에는 θ 를 많이 썼다. 다음시간부턴 본격적인 알고리즘 시작!