알고리즘 성능 평가
복잡도(Complexity)
- 알고리즘의 성능을 나타내는 기준
1. 시간 복잡도
- 알고리즘의 수행시간 분석
- 시간 복잡도가 높을수록, 수행 시간이 오래 걸리고
시간 복잡도가 낮을수록, 수행 시간이 적게 소요된다.
2. 공간 복잡도
- 알고리즘의 메모리사용량 분석
- 공간 복잡도가 높을수록, 메모리를 많이 사용하고
공간 복잡도가 낮을수록, 메모리를 적게 사용한다.
결론 : 복잡도가 낮을수록 좋은 알고리즘 !
빅오 표기법(Big-O Notation)
- 차수가 가장 큰 항을 기준으로 표현
시간 복잡도 순위
(좋은 순위부터 나쁜 순위 순)
O(1) : 상수 시간(Constant time)
O(logN) : 로그 시간(Log time)
O(N) : 선형 시간
O(NlogN) : 로그 선형 시간
O(N^2) : 이차 시간
O(N^3) : 삼차 시간
O(2^n) : 지수 시간