시간 복잡도와 공간 복잡도

출처 : 이것이 코딩 테스트다 도서 Chapter 01

 

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

 

시간 복잡도

빅오 표기법을 사용 

* 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법

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

 

	N이 1,000일 때의 연산 횟수
O($N$)	1,000
O($NlongN$)	10,000
O($N^2$)	1,000,000
O($N^3$)	1,000,000,000

 

시간 제한이 1초인 문제에 대한 예시

N의 범위가 아래와 같을 때 시간 복잡도를 아래와 같이 설계하면 문제를 풀 수 있다.

N의 범위	시간 복잡도
500	O($N^3$)
2,000	O($N^2$)
100,000	O($NlongN$)
10,000,000	O($N$)

 

---

공간 복잡도

빅오 표기법을 사용 

* 자료형 int 배열의 예시 (int 크기 : 4바이트)

int a[1000]	4KB
int a[1000000]	4MB
int a[2000][2000]	16MB

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다.

👉 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야한다.

 

 

---

시간 측정

수행 시간 측정 소스 코드

long beforeTime = System.currentTimeMillis(); //측정 시작
        
// 프로그램 소스 코드
        
long afterTime = System.currentTimeMillis(); // 측정 종료
System.out.println("time(m) : "+(afterTime - beforeTime)/1000); // 수행 시간 출력

 

---

덧붙임

덧붙임 출처 블로그

• 1초에 연산 횟수가 1억이라고 생각한다.
• 메모리 사용량 = 배열의 크기 * 해당 자료형의 크기
  로 생각하며, 지역 변수, 함수 등을 생각해서 5~10MB정도는 여유로 빼고 생각한다.