1. 시간 복잡도
- 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.
- 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스이다.
1)빅-오 표기법
- 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법 이라고 부른다.
- O(1) (constant) : 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
- O(log2 n) (Logarthmic) : 입력 데이터의 크기가 커질수록 처리 시간이 log 만큼 짧아지는 알고리즘
- 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어진 경우
- O(n) (Linear) : 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘
- 1차원 for 문
- O(n log2 n) (Linear-Logarithmic) : 데이터가 많아질 수록 처리시간이 로그 배 만큼 더 늘어나는 알고리즘
- 정렬 알고리즘 중 병합 정렬, 퀵 정렬
- O(n^2) (Quadratic) : 데이터가 많아질 수록 제곱으로 처리시간이 늘어난다.
- 이중 루프
- O(2^n) (Exponential) : 데이터가 많아질수록 기하급수적으로 처리시간이 증가한다.
- 피보나치수열, 재귀가 역기능을 할 경우도 해당된다.
2. 공간 복잡도
- 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 나타낸다.
- 고정 공간과 가변 공간이 있음
- 고정 공간(알고리즘과 무관한 공간) : 코드 저장 곤간, 단순 변수 및 상수
- 가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
- 반복문일 때는 n값에 상관없이 같은 공간을 계속 사용함으로 공간 복잡도는 O(1)이다.
- 재귀 함수일 때는 n번 반복함에 따라 1~n 까지 공간이 n개 필요하여 O(n) 이 된다.