[1장] 복잡도

1.복잡도

• 시간 복잡도 : 연산에 필요한 계산의 횟수
• 공간 복잡도 : 연산에 필요한 메모리의 사이즈
• trade-off: 시간 복잡도 ~= 1/공간 복잡도
• Asymptotic notation : big-O, thetha, omega

1.1 시간 복잡도

빅-오 노테이션과 명칭 정리

big-O notation	명칭
O(1)	상수 시간(Constant)
O(logN)	로그 시간
O(N)	선형시간
O(NlogN)	로그 선형 시간
O(NK)	다항 시간(polynomial)

N의 범위가 주어졌을 때 사용 가능한 알고리즘의 시간 복잡도

N의 범위	시간 복잡도
N = 8 ~ 15	O(2N) + 가지치기
N = 500	O(N3)
N = 2000	O(N2)
N = 100,000	O(NlogN)
N = 10,000,000	O(N)

1.2 공간 복잡도

int a[1000] : 4KB (1000 * 4Byte)
int a[1000000] : 4MB
int a[2000][2000] : 16MB (4*10^6 * 4Byte)

만약 리스트의 크기가 1000만 단위 이상이라면 알고리즘을 잘못 설계한 것이 아닌지 고민