이 글은 BOJ 블로그에 있는 글과 동일합니다.

알고리즘 공부를 시작할 때 맨 처음 만나는 개념 중 시간, 공간 복잡도가 있습니다. 안타깝게도, 이는 오개념이 가장 많이 퍼진 주제이기도 합니다. 여러 오개념이 있지만 이 글에서는…

“빅-Ω 표기법은 최선의 경우를 다룰 때 사용한다. 빅-Ө 표기법은 평균의 경우를 다룰 때 사용한다. 빅-O 표기법은 최악의 경우를 다룰 때 사용한다.”

…라는 오개념을 다룹니다. 이 주장은 각종 블로그 글은 물론, 이름 있는 출처에도 가끔씩 나오며 심지어 책으로도 나왔습니다.

잘못된 말입니다. 빅-O, 빅-Ω, 빅-Ө 표기법은 그 자체로 최선, 최악 등의 경우를 가정하지 않으며, 세 표기법 모두를 최선, 최악, 평균의 경우에 모두 사용할 수 있습니다. 단지 최악의 경우 및 빅-O 표기법을 가장 많이 쓸 뿐입니다.

올바른 용례

“길이가 n인 정수 리스트 L에 정수 target이 있는지 판별하세요“라는 문제를 다음과 같은 의사코드로 풀었다고 해봅시다.

function find(L, target):
  for x in L:
    if x == target: return true
  return false

최악의 경우는 L에 target이 없어서 L 전부를 훑어볼 때이고, 최선의 경우는 맨 첫 수가 target과 같을 때입니다. 따라서

• 이 알고리즘의 최선의 경우 시간 복잡도는 O(1)이자, Ω(1)이자, Ө(1)입니다.
• 이 알고리즘의 최악의 경우 시간 복잡도는 O(n)이자, Ω(n)이자, Ө(n)입니다.
• 평균 시간 복잡도는 정의하기 조금 어렵지만, 직관적으로 생각할 수 있는 평균의 기준을 따른다면 시간 복잡도는 O(n)이자, Ω(n)이자, Ө(n)일 것입니다.

시간 복잡도가 O(f(n))이라는 것은 수행 시간이 최대 f(n)만큼 커진다는 뜻입니다. 그것뿐입니다. 정확히 무슨 수행 시간인지는 맥락에 따라 다릅니다.

상한은 최악을 의미하지 않습니다

“빅-O 표기법은 수행 시간의 상한을 표현한다“는 맞는 말입니다. 최악의 경우에서 빅-O 표기법을 쓰면 최악의 수행 시간의 상한이 되고, 최선의 경우에서 빅-O 표기법을 쓰면 최선의 수행 시간의 상한이 됩니다. 딱 보면 뭔가 말이 안 되는 것 같은데요.

쉬운 이해를 위해, 알고리즘 중간고사를 봤다고 생각해 봅시다. 시험이 막 끝나서 정확한 점수는 모르지만, 어느 정도 예상은 할 수 있습니다. 최악의 경우(실수를 꽤 했을 때)와 최선의 경우(시도한 문제들의 풀이가 완벽할 때) 얼마나 받을지 예상을 해봅니다.

이제 친구가 여러분에게 물어봅니다. “몇 점 받을 것 같아?”

• “못 봐도 80점은 나오지 않을까?“라고 답한다면, “못 봐도“는 최악의 경우, “80점“은 예상 점수의 하한입니다. 아무리 실수를 많이 해서 마구 틀리더라도 적어도 80점은 될 것 같다는 뜻입니다.
• “잘 보면 90점도 나올 것 같아!“라고 답한다면, “잘 보면“은 최선의 경우, “90점“은 예상 점수의 하한입니다. 정말 잘 봐서 시도한 모든 풀이가 완벽하면 적어도 90점은 될 것 같다는 뜻입니다.
• “못 보면 70점 밑으로도 갈 것 같아…“라고 답한다면, “못 보면“은 최악의 경우, “70점“은 예상 점수의 상한입니다.
• “잘 봐도 60점 안 될 거야……“라고 답한다면, “잘 봐도“는 최선의 경우, “60점“은 예상 점수의 상한입니다. 괜찮습니다. 기말고사를 잘 보면 되죠.

이처럼 최선과 최악의 케이스에서 모두 예상 점수의 하한과 상한을 논할 수 있습니다. 중요한 것은 하한, 상한이 그 자체로 최선, 최악을 의미하는 것이 아니라, 단순히 특정 시나리오에서 예상 점수의 범위를 표현할 때 쓰인다는 것입니다.

알고리즘도 마찬가지입니다. 최선과 최악의 케이스에서 모두 수행 시간의 하한과 상한을 논할 수 있습니다. 하한, 상한은 단순히 특정 시나리오에서 수행 시간의 범위를 표현합니다. 그래서,

• “최악의 시간 복잡도가 O(n)“이라는 것은, 최악의 경우에 정확한 연산 횟수는 세보지 않았지만 그래도 선형 시간 안에는 돈다는 뜻입니다. 이때 n은 최악의 경우에 대한 상한입니다.
• “최선의 시간 복잡도가 O(n)“이라는 것은, 최선의 경우에 정확한 연산 횟수는 세보지 않았지만 그래도 선형 시간 안에는 돈다는 뜻입니다. 이때 n은 최선의 경우에 대한 상한입니다.
• “최악의 시간 복잡도가 Ω(n)“이라는 것은, 최악의 …중략… 그래도 선형 시간보다 빠르지는 않다는 뜻입니다.
• “최악의 시간 복잡도가 Ө(n)“이라는 것은, 최악의 …중략… 그래도 딱 선형 시간이 걸린다는 뜻입니다.

그러고 보니 Ө도 하나 얘기를 해야 되는데요…

빅-Ө는 중간을 의미하지도 않습니다

비슷한 오개념으로 “빅-Ө는 빅-O와 빅-Ω의 중간을 의미한다“라는 것이 있습니다. n과 n^2의 중간은 어디일까요?

시간 복잡도가 Ө(f(n))이라는 것은 O(f(n))인 동시에 Ω(f(n))이라는 뜻입니다. 알고 있는 Ω(하한)과 O(상한)이 다르다면, Ө는 아마도 중간 어딘가이긴 하겠지만, 정확히는 Ө를 논할 수 없다고 말해야 옳습니다. O와 Ω가 한 함수에서 딱 만나야 Ө가 생기는 것입니다.

오해가 퍼진 이유

“빅-O가 최악의 경우를 의미한다“라는 오개념이 퍼진 이유는 여러 가지가 있겠지만, 이런 이유를 들 수 있을 것 같습니다.

1. 빅-O와 최악의 경우가 대개 자주 엮입니다. 아무 입력이나 들어올 수 있는 온라인 저지 환경에서는 최악의 경우에서도 빠른 알고리즘이 선호됩니다. 그리고 수행 시간이 얼마 이하임을 알아야 알고리즘이 정당하다고 할 수 있는데, 그 상한의 역할을 하는 게 빅-O 표기법입니다. 그래서 알고리즘 문제 풀이에서는 빅-O로 최악의 시간 복잡도를 구하는 경우가 많습니다.
2. “상한“과 “최악의 경우“가 의미상으로 비슷해 보입니다. 그도 그럴 게, 최악의 시간 복잡도가 O(f(n))인 알고리즘은 모든 경우에서 O(f(n))의 시간에 돕니다. 최악의 시간 복잡도는 어떻게 보면 모든 입력의 시간 복잡도에 대한 상한인 셈입니다. 하지만 다시 정리하자면 빅-O에서 얘기하는 상한은 최선, 최악 관계없이 특정 경우에서 함수의 상한을 얘기하는 것으로, 꼭 모든 경우에 대한 상한일 필요는 없습니다.
3. Ө를 쓸 수 있는 상황에서도 O를 쓰는 경우가 많습니다. 물론 잘못된 것은 아니지만, 최악과 빅-O가 더 깊게 엮이는 효과를 어느 정도 불렀을 것 같습니다. (사실 저도 씁니다. 셋 중에 아스키 문자가 O밖에 없어서요…)

빅-O가 최악의 경우를 뜻한다고 잘못 생각한다면, 반대로 빅-Ω가 최선의 경우라고 잘못 생각하는 것도 자연스러워 보입니다. 그리고 최악과 최선을 빼고 남은 게 평균이라서 빅-Ө가 평균이라는 오개념까지 완성된 게 아닐까 추정해 봅니다.