[CLRS] [3-1] 시간 복잡도 (big-O, big-Ω, big-θ)

1. Introduction

- 효율적인 알고리즘을 구현하기 위해 이 "효율"을 계산하기 위한 "시간 복잡도"에 대해서 알아보자

 

2. Big-O Notation 

- Big-O Notation은 함수의 상한을 나타낸다. 

- 즉 상한을 걸어두고, 그 함수는 상한에 걸어둔 Big-O Notation보다 특정 순간부터 증가하지 않음을 의미한다.(이 때 최고차항을 기준으로 나타낸다.)

- 예를들어 다음과 같은 함수가 있다고 생각해보자.

- f(x) = n^3 + 2n+1 --> O(n^3)이라고 나타낼 수 있다. 

- 하지만 O(n^4),O(n^5)로도 나타낼 수 있다. 그 이유는 f(x)는 n^4 , n^5보다 느리게 증가하기 때문이다.

- 따라서 c>=3 을 만족할 때 O(n^c)로 Big-O Notation으로 표현이 가능하다.

 

3. Big-Omega Notation

- Big-Omega Notation은 함수의 하한을 나타낸다.

- 즉, 하한을 걸어두고, 그 함수는 하한에 걸어둔 Big-Omega Notation 보다 특정 순간부터 감소하지 않음을 의미한다.

-  f(n) = n^3 + 2n+1  이 다음과 같을 때, Ω(n^3)으로 나타낼 수 있다.

- 뿐만 아니라 Ω(n^2), Ω(n) ... 등등 가능하다. 

- 따라서 c<=3을 만족하는 Ω(n^c)로 Big-Omega Notation으로 표현이 가능하다.

 

4. Big-Theta Notation

- Big-Theta Notation은 Big-Omega Notation과 Big-O Notation 을 둘 다 만족해야한다.

따라서 f(n) = n^3 + 2n+1  이 다음과 같을 때

- θ(n^3)이라고 할 수 있는 것이다.

 

5. Big O? 

- 실제론 Big-O Notation을 Big-Theta Notation으로 사용한다.

- 따라서 실제로 Big-O로 표기된 알고리즘의 시간복잡도는 결국 Big-Theta와 같다.

 

6. 최악의 경우와  big-O, Ω, θ의 관계

-  두 개념은 완전히 무관하니 참고하도록 하자. 

- 다시말해 O(n^2)일 때 n^2은 최악의 경우라고 할 수 없는 것이다.