[코테] 복잡도 - 시간복잡도, 공간복잡도, 프로그램 수행 시간 측정(파이썬)

0. 시간 복잡도와 공간 복잡도

- 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수

- 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

 

 

 

 

1. 시간복잡도

코딩테스트에서 시간복잡도는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미.

(메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 메모이제이션 기법 존재)

 

빅오(Big-O) 표기법 : 시간 복잡도를 표현. 가장 빠르게 증가하는 항만을 고려하는 표기법. 

ex) 2중 반복문의 경우에는 O(N^2)

ex) 퀵 정렬은 O(NlogN) - 최악의 경우 O(N^2)

 

- 빅오 표기법과 N이 1,000일 때의 연산 횟수

빅오 표기법	명칭	N이 1,000일 때의 연산 횟수
O(1)	상수 시간 (Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간	1,000
O(NlogN)	로그 선형 시간	10,000
O(N^2)	이차 시간	1,000,000
O(N^3)	삼차 시간	1,000,000,000 (일반적으로 코테에서 사용 어려움)
O(2^n)	지수 시간

 

- N의 범위와 시간 복잡도

N의 범위	일반적으로 사용 가능한 시간복잡도 (시간 제한 1초 기준)
500	O(N^3)
2,000	O(N^2)
100,000	O(NlogN)
10,000,000	O(N)

 

 

 

 

2. 공간복잡도

- int 리스트 크기에 따른 메모리 사용량 

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

* 보통 메모리 사용량을 128~512MB 정도로 제한. 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘 설계.

* 파이썬은 Int 자료형 없지만 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다.

 

 

 

 

 

3. 시간과 메모리 측정

1) 수행 시간 측정 소스 코드 (python)

import time
start_time = time.time() # 측정 시작

#프로그램 소스코드
end_time = time.time() # 측정 종료
print("time : ", end_time - start_time) # 수행 시간 출력

 

2) 메모리 사용량 측정

memory_profiler 라이브러리 사용.

참고 자료 : https://has3ong.tistory.com/149

[Python] Memory_Profiler, 메모리 사용량 확인하기

 

 

참고 도서 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈)