복잡도(Complexity): 알고리즘의 성능을 나타내는 척도

1. 시간 복잡도

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

• 알고리즘을 위해 필요한 연산의 횟수
• 시간 복잡도를 표현 할 때는 빅오(Big-O) 표기법 사용

1.1. Big-O 표기법

• 가장 빠르게 증가하는 항만을 고려 (함수의 상한만을 나타냄)
• 시간 복잡도에서의 '연산'은 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

빅오 표기법	N이 1,000일 때의 연산 횟수
O(N)	1,000
O(NlogN)	10,000
O(N²)	1,000,000
O(N³)	1,000,000,000

 

2. 공간 복잡도

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

• 알고리즘을 위해 필요한 메모리의 양

/* 자료형 int 기준 */
int a[1000] //4KB
int b[1000000] //4MB
int c[2000][2000] //16MB