왜 시간 복잡도(Time complexity)인데 T(n)이 아니고 O(n)이라고 쓰는 걸까?

들어가며

면접 예상 질문을 보다가 '시간복잡도와 공간복잡도에 대해 설명해 주세요.', '평소 시간복잡도를 이야기할 때 다른 것을 사용하지 않고, Big-O를 사용하는 이유가 무엇인가요'와 같은 질문을 접했다.

정답을 외울 수도 있지만, 나도 문득 궁금해져 더 찾아보게 되었다. 왜 시간 복잡도(Time complexity)인데 T(n)이 아니고 O(n)이라고 쓰는 걸까? 그냥 그런 줄 아는 것보다 재미있는 역사적 맥락이 있었다.

시간복잡도란?

시간복잡도란 무엇인가. 학부 교과서의 내용을 요약하자면 '실행 환경 등의 종속적인 요소를 제거한 알고리즘 실행 완료 경과 시간'을 말한다.

역사적 유래(origin of O)

언제부터 시간복잡도를 O(n) 으로 쓰기로 한 것일까. 이 표기 자체는 1894년 독일의 수학자 폴 바흐만(Paul Bachmann)이 처음 도입하고, 에드문트 란다우(Edmund Landau)가 정립한 수학적 표기법이다. 정수론과 해석학에서 무한대로 갈 때 오차 범위 표기의 편의를 위해서 사용했다. 정밀한 오차를 계산하기보다 추정치로 'O(x) 이상 늘어나지 않는다'를 표현하고자 한 것이다. 여기서 'O'는 독일어 Ordnung(오르드눙) 에서 따온 것인데 이는 Order (차수, 규모, 질서) 와 같은 의미라고 보면 된다.

알고리즘 시공간 복잡도 연구의 선구자인 주리스 하트마니스(왼쪽)와 리처드 스턴스(오른쪽)
출처: Computational Complexity

이 수학의 용어를 주리스 하트마니스와 리처드 스턴스가 1965년 On the Computational Complexity of Algorithms 이라는 논문에서 알고리즘의 시공간 복잡도를 수학적으로 표현하는 방식을 도입했다. 이 논문 내에서 사실 T(n)이라는 표현이 나오긴 한다. 그러나 엄밀히 수행시간을 계산하기보다 P 문제와 NP 문제에 따른 풀이 가능성을 이야기하기 위해 논리적 의미로 T(n)을 사용했다. 이 논문을 온전히 이해하긴 어렵지만, 복잡도를 기준으로 풀 수 있는 문제의 영역을 명확히 증명함으로써, 하드웨어의 단순한 물리적 속도 향상이 아닌 알고리즘 자체의 복잡도를 개선해야만 더 어려운 문제를 정복할 수 있다는 현대 컴퓨터 과학의 당연한 명제의 토대가 되었다.

컴퓨터 과학의 복잡도 표현을 정립한 도널드 크누스(Donald Knuth) 교수
출처: Stanford News (Image credit: Chuck Painter / Stanford News Service)

《The Art of Computer Programming》의 저자인 도널드 크누스가 이 아이디어를 가지고 컴퓨터 과학의 복잡도 표현을 정립했다. 자주 사용하는 Big-O 뿐 아니라, Big-Omega, Big-theta 가 그것이다.

Big-O가 필요했던 그 시절의 사정

그렇다면 이런 연구가 이루어지고 하드웨어와 상관없는 구조적 복잡성을 표현해야 했던 이유는 무엇일까?

1960년대 즈음의 컴퓨터는 우리가 지금 알고 있는 컴퓨터와는 많은 것이 달랐다. 하드웨어를 직접 조작하는 형식의 코드가 많고 OS 같은 개념이 대중화 되지 않았었다. 심지어 1바이트가 8비트라는 기준 조차도 당시에는 없었다. 하드웨어 제조사 마다 누군가는 6비트를, 누군가는 9비트를 1바이트로 정해서 만들었다. 더욱이 이전 모델에서 돌아가던 코드가 다음 모델에서 돌아가지 않는 것이 당연한 상식이었다. 컴퓨터를 바꾸면 코드를 다시 짜야 했다.

이런 환경에서 어떤 알고리즘의 실행시간이 느리다면, 그것이 알고리즘의 문제인지 하드웨어의 문제인지 판단하기가 어려웠다. 생각해보면 요즘은 알고리즘 테스트에서 시간복잡도를 주로 접해서 그렇지, 문제에서 코드의 시간복잡도를 개선할 것이 아니라 정해진 코드를 돌리는 하드웨어를 개선하는 것도 가능한 선택지이긴 한 것이다.

지금도 애플리케이션의 처리량을 개선할 때나, 데이터 양에 따른 인덱스의 효율성 등을 계산할 때, 같은 소프트웨어를 쓴다고 해서 같은 결과가 나오지 않기는 마찬가지다. 같은 Mysql 버전을 깔면 다 똑같은 속도가 나오지 않는다는 것이다. 이런 상황의 의사결정을 위해서 프로파일링을 하는 것도 코드 밖의 조건을 개선 해야할지, 코드를 개선해야 할지 판단하기 위한 것이니 비슷한 이치라고 보겠다.

(trivia - 이런 시대에 IBM의 System360이 컴퓨터의 새로운 지평을 열었다. 그리고 이때 1바이트는 8비트였기에 이렇게 널리 쓰이게 되었다. 이걸 만들 때 당시에 OS를 만들었던 경험을 가지고 만들어진 고전이 바로 The Mythical Man-month 이다.)

시간복잡도의 다양한 표현

이처럼 하드웨어 환경과 관계 없이 알고리즘 효율성을 표현하기 위해 정립된 Big-O 표기는 가끔 수학적으로 엄밀하지 못한 표현으로 쓰인다. 바로 '최선의 경우 O(1)이다' 라는 표현이다. Big-O 표기는 시간복잡도의 점근적 상한선을 의미한다. 흔히 말하는 '최악의 경우'를 뜻한다.

점근적이라는 의미는 어떤 기준이나 한계치에 점점가까워지지만 닿지는 않는 것을 말한다. 따라서 복잡도의 점근적 상한이란 상한에 완전히 도달하지는 않지만, 가까워 지는 것을 의미한다고 볼 수 있다.

Big-Omega($\Omega$)는 점근적 하한선, Big-Theta($\Theta$)는 점근적 상하한이 동일한 경우를 의미한다. 따라서 엄밀히 말하면 알고리즘의 시간복잡도는 단순히 '최악일 때 O(n), 최선일 때 O(1)' 과 같이 Big-O 표기로만 퉁쳐서 표현하는 것은 수학적으로는 문제가 있다. 입력크기 n에 대한 상한과 하한이 다르고 그것을 표기하고 싶을 때는 '상한은 O(n), 하한은 $\Omega$(1) 이다' 라고 해야 정확한 것이다.

마치며

시간복잡도와 Big-O 표기는 결국 컴퓨터 공학이 막 태어날 무렵인 1960년대 ~ 1970년대에, 하드웨어의 불안정성과 파편화를 극복하고 알고리즘의 본질적 효율성을 표현하기 위해 탄생한 선구적 해결책이었다. 아직까지도 이 표기를 유효하게 쓰고 있으니 말이다.

조사를 하면서 시간복잡도의 수학적 증명 뿐 아니라 시대상을 이해하기가 꽤 힘들었다. 컴퓨터라는 것의 컨셉이 60년전과 지금 상상을 초월할 정도로 변해버렸기 때문이다.

올 초 태어난 아들이 자라서 10년 뒤에 컴퓨터 라는 것을 어떻게 이해할 지 모르겠다. 애플 비전 프로 같은 것들이 그냥 컨텍트 렌즈 같은 형태로 구현이 되고, 더 이상 키보드 같은 것도 없는 세상이 올 수도 있겠지. 그 때 라떼 이야기를 하면서 지금 이 글을 타이핑한 키크론 키보드를 보여줘야 겠다.