빅오(Big-O)란?
알고리즘 성능을 수학적으로 표기해주는 표기법이다.
알고리즘의 실행시간보다는 데이터나 사용자 증가률에 따른 알고리즘 성능을 예측하는게 목표이므로 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거한다.
즉, 빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.
여기서 측정되는 복잡성에는 시간 복잡도와 공간 복잡도가 있다.
- 시간 복잡도 : 입력되는 n의 크기에 따라 실행되는 조작의 수
- 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리 양 (메모리 발전으로 중요도 낮아지는 중)
O(1) - 상수시간
입력 크기와 상관 없이 항상 일정한 시간이 소요되는 알고리즘이다. 예를 들어, 배열에서 특정 인덱스의 요소에 접근, 해시 테이블의 조회 및 삽입이 O(1) 시간 복잡도를 갖는다.
O(log n) - 로그시간
입력 크기에 비례하여 로그 함수의 값을 가지는 알고리즘이다. 이진 검색과 같이 입력 크기를 반으로 나누는 경우가 O(log n) 시간복잡도를 갖는다.
O(n) - 선형시간
력 크기에 비례하여 선형적으로 증가하는 알고리즘이다. 리스트나 배열을 순차적으로 탐색하는 경우 O(n) 시간복잡도를 갖는다.
O(n log n) - 선형로그 시간
입력 크기에 비례하여 로그 함수의 값과 곱해지는 알고리즘으로, 효율적인 정렬 알고리즘인 병합 정렬과 퀵정렬이 O(n log n) 시간복잡도를 갖는다.
O(n^2) - 이차시간
입력 크기의 제곱에 비례하는 알고리즘으로, 중첩된 반복문이 사용되는 정렬 알고리즘 중 선택 정렬과 삽입 정렬이 O(n^2) 시간복잡도를 갖는다.