빅오 표기법(Big-O notation)

성능을 절대적인 값으로 표현하지 않고 상대적으로 표현하는 방식이다.

 

예를 들면, 영화 "기생충"에서 송광호씨가 하루에 접을 수 있는 최대 피자박스의 수가 100 개 이다. 그러면 200 개를 접으려면 얼마나 걸릴까? 당연히 2 일이 걸린다. 그러면 우리는 이것을 입력(n)에 따라 비례하는 것이니 O(n)으로 표시할 수 있다. O(n)은 우리 주위에서 쉽게 볼 수 있다. 설계사무실에서의 도면, 자동차공장에서의 차량, 포장기계가 생산하는 제품 등등의 생산성능도 모두 O(n)이다. 

 

그러면 입력크기(n)가 커져도 항상 같은 시간을 유지하는 것이 있을까? 있다. 배열의 원소에 접근하려고 할 때이다. 배열의 첫 번째 원소를 가기 위해서는 배열의 첫 주소에 0을 더한 후 값을 읽어온다. 4 번째 접근하려면 배열의 첫 주소에 3을 더한 후 값을 읽어온다. 이것은 O(1)로 나타낸다.

 

아래는 "전문가다운 C++ 프로그램 디자인"에서 찾은 표이다. 알고리즘에 따라 빅오(O)의 값이 변함을 알 수 있다.

빅오(O)의 값 변화와 알고리즘 예