빅 오( Big O ) 표기법이란 무엇일까?

효원이가 물어 봤을 때, 정확하게 몰랐었다가, 동우가 소개해준 책의 첫번재 페이지에 설명 되어 있는 것을 보고, 자세히 보게 되었다가, 정리하게 된다.

big O 표기법은, 전산학자들이 어떤 하나의 함수의 복잡도를 정의하는데 즐겨 사용하는 표기법이다. 표기는 다음 처럼 한다. O(함수); 식으로 표현 한다.

괄호안의 함수는 (n) 또는 (c) 로 표기하는데, c는 상수를 뜻한다. (즉 1, 2, 3, 4 등..)

함수의 복잡도란 무엇일까?

복잡도를 해결하기 위해서, n 번의 연산을 한다면, 그것은 n 번의 복잡도를 가졌다고 말할 수 있고, 표기하면, O(n) 으로 표기 된다. 어떤 일을 처리함에 있어, 그 처리의 복잡도를 뜻한다. 라고 해석 해도 될 듯 싶다.

예를 들자면, 내가 상자 1000개를 가지고 있는데, 이 상자들 중 한 상자에 만원이 들어 있다고 가정 했을때, 내가 이 만원을 찾기 위해선, 최대 1000개의 상자를 열어 봐야 할 것이다. 이것을 빅오(big O) 표기법으로 표현하자면, 만원을 찾는 함수는 O(n)의 복잡도를 가졌다고 볼 수 있는 것이다.

그렇다면, O(c)의 복잡도는 무슨 뜻인가?

어떠한 경우에서도 c번의 횟수만으로 일을 처리 할 수 있음을 뜻하는데, 위의 상자 1000개에서 만원을 찾는데, 무조건 2번만에 찾을 수 있다면, O(2)로 표기 될 수 있으며, O(2)의 복잡도를 가지고 있다고 말 할 수 있다.

무척 가벼운 연산임을 알 수 있을 것이다.

한가지 중요한 사실은 빅 오(Big O)는, 최악의 경우일 때, 복잡도를 나타낸다.

이렇게 복잡도를 표현함에 있어, 가장 복잡하지 않은 순으로 정렬하자면,

상수,  log₂n,  n, nlog₂n,  n²  ,n²  ,2ⁿ 순으로 정렬 할 수 있겠다.