Big 5 Notation#

Big 5의 핵심은 데이터 증가에 따른 성능의 변화 추세를 나타내는 것이다.

공간 복잡도 : 메모리 사용량에 대한 분석. 보통 이건 고려사항이 아니다. 이는 현대 컴퓨터는 메모리가 충분하기 때문이다. 시간 복잡도 : 실행시간에 대한 분석

Concept

• O(1) : 상수 시간. 입력 데이터의 크기에 상관없이 실행시간이 일정한 알고리즘.
• O(n) : 선형 시간. 입력 데이터의 크기에 비례하여 시간이 걸리는 알고리즘.
• O(log n) : 로그 시간. 입력 데이터의 크기에 대한 로그값에 비례하여 시간이 걸리는 알고리즘. binary search에서 나타난다. 데이터 크기의 영향을 상대적으로 덜 받는다.
• O(n^2) : 제곱 시간. 입력 데이터의 크기의 제곱에 비례하여 시간이 걸리는 알고리즘. 보통 이중 for loop에서 나타난다.
• O(n log n) : 선형로그 시간. n * log n에 비례하여 시간이 걸리는 알고리즘. 보통 quick sort, merge sort 등의 정렬 알고리즘에서 나타난다.