Lecture3 - 알고리즘 설계와 분석의 기초(2)

---

Big O relation

d>c>1인 경우

 

b>1,  c,d>0인 경우

 

b>1, d>0인 경우

 

c>b>1인 경우

---

합성 함수에서의 Big O relation

---

Big Omega notation

Ω(g(n))과 같이 표기하고 적어도 g(n)의 비율로 증가하는 함수라는 뜻으로 O(g(n))과 대칭적이라고 볼 수 있다.

Formal definition은 Ω(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0 , cg(n)≤f(n) }과 같은 방식으로 정의된다.

직관적으로 생각해보면 "f(n) = Ω(g(n)) ⇒ f는 g보다 느리게 증가하지 않는다"라고 생각할 수 있다.

---

Big Theta notation

Θ(g(n))과 같이 표기하고 정확히 g(n)의 비율로 증가하는 함수를 뜻한다.

Formal definition은 Θ(g(n)) = O(g(n)) ∩ Ω(g(n))과 같은 방식으로 정의된다.

다시말해 Big O와 Big Omega가 동시에 성립하는 부분이다.

직관적으로 바라보면 "f(n) = Θ(g(n)) ⇒ f는 g와 같은 정도로 증가한다"고 볼 수 있다.

---

little o와 omega까지 종합하여 간단하게 정리해보면 다음과 같다.

• O( g(n) ) – Tight or loose upper bound

• Ω( g(n) ) – Tight or loose lower bound

• Θ( g(n) ) – Tight bound

• o( g(n) ) – Loose upper bound

• 𝜔( g(n) ) – Loose lower bound

---

시간 복잡도 분석의 종류

시간 복잡도란 알고리즘이 입력 크기에 따라 실행되는 시간을 분석하는 방법이다.

시간 복잡도는 최악의 경우, 평균적인 경우, 그리고 최선의 경우에 따라 나누어 진다.

1. 최악의 경우 (worst-case) 최악의 경우 시간 복잡도는 입력값이 가장 크고 알고리즘이 가장 많은 시간을 소비하는 경우이다. 예를 들어, 정렬 알고리즘에서 최악의 경우는 역순으로 정렬된 배열이 입력으로 주어졌을 때이다. 이 경우, 선택 정렬 알고리즘은 O(n^2)의 시간 복잡도를 가지며, 병합 정렬 알고리즘은 O(nlogn)의 시간 복잡도를 가진다.
2. 평균적인 경우 (average-case) 평균적인 경우 시간 복잡도는 입력값이 무작위로 주어졌을 때 알고리즘이 소비하는 시간이다. 예를 들어, 동일한 크기의 무작위 배열을 정렬하는 경우, 병합 정렬 알고리즘은 평균적으로 O(nlogn)의 시간 복잡도를 가진다.
3. 최선의 경우 (best-case) 최선의 경우 시간 복잡도는 입력값이 가장 작고 알고리즘이 가장 적은 시간을 소비하는 경우이다. 예를 들어, 선택 정렬 알고리즘에서 최선의 경우는 이미 정렬된 배열이 입력으로 주어졌을 때이다. 이 경우, 선택 정렬 알고리즘은 O(n^2)의 시간 복잡도를 가지지만, 병합 정렬 알고리즘은 최선의 경우에도 O(nlogn)의 시간 복잡도를 가진다.

따라서, 최악의 경우 시간 복잡도는 알고리즘의 성능을 가장 강조하며, 평균적인 경우는 입력값이 무작위로 주어졌을 때 알고리즘이 소비하는 시간을 고려하며, 최선의 경우는 입력값이 이미 정렬되어 있거나, 가장 작을 때 알고리즘이 소비하는 시간을 고려한다. 이러한 시간 복잡도 분석은 각각의 상황에 따라 이용되어 알고리즘을 설계하고 최적화하는 데 중요한 역할을 한다.

---