시간 복잡도는 무엇이고 왜 중요할까?

한국어판 위키백과에서는 시간 복잡도를 다음과 같이 설명하고 있다.

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.
예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다.

이 설명을 한번에 이해 하였다면 이런 곳에 계실 분이 아니다. 읽지 않아도 된다.

이런 걸 왜 만들었을까?

교재에 있는 시간 복잡도의 정의를 보면 자연스레 이런 생각이 들게 된다. 도대체 왜 이런 어려운 개념을 만들었을까?

소프트웨어 개발이란 컴퓨터라는 강력한 성능의 계산기를 이용해 주어진 문제를 해결하는 작업이다. 그런데 어떠한 문제의 답을 계산하는 방법은 한 가지가 아닐 수 있다. 시간복잡도는 다양한 풀이법(알고리즘) 중에 어느 것이 더 효율적인지를 판별하기 위해 만든 것이다.

자신이 만든 코드의 효율성을 짐작도 못하는 사람이 소프트웨어 개발을 할 수 있을까? 시간 복잡도는 책에서나 나오는 현실과 동떨어진 이론이 아니다. 오히려 꼭 알아야 할 기본 중의 기본이다. 만약 개발자들의 머릿속에서 시간 복잡도가 사라진다면 소프트웨어 수준은 수십년 전 수준으로 퇴보할 것이다.

쉽게 말해서 유튜브가 이렇게 되어버릴 수 있다.

알고리즘의 효율성을 따지는 법

200*10 이라는 곱셈 문제를 푼다고 생각해보자. 참가 인원 100명 중 곱셈 문제를 빠르게 해결한 사람부터 상금을 받는다. (손으로 수학 문제를 푸는 것도 '문제를 해결하는 유한한 절차'라는 알고리즘의 정의에 부합한다.)

• 200을 10번 더한다
• 초등학교 수학 시간에 배운 곱셈 방식대로 푼다
• 윈도우 계산기를 쓴다
• 종이를 쓸 것도 없다. 10을 곱했으니까 0 하나만 더 붙이면 답이 된다

대부분 마지막 방법으로 쉽게 풀어낼 것이다. 가능하면 빠른 시간 안에 문제를 풀고 싶은 것이 당연하기 때문이다. 하지만 암산을 곱셈을 해결하는 가장 좋은 알고리즘이라고 할 수 있을까? 복잡하고 큰 숫자를 암산으로 계산하는 것은 매우 어렵다. 숫자가 복잡해질수록 계산기를 이용해 푸는 것이 훨씬 빠르다. 같은 종류의 문제인데도 입력이 달라지니 효율적인 풀이 방식이 변해버린 것이다.

200*10과 같이 단순하거나 작은 숫자는 암산이 제일 빠르다. 복잡한 숫자일수록 계산기를 이용하는 것이 빠르다. 모든 곱셈 문제를 최적으로 해결할 수 있는 하나의 알고리즘은 존재하지 않는 셈이다.

Big-O 시간 복잡도는 다음과 같은 방법으로 적당히 알고리즘을 평가한다.

• 최악의 상황만 가정한다
  • 운 좋게 암산하기 좋은 숫자가 나오는 최선의 상황(Big-omega)은 가정하지 않는다.
  • 평균적인 상황(Big-Theta)이 어떤지도 계산하지 않는다. 곱셈의 '평균적인 상황'을 정의하기 쉽지 않기 때문이다.
• 연산의 횟수가 적을수록 효율적인 알고리즘으로 본다. 다른 변수(하드웨어 성능 등)는 무시한다.
• 연산의 횟수도 정확하게 세는게 아니라 대충 어림짐작한다.

시간 복잡도는 어디까지나 '정확히'가 아니라 '적당히' 계산한다는 점을 잊어선 안된다. 실제 소프트웨어의 성능에 영향을 미치는 수많은 요소(하드웨어 성능, 메모리 계층구조의 적절한 사용, 캐싱 여부 등)를 모두 무시한다. 중요하지 않아서가 아니라 계산하기 어려워서이다.

연산 횟수를 짐작하는 방법

극히 예외적인 경우를 제외하면, 연산 횟수는 입력 데이터의 크기에 비례해 증가하는 변수이다. 따라서 시간복잡도는 입력의 크기를 정의역(x)으로, 계산의 횟수를 치역(y)으로 하는 함수로 표현한다.

시간 복잡도의 목적이 어디까지나 알고리즘을 적당히 평가하는 것이라는 점을 생각하면, 연산의 횟수를 마지막 하나까지 세는 것은 쓸데없는 일이다. 결과를 좌우하는 제일 중요한 변수만 계산한다. 중요한 변수만 계산한다는 말의 의미를 예제를 통해 알아본다. 어떤 알고리즘의 입력이 n일 때 연산 횟수가 다음과 같다고 하자.

n이 1이나 2와 같은 작은 수일 때는 뒤에 더해진 10만이 결과값에 중요한 영향을 미친다. 그러나 n의 값을 키우다 보면 10만이라는 숫자는 점점 초라해진다. n이 1만이면 $5n^2$는 5억이다. 연산을 5억 번하나 5억 10만 번 하나 무슨 차이란 말인가? 10만은 떼버리는게 낫다.

한편 n이 1만일 때 2500n은 2500만이다. 마찬가지로 5억번이나 5억 2500만번이나 큰 차이로 보이진 않는다. 떼버리자. 2500만과 10만을 떼버리는 판인데 $n^2$앞의 5를 살려두는 것도 이상하다. 그냥 다 떼버리자.

처음의 '입력이 1만이면 5억 2510만번을 계산한다'에서, '대충 1억번은 넘을 것 같다'로 수준이 내려왔다. '입력이 n일 때 대충 $n^2$정도 될 것 같다.' 라는 말을 줄여 $O(n^2)$로 표기한다. 이처럼 시간복잡도는 함수식에서 최고차항만 남기고 모든 상수를 떼버리는, 충격적일 정도로 게으른 방식으로 알고리즘의 성능을 평가한다. 이렇게 대충해도 괜찮은 걸까?

입력이 1만일 때 대충 몇 억번인 함수보다는 대충 몇 만번인 함수가 훨씬 낫다. 물론 계산 과정에서 떼버린 변수들에 의해 오차가 매우 심하게 발생할 수 있다. 예를들어 연산 횟수가 다음과 같더라도 똑같이 $O(n^2)$이다.

실제 프로젝트에서 이런 알고리즘을 짠 동료와 같은 취급을 받는다면 매우 억울할 것이다. 그러나 Big-O 시간복잡도에서는 입력이 무한대로 커질 수 있다고 가정한다. $10^{99999999999}$이라는 큰 숫자도 무한대 앞에선 별 것 아니다. 입력이 커질수록 둘다 $O(n^2)$이라는 큰 그림에 점점 가까워진다. 그래서 Big-O를 '점근적' 시간복잡도라고 하는 것이다.

마치며

지금까지 시간복잡도를 계산하는 목적과, 대강의 방법에 대해 알아보았다. 이 글의 목적은 시간복잡도를 공부하기 위한 동기를 부여하는 것이기 때문에 실제 자료구조나 알고리즘에 대한 이야기는 하지 않았다. 알고리즘 교재의 첫 2~3페이지를 친절하게 풀어 쓴 수준이다. 자료구조의 연산별 시간복잡도, 코드를 보고 시간복잡도를 계산하는 방법 등 자세한 이야기는 다음 기회에 다룰 예정이다.

마지막으로 위키백과에서 설명한 '시간복잡도'를 다시 한 번 읽어보자. 설명이 조금이라도 이해하기 쉬워졌다면 내 목적은 다한 것이다.

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.
예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다.