1.1.1 빅오 표기법
정의 모든 n ≥ n0에 대해 조건 f(n) ≤ cg(n)을 만족하는 두 양의 상수 c와 n0이 있다면 f(n)은 g(n)의 빅오(big-O) 또는 f(n) = O(g(n))입니다.
cg(n)은 모든 n ≥ n0에 대해 f(n)의 상한(upper bound)2입니다. 이때 함수 f(n)의 증가 속도는 cg(n)보다 느립니다. 입력 크기 n이 충분히 크면 항상 cg(n)이 f(n)보다 큽니다.
▲ 그림 1-1 빅오 표기법
예시
n2 + n = O(n2)
2 역주 상한은 알고리즘의 실행 시간이 최악일 때도 이 시간과 같거나 빠르다는 뜻입니다.