Algorithm - [Asymptotic notation]

Asymptotic notation

알고리즘의 수행 시간을 표기하기 위해, 필수적인 부분에 집중하고 불필요한 상세들을 무시한다. 예를 들어, f(n) = n^2 + 2n 일 때, 시간 복잡도는 n^2이라고 한다. n이 무한대로 가는 데에선 낮은 차수의 증가폭이 높은 차수의 증가폭을 넘지 못하기 때문이다.

 

점근법 표기법

 

상한 표기법 : Big- O

점근적 상한만 알고 있을 때 사용하며 기껏해야 f(n)의 비율로 증가하는 함수

 

e.g. 7n-2가 O(n)임을 증명하라.

sol)

Let. c>0 이고 n_0 >= 1

n <= n_0에 대해 Cn >= 7n-2를 만족하는 c, n_0가 존재하는가?

​-> c=7,n_0 = 1일때 존재한다.

​

하한 표기법 : Big - Omega

점근적 하한만 알고 있을 때 사용하며 적어도 f(n)의 비율로 증가하는 함수

- O(f(n))과 대칭관계

e.g.

 

상한과 하한 표기법 : Big - Theta

상한과 하한을 둘 다 알고 있을 때의 표기법이며(상한 표기법, 하한 표기법의 교집합) g는 f같은 정도로 증가한다는 것을 직관적으로 이해

 

 

---

일반적인 표기 기준

1. O(1)

상수, 입력값의 크기 무관

사칙연산, if문, 일정범위 계산, 링크드리스트에서 삭제(time과 관련)

​

2. O(logn)

반복문, 입력값의 일부분을 버림(half)

e.g., 이진 검색

​

3. O(n)

선형, 입력값에 각 요소들에 대한 작업.

링크드리스트에서 검색, 배열 내 최대값 원소.

​

4. O(nlogn)

비선형, 분할과 정복 알고리즘

e.g., 병합정렬

​

5. O(n^2)

이중 반복문

e.g., 삽입정렬, 선택정렬, 버블정렬

​

6. O(2^n)

차수승, 모든 부분집합 검색

​

7. O(n!)

모든 순열 검색

​​

저장/검색의 복잡도

Binary search tree

- worst : Theta(n)

- 평균 : Theta(log n)

balenced binary search tree(ex. rb tree)

- worst : Theta(log n)

b-tree

- worst : Theta(log n)

hash table

- O(1)