빅오(O)는 왜 최악의 경우가 아닐까

상한보다 최악이 있는가

  헷갈리는 부분이라 고민을 해보고 싶어서 작성한다. 먼저 시간 복잡도에서 빅오는 충분히 큰 입력을 가정하며, 입력에 대한 연산수로 알고리즘의 실행 시간을 표기하는 방법이다. 이 때 빅오는 상한, 빅오메가는 하한, 빅세타는 평균의 의미로 사용한다. 그런데 나는 상한(Upper Bound)라는 말이 왜 최악과 같지 않은지 와닿지 않았다.

위와 아래로 일정한 범위를 이루고 있을 때, 위쪽의 한계

상한의 정의는 위쪽의 한계. 이보다 더 높을 수 없기 때문에 시간을 기준으로 가장 오래걸리는 최악이다. 그런데 왜 최악과 상한을 분리시켜 봐야하는가? 그림을 그려보았다.

상한과 하한, 최악과 최선

  알고리즘에는 입력 데이터의 수, 그리고 정렬의 경우 데이터 배열에 의해 최선/최악의 연산수가 결정된다. 어떤 알고리즘의 연산수가 위 그림처럼 최악과 최선을 가지고 있다고 해보자. 그렇다면 이 알고리즘의 데이터에 따른 연산수의 범위는 노란색 영역과 같다. 이를 고려했을 때, n₀ 이상의 범위에서는 해당 알고리즘의 시간 복잡도 범위는 상한과 하한 내에 존재한다. 즉, 상한과 최악이 같지 않다는 것은, 상한은 "여긴 넘지 않을거야"라며 어림잡아 그어놓은 경계이기 때문에 둘은 같지 않다.

 

모호하지 않은가?

  빅오는 그런 모호한 수치인 듯 하다. 아래는 n에 대한 방정식을 빅오로 표기한 것이다.

$$4n^2+3n+4   \approx   O(n^2)$$

이 식에서 n은 연산수인 자연수이므로, 당연히 4n²+3n+4 > n²이다. 연산수를 계산한 방정식보다 상한이 더 작다. 빅오를 표기하기 위해서는 최고차항 외 항은 모두 제거하고, 최고차항에서도 계수는 없애 표기하기 때문이다. 그래서 따라오는 조건이 "충분히 큰 n값"이다. n이 무한대로 가면 계수도, 다른 항이나 상수들도 의미가 없어질 수 있다.

  알고리즘은 명확해야한다라는 정의와 상반된 느낌이지만, 연산수를 명확하게 밝혀내는 비용과 이에 대한 활용 가치를 비교적으로 생각하면 현재 표시하고 있는 기법으로 충분하다는 것이다.

 

결론

  결론이다. 알고리즘의 시간 복잡도는 입력 크기에 따른 연산수에 대한 방정식을 빅오 표기법을 사용하여 표현한다. 이 때 빅오(O)로 표현된 시간 복잡도는 알고리즘의 상한을 나타내며, 최악의 경우를 뜻하진 않는다. 여기서 뜻하는 상한은 최악의 경우가 이를 넘지 않을 것이다라고 가정하는 계산된 경계다. 최악의 경우는 상한을 넘을 수 있지만, 충분히 큰 입력값을 가정하므로 최악의 경우와 상한은 비슷한 값으로 수렴한다. 또한, 시간 복잡도를 명확하게 정의하지 않은 이유로 밝혀내는 비용과 비교적인 활용 가치를 고려할 수 있다.