[자료구조] 복잡도

빅오 표기법

* 두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다.

(간단하게 생각하는 법)
1. 상수항 무시
2. 영향력 없는 항 무시 - 가장 큰 차수 이외의 것들은 무시한다.

 

빅오메가 표기법 / 빅세타 표기법

* 두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n<n0에 대하여 |f(n)|>=c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=Ω(g(n))이다.

* 두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 c|g(n)| <=|f(n)|을 만족하는 3개의 상수 c1, c2와 n0가 존재하면 f(n)=Ω(g(n))이다.

빅오 표기법을 사용하는 이유

• 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다.
• 알고리즘의 실행 시간이 얼마나 걸리는지만 고려할 것이 아니라, 리스트의 크기가 증가할 때 어떻게 증가하는지 파악할 필요가 있다

	단순 탐색(n) / 100	이진 탐색(log2 n)
100	100ms	7ms
10,000	10s	14ms
1,000,000,000	11d	32ms

• 크기가 증가함에 따라 걸리는 시간의 격차가 더욱 커져감을 알 수 있다.

 

시간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미

 

공간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미

빅오 표기법	명칭
O(1)	상수시간
O(logN)	로그시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간