[알고리즘] Asymptotic Notation

(2021.10.06)

알고리즘 수업들으면서 정리하기 3탄

3주차 내용

 

 

---

Asymptotic Notation (점근적 표기)

 

알고리즘의 런타임을 표기하기 위해서 highest-order term으로 정의하는 것을 점근적 표기라고 한다.

점근적 표기에는 세가지가 있다.

• Big O: 상한선 제시 - upper bound
• Big Omega: 하한선 제시 - lower bound
• Big Theta: 상한선과 하한선 둘다 제시

(Big O는 Big theta로 표기가능하지만, Big theta는 Big O로 표기할 수 없음 - 교수님 왕강조)

 

 

 

Big O

--> 상한선 제시 : upper bound

 

출처: 교수님 강의노트

 

 

 

 

Big Omega

--> 하한선 제시 : lower bound

--> BEST case performance를 얘기할 때 주로 사용함.

 

출처: 교수님 강의노트

 

 

 

 

Big Theta

--> asymptotically tight bound

 

출처: 교수님 강의노트

 

 

 

그래서 앞에서 계산했던

insertion sort의 Best 런타임이 하한선이 되어 오메가(n)으로 표기하고,

insertion sort의 Worst 런타임이 상한선이 되어 O(n^2)으로 표기하는 것이었다!!

(사실 이거 안적어서 과제에서 점수 깎임)

 

 

 

 

 

과제로 했던 계산문제들 ↓↓↓↓↓↓↓

 

여기서 주의할 점: c는 양의 실수, n0는 0포함하여 자연수여야함

 

 

↓↓↓↓↓↓↓ 제일 어려웠던 문제 ↓↓↓↓↓↓↓