시간 복잡도
1. 개요
Time Complexity ・ 時間複雜度
컴퓨터공학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다.[1]
2. 설명
정의에서 알 수 있는 사실이지만, 시간 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘임을 뜻한다.
위로 갈수록 간단하고, 아래로 갈수록 복잡해지며, $$\log n$$은 $$\log_2n$$을 뜻한다.[2]
- $$\mathcal{O}(1) $$과 같은 상수(constant) 형태
- $$\mathcal{O}(\log n) $$과 같은 로그(logarithmic) 형태[3]
- $$\mathcal{O}(n) $$과 같은 선형[4]
- $$\mathcal{O}(n\log n) $$ 과 같은 선형로그 형태[5]
- $$\mathcal{O}(n^c) $$, $$\mathcal{O}(n^3) $$과 같은 다차(polynomial) 형태[6]
- $$\mathcal{O}(c^n) $$, $$\mathcal{O}(3^n) $$과 같은 지수(exponential) 형태[7]
- $$\mathcal{O}(n!) $$과 같은 팩토리얼(factorial) 형태[8][9]
여기서, 일반적으로 위로 갈수록 알고리즘이 매우 빨라지며[10], 아래로 갈수록 $$n$$의 값이 커지고 '''급격하게''' 알고리즘의 수행 시간이 증가한다.
예를 들어, $$n$$에 대한 $$\mathcal{O}(1) $$, $$\mathcal{O}(\log n) $$, $$\mathcal{O}(n) $$, $$\mathcal{O}(n\log n) $$, $$\mathcal{O}(n^2) $$, $$\mathcal{O}(n^3) $$, $$\mathcal{O}(2^n) $$, $$\mathcal{O}(n!) $$를 나열하여 비교하면 다음과 같다.
$$n$$의 값이 작을 때는 알고리즘 사이에 큰 차이가 없고, 심지어 시간 복잡도가 복잡한 알고리즘이 시간 복잡도가 낮은 알고리즘보다 부분적으로 빠른 경우도 있지만, 보다시피 $$n$$이 값이 커지면 커질수록 시간 복잡도가 복잡한 알고리즘은 수행 시간이 급격하게 길어지게 된다. 이를 대표적으로 나타내는 것이 정렬 문제이다. 2중 for문을 사용한 정렬은 시간 복잡도가 $$n^2$$과 같은 제곱(quadratic) 형태로, sort 함수를 이용한 정렬과 비교했을 때 수행 시간이 엄청나게 길어지게 된다.
비슷한 형태의 시간 복잡도를 가지는 함수는 사실 큰 차이가 없지만, 시간 복잡도 함수의 형태 자체가 다르면 바로 신세계가 열리는 것을 볼 수 있다. $$n=64$$일 때 $$n^2$$와 $$n^3$$은 $$64$$배 차이가 나지만[11], $$n^2$$와 $$2^n$$의 차이는 어마어마한 것을 보라.[12]
이로 인해서, 매우 작은 $$n$$이 입력값으로 들어오는 몇몇 특별한 알고리즘이 아닌 이상, 지수급 이상의 시간 복잡도를 가지는 알고리즘은 어느 정도 큰 $$n$$ 값이 입력으로 들어올 때 성능이 급격하게 떨어지므로 거의 써먹을 수가 없다.
이것을 또 뒤집어 말하면, 알고리즘을 어떻게든 개선해서 $$2^n$$과 같은 지수 형태의 알고리즘의 코드를 $$n^c$$의 다항 형태로 어떻게든 변경한다면, 프로그램의 엄청난 성능 향상을 기대할 수 있다는 말. 이런 고로, 프로그래밍 등에서 보통 알고리즘 과목은 전공필수 내지 공학인증필수 과목으로 지정되고 있다. 그만큼 중요하고, 알아두면 쓸 곳이 많기 때문.
3. 활용
실무 프로그래밍에서 로직의 소요 시간이라는 요소가 가지고 있는 중요성을 생각했을 때, 매우 중요한 요소임에는 틀림 없으나 어째서인지 양산형 코더들은 물론이거니와 컴퓨터공학 전공자들 중에서도 관심을 가지는 사람이 별로 없다. 그러나, 상용 소프트웨어 개발에서는 $$n^2$$와 $$n^3$$ 알고리즘의 차이는 단지 몇 초~수 분 차이일 뿐이지만 이를 사용하는 사용자 입장에서는 충분히 느낄 수 있을 정도기에 그 중요성은 매우 크다.
예를 들어, 내부 알고리즘이 느려서 버튼 하나 누를 때마다 5초간 기다리다가 다음 작업을 하는 것과 1초 미만의 시간을 기다리고 다음 작업을 하는 것은 상당히 큰 차이가 있다. 모 게임에서는 $$n^5$$ 만큼의 시간 복잡도를 가지는 알고리즘이 적용되어 있던 내부 모듈을 $$n^3$$ 만큼의 시간 복잡도를 가지게 개선하여 유저들의 극 호평을 받은 적이 있다.
'이미 출시되어 있는 알고리즘을 가져다 쓰면 되지 않느냐?' 라고 반문하기도 하는데, 사실 현업에서는 맞는 말이다. 비즈니스 로직에 필요한 정렬/탐색 등의 알고리즘은 이미 수많은 개발자들이 연구하여 인터넷에 공유해 놓았다. 그러나 시간 복잡도의 개념을 이해하지 못한 채 무작정 그걸 갖다쓰기만 하면 알고리즘을 올바르게 적용하는 것이 힘들어지기 마련이고, 직접 알고리즘을 짜내야 하는 특수한 상황에서도 엄청난 어려움이 따르게 된다.
아무튼, 정작 컴퓨터에서 매우 중요한 학문인데 대우는 안습한 기초 학문 분야의 한 사례라 할 수 있겠다.
4. 관련 문서
[1] 점근 표기법은 시간 복잡도를 나타낼 때에 주로 사용되는 표기법이기 때문에 많은 이들이 시간 복잡도와 점근 표기법을 구분하지 못하는 경우가 많으나, 엄밀하게는 시간 복잡도와 점근 표기법은 전혀 다른 것이다. 본 항목 또한 오랜 시간 동안 점근 표기법 문서의 넘겨주기 항목으로 되어 있었다.[2] 2를 밑으로 하는 로그는 국제표준규격(ISO 31-11)에서 $$\rm lb$$로 표기할 것을 권장하고 있지만 대문자 O 표기법에서는 로그의 밑이 의미가 없기 때문에 그냥 $$\log n$$으로 나타낸다.[3] 이진 탐색이 대표적인 예이다.[4] 개념의 이해만을 위해 덧붙이자면, 친구네 집 아파트(101동)에 도달했을 때, 친구네 주소(302호)를 알고 있으면 $$\mathcal{O}(1) $$로 친구네 집에 들어갈 수 있다. 그런데 101동밖에 모른다면, 최악의 경우 그 101동의 모든 호수를 뒤져가며 찾아야지 않겠는가? 이런 경우를 $$\mathcal{O}(n) $$으로 생각할 수 있겠다.[5] 퀵 정렬, 병합 정렬, 힙 정렬은 이런 시간 복잡도를 가진다.[6] 위의 시간 복잡도 $$\mathcal{O}(n) $$인 경우에서 파생되어, A아파트 특정 단지, 특정 동, 특정 호에 사는 친구네 집을 찾으려고 한다. (2차) 친구네 집이 몇 단지인지는 아는데, 동·호수를 모른다면 최악의 경우 그 아파트 단지의 모든 동수와 호수를 뒤져가며 찾아야 하므로 (동수)*(호수)의 시간 복잡도를 가지며 이를 $$\mathcal{O}(n^2) $$으로 생각할 수 있겠다. (3차) 친구네 집이 몇 단지인지도 모른다면, 최악의 경우 A아파트의 모든 단지수와 동수와 호수를 다 뒤져봐야 하므로 (단지수)*(동수)*(호수)의 시간 복잡도를 가지며 이를 $$\mathcal{O}(n^3) $$으로 생각할 수 있겠다.[7] $$3^n$$은 $$(2^n)^{\log 3}$$으로도 쓸 수 있기 때문에 $$2^n$$의 예시만 드는 경우도 많다.[8] 억지로 만들지만 않는다면 이 이상은 볼 수 없다. 스털링 근사를 이용하면 $$n!\sim(n/e)^n$$이므로 팩토리얼 이상의 [math(\mathcal{O}(n^{n^{n^{\cdots}}}) )] 형태의 시간 복잡도를 가진 루프를 만들 수도 있지만, 일반적으로 알고리즘을 다룰 때에는 전수조사보다 효율적인 것만 다룬다. 대개의 경우 전수조사가 $$\mathcal{O}(n!) $$이라 $$n^n$$ 같은 것은 다루지 않는다.[9] 초당 10억 개의 명령문을 수행하는 컴퓨터가 $$n=1000$$이고 $$2^n$$의 작업을 수행한다면 $$3.4\times10^{284}$$년(약 3 나유타 아가라 년) 동안의 시간이 필요한데, 이 정도면 우주가 통째로 멸망하고도 남는다. 참고로 $$1$$ 아가라는 $$10^{224}$$.[10] 다차 형태라 할지라도, $$\mathcal{O}(n^{1/2}) $$ 등 지수가 $$1$$보다 작은 경우, $$\mathcal{O}(n^{1/c}) $$은 $$\mathcal{O}(\sqrt[c]{n}) $$이므로 $$\mathcal{O}(n) $$ 같은 선형보다 항상 빠르다. 소수 판별 등이 이런 상황의 대표적인 경우로, 함수의 인수가 $$n$$일 때 이를 $$1$$부터 $$n$$까지 나눈다면 $$\mathcal{O}(n) $$의 시간 복잡도를 가진다. 하지만, 모든 합성수 $$n$$은 $$n$$의 제곱근보다 작은 소인수를 반드시 하나 이상 가지므로, $$1$$부터 $$\sqrt{n}$$까지만 나누면 $$\mathcal{O}(\sqrt{n}) $$의 시간 복잡도를 가지게 되어, 같은 결과를 내면서도 연산 속도가 엄청나게 상승한다.[11] $$64$$배 차이가 큰 차이가 아니라는 것은 사실 이상하지만, 위 표에서 보듯 시간 복잡도의 형태 자체가 달라지면 본문에 비슷하게 서술한대로 안드로메다급 차이가 나기 때문에, 비교적 차이가 '''매우''' 적게 난다는 뜻. $$n$$의 값이 커지면 커질수록 이 차이는 물론 더욱 급격하게 벌어진다.[12] 압축 암호찾기 프로그램의 경우, 정해진 글자에 따라 모든 경우를 하나하나 대입하므로 $$n$$값이 조금만 커져도 수행 시간이 넘사벽으로 나타나는 것을 알 수 있다. 영문자 소문자(26)+대문자(26)+숫자(10)+공백 정도만 해도 총 시간 복잡도가 $$\mathcal{O}(63^n) = \mathcal{O}(2^{n\log63}) $$의 형태이기 때문에, $$n = 6$$만 되어도 약 625억 단계의 연산이 필요하다. 즉, 조금만 긴 암호에 대해서는 '''전혀''' 쓸모없는 프로그램이다.