[복잡도]
1) 복잡도란 ? 알고리즘의 성능을 나타내는 척도. 복잡도가 낮을수록 좋은 알고리즘.
- 시간복잡도 : 필요한 연산의 횟수, 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지
- 공간복잡도 : 필요한 메모리의 양, 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지
2) 시간복잡도
- 단순 복잡도는 시간복잡도를 의미한다. 시간제한이 관건.
- 연산은 사칙연산 비교연산을 포함(더하기 뿐만 아니라 a,b 값을 비교하는 비교연산도 한번의 연산이다.)
- 시간 복잡도를 표현할 때는 빅오 표기법(가장 빠르게 증가하는 항만을 고려하는 표기법)을 사용한다.
- 코딩테스트에서는 최악의 경우에 대한 연산 횟수가 가장중요하다. 그러니 최약의 경우의 시간 복잡도를 우선 고려해야 한다.
- 예를 들어, 2중 for문으로 5크기의 배열 내 요소들을 곱해주는 건, 5*5 즉 N의 제곱
| 빅오 표기법 | 명칭 |
| O(1) | 상수시간 |
| O(logN) | 로그시간 |
| O(N) | 선형시간 |
| O(NlogN) | 로그 선형시간 |
| O(N2) | 이차시간 |
| O(N3) | 삼차시간 |
| O(2n) | 지수시간 |
위에 있을 수록 더 빠르다~!
그리고, 특이케이스 는 연산횟수가 2N3+5N2+1000000인 알고리즘의 시간복잡도는 O(N3)이다. 가장 큰차수만 남기므로. 하지만 여기서 n이 작을 때는 상수값인 1000000이 미치는 영향력은 매우 크다. 그래서 고려는 하되. 빅오표기법이 항상 절대적인 것은 아니다.
- 시간복잡도 분석은 문제풀이의 핵심. 문제 해석전 조건을 먼조 보기도 하자. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있다. 예를 들어 데이터개수 n이 1000만개를 넘어가며 시간제한이 1초라면, 최악의 경우 O(N)의 시간복잡도로 동작하는 알고리즘을 작성해야 할 것으로 예상가능 혹은 데이터의 크기나 탐색범위가 100억을 넘어가는 경우 이진탐색과 같이 O(logN)의 시간복잡도를 가즌ㄴ 알고리즘을 작성해야 할 것이다.
* N의 범위가 500인 경우: 시간복잡도가 O(N3)인 알고리즘을 설계
* N의 범위가 2000인 경우: 시간복잡도가 O(N2)인 알고리즘을 설계
* N의 범위가 100000인 경우: 시간복잡도가 O(NlogN)인 알고리즘을 설계
* N의 범위가 10000000인 경우: 시간복잡도가 O(N)인 알고리즘을 설계
3) 공간복잡도
- 공간복잡도도 빅오표기법 사용. 일반적으로 메모리 사용량기준은 mb단위로 제시된다.
- 코딩테스트의 대부분은 배열으 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 코딩테스트에서 보통 메모리사용량을 128~512MB 로 제한하기 때문에 데이터의 개수가 1000만단위가 넘어가지 않도록 알고리즘설계를 해야함
4) 시간과 메모리 측정
- 공간복잡도도 빅오표기법 사용. 일반적으로 메모리 사용량기준은 mb단위로 제시된다.
- 코딩테스트의 대부분은 배열을 사용
- 파이썬에서는 코드의 시간과 메모리를 측정할 수 있다.