빅오(O, big-O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

점근적 실행 시간( Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법이다.

여기서 말하는 점근적 실행 시간이란 n이 무한대에 가까워질 때, limit 함수의 실행시간 추이를 말한다.

따라서 관심의 대상은 ‘큰 입력’이다.

예) 비행기로 엄청난 양의 정보나르기, 컴퓨터로 엄청난 양의 정보 전송하기.

점근적 실행 시간 = 시간 복잡도 = 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도

빅오는 최고차항만을 표기

ex) 입력값 n에 대해

$$ 4n^3+3n+4 $$

위 식의 횟수만큼 계산하는 함수가 있다면, 그 함수의 시간 복잡도는 최고차항인 4*(n의 세제곱)만을 고려, 그 중에서도 계수를 무시하고 세제곱이라는 차수만 고려한다. 따라서

그 함수의 시간 복잡도는 O(n^3)이다.

빅오 표기법의 종류는 크게 다음과 같다.

빅오 notation 종류
O(1) 해시 테이블의 조회 및 삽입
O(log n) 이진검색
O(n) 비정렬 리스트 최댓값, 최솟값 찾기
O(n log n) 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘, 적어도 모든 수에 대해 한번 이상은 비교해야하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n logn)보다 빠를 수 없음.
O(n^2) 버블 정렬과 같은 비효율적인 정렬 알고리즘 등
O(2^n) 피보나치 수를 재귀로 계산하는 알고리즘 등
O(n!) 외판원 문제(브루트 포스)