[ 알고리즘 ] 빅-오 표기법이란?

[ 알고리즘 ] 빅-오 표기법이란?

 

빅오 표기법은 대문자 O를 사용하기 때문에 빅(Big) 오(O)라고 부릅니다. 

 

앞 글에서 이진 탐색 알고리즘의 시간 복잡도 함수를 구하면서 

최악의 경우의 비교연산 횟수는 k+1에서 +1이 중요하지 않다고 했습니다. 

왜 그렇게 말할 수 있는지 빅-오 표기법을 통해 설명하겠습니다. 

(이해를 위해 이전 글을 읽어오시면 좋습니다.) 

---

 

 

먼저 빅-오에 대한 설명을 위해 하나의 예로 시간 복잡도 함수를 봅시다. 

시간 복잡도 함수를 T(n)를 구하는 이유는 데이터의 수 n이 증가에 따라 연산횟수의 변화 정도를 판단하기 위해서입니다. (중요)

오차 없이 시간 복잡도를 함수를 구할 수 없고, 구할 필요도 없다는 겁니다. 즉, 근사치(approximtation) 식으로 구성해도 됩니다. 

 

 

 

그럼 위의 함수에서 1정도는 빼도 되겠고,

 

 

2n는 생략해도 될까요?

네 가능합니다. 이유는 이 함수에서 2n이 차지하는 비율이 미미하기 때문입니다. 아래 표를 통해서 확인해보겠습니다.

 

 

 

---

 

티스토리 블로그에서는 수식 입력을 지원하지 않아 위의 수는 n^{2}로 표기하겠습니다.

n	n^{2}	2n	T(n)	n^{2} 비율	2n의 비율
10	100	20	120	83.33%	16.67%
100	10,000	200	10,200	98.04%	1.96%
1,000	1,000,000	2,000	1,002,000	99.80%	0.2%
10,000	100,000,000	20,000	100,020,000	99.98%	0.02%
100,000	10,000,000,000	200,000	10,000,200,000	99.99%	0.01%

 

표에서 바로 알 수 있듯이 n(데이터)가 증가하면서 2n+1이 미치는 영향은 적습니다.

따라서아래와 같이 간략화할 수 있습니다. 

 

 

 

---

이를 빅오표기법으로 표현하면 다음과 같습니다. 

"빅오 오브(of) n의 2제곱"으로 읽으면 됩니다. 

 

그럼 이제 수식을 보고 빅-오를 구할 수 있겠죠? T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 됩니다. 

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------