2.1.2 성능을 비교하는 방법: 빅오

먼저 빅오 정의를 살펴보면 다음과 같습니다.

모든 n > n₀에 대해 0 <= f(n) <= cg(n)인 양의 상수 c, n₀가 존재하면

f(n) = O(g(n))

정의만으로는 어떤 의미인지 알기 어렵습니다. 코드 2-1의 예로 빅오 정의를 이해해 봅시다. T(n)=2n+3은 n에 대한 선형 함수입니다. 선형 함수의 특징은 기울기가 증가할수록 그래프는 가파르게 그려진다는 것입니다.

그림으로 확인해 볼까요?

▲ 그림 2-1 선형 함수의 기울기