시간복잡도는 알고리즘의 시간효율성을 의미하고, 공간복잡도는 알고리즘의 공간효율성을 의미한다.
이때, 시간과 공간복잡도를 나타내는 방법중에 Landau Symbols를 이용한 점근 표기법인 빅오(Big-O) Notation, 빅오메가(big-Ω) Notation, 빅세타(big-Θ) Notation 등이 있다.
Big-Θ Notation 을 기준으로 Big-O, Big-Ω Notation을 알아보자.
* 참고 *
모든 Landau Notation 은 n이 무한히 클 때 정의하므로, 상수인자와 낮은차원의 항목은 생략하고 사용한다.
따라서, 표기할 때 최고차항이나 가장 높은 차원의 항만 남겨두고 사용하면 된다.
Big-Θ Notation
Big-Θ Notation 의 정의는 다음과 같다. 점근적 상한과 하한의 교집합 (Asymptotic tighter bound)으로 평균 범위의 개념으로 알고리즘이 아무리 좋거나 나쁜 상황이더라도 비교하는 함수 범위 안에 존재함을 표현한다.
만약 특정 실행시간이 Θ(g(n)) 이라면, 상수 C1 ,C2에 대해 최소 C1*g(n) 이며 최대 C2*g(n)이라는 것을 의미한다.
또한, n이 무한히 커졌을 때, f(n) 과 g(n)의 비율은 상수값으로 수렴하게되고, C>0 이기때문에 둘의 증가속도는 같다고 볼 수 있다.
n값이 충분히 큰 경우에 한 해 실행시간은 반드시 C1*g(n) 과 C2*g(n) 사이에 존재하는것을 확인할 수 있다.
위의 그림에서 n이 무한히 커진다면, 빨간그래프와 파란색 그래프는 하나의 직선의 형태로 보일것이다.
이는 n 이 무한히 큰 경우에,
f(n) = Θ(g(n)) 이면, f(n)과 g(n) 은 동등한 비율로 증가하고 둘의 시간 복잡도는 같음을 의미한다.
Big-O Notation
Big O Notation 은 점근적 상한선을 나타낸다.
이는 최악의 경우를 전제로 최대치에서 알고리즘과 비교한다.
아무리 알고리즘이 나빠도 비교함수와 같거나 좋음을 의미한다.
우선 수학적 정의를 살펴보자.
여기서, 양의 상수 C와 N 이 존재하면, Big-O Notation 표기법으로 쓸 수 있다.
또한, n이 무한히 커졌을 때, f(n) 과 g(n)의 비율은 상수값으로 수렴하게되고, C>=0 이기때문에 둘의 증가속도는 같거나 크다고 볼 수 있다.
둘의 증가속도가 같은 경우에 우리는 Big-Θ Notation 을 사용하기로 했다.
따라서, Big-Θ Notation은 Big-O Notation 에 포함되는 정의라고 말 할 수 있다.
Big-Θ Notation -> Big-O Notation
다음과 같이 f(n)과 g(n)을 예시로 BIg -O notation을 이해해보자.
인 경우로 예시를 들어보자. 예시의 다항식으로 정의를 써보면 f(n) <= k*g(n) 이 성립하는 k와 n0을 구할 수 있다.
따라서 f(n) = O(g(n)) 이라고 표기할 수 있다.
빅오 표기법 (big-O notation) 이란 :: 인생의 로그캣 (tistory.com)
이것은 f(n)의 running time이 최악인 경우에도, 점근상한선인 k*g(n)을 넘을수가 없다는것을 의미한다.
즉, 아무리 느려봤자 k*g(n)의 시간복잡도를 넘어설 수 없다는것을 의미한다.
Big-Ω notation
Big-Ω notation 은 Big-O notation 과 반대라고 생각하면 쉽다.
점근적 하한선을 나타내고 알고리즘이 아무리 좋은 상황이더라도 비교 함수보다는 같거나 좋지 않음을 표현한다.
이것은 f(n)의 running time이 최고인 경우에도, 점근하한선인 k*g(n)이하로 내려갈 수 없다는것을 의미한다.
즉, 아무리 빨라도 k*g(n)의 시간복잡도보다 빠를 순 없다는것을 의미한다.
다음의 사진을 보면 위에서 설명한것을을 비교하여 이해하기 쉽다.
본문에 small o 와 small omega 에 대해 언급하진 않았지만, 간략하게 설명하자면 small o 와 small omega는
각각 Big O 와 Big omega 에서 f(n) = g(n) 인 경우만 제외했다고 생각하면 된다.
빅 세타 : f = g
빅 오 : f <= g
빅 오메가 : f>=g
스몰 오: f<g
스몰 오메가 : f>g
'CS > 데이터구조' 카테고리의 다른 글
| Week1-2 Asymptotic Analysis_Linear and Binary Search (0) | 2022.09.14 |
|---|---|
| Week1-2 Asymptotic Analysis (0) | 2022.09.14 |