개요
복잡도
- 알고리즘 또는 자료구조 등의 성능을 나타내는 척도를 복잡도라 부르는데, 대부분은 Big-O 표기법을 사용한다
시간 복잡도
- 특정 입력에 대하여 시간이 얼마나 걸리는지를 측정
- 일반적으론 O(n) 시간 복잡도가 좋은 알고리즘으로 취급하며, 그 외 log(n) 정도가 바람직한 편
- n^2 또는 n! 같은 경우는 데이터가 커질수록 급격히 느려지게 된다
공간 복잡도
- 특정 입력에 대하여 얼마나 많은 메모리를 사용하는지를 측정
- 사실 시간 복잡도처럼 Big-O 표기법을 사용하진 않는데, 메모리가 지수적으로 증가하진 않기 때문
종류
정렬 알고리즘
탐색 알고리즘