문서 보기문서 편집수정 내역 시간 복잡도 (덤프버전으로 되돌리기) [include(틀:이론 컴퓨터 과학)] [목차] == 개요 == {{{+1 [[時]][[間]][[複]][[雜]][[度]] / time complexity}}} [[컴퓨터과학]] 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도는 [[점근 표기법]]을 이용하여 나타낸다.[* 점근 표기법은 시간 복잡도를 나타낼 때에 주로 사용되는 표기법이기 때문에 많은 이들이 시간 복잡도와 점근 표기법을 구분하지 못하는 경우가 많으나, 엄밀하게는 시간 복잡도와 점근 표기법은 전혀 다른 것이다. [[변위]]라는 물리량을 반드시 [[미터]]로만 표기할 필요는 없지만 가장 많이 쓰이는 단위가 미터인 것과 비슷하다.] == 설명 == 정의에서 알 수 있는 사실이지만, 시간 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘임을 뜻한다. 위로 갈수록 간단하고, 아래로 갈수록 복잡해지며, [math(\log n)]은 [[이진로그|[math(\log_2n)]]]을 뜻한다.[* 2를 밑으로 하는 로그는 [[국제표준화기구|국제표준규격]](ISO 31-11)에서 [math(\rm lb)]로 표기할 것을 권장하고 있지만 대문자 O 표기법에서는 로그의 밑이 의미가 없기 때문에 그냥 [math(\log n)]으로 나타낸다.][* 대부분의 경우에 [math(\log_2n)] 을 의미한다는 것이지, 항상 그렇지는 않다. BST 같은 halving 알고리즘들이 대다수이기는 하지만, reference 가 3개 이상 있는 트리의 traversal 같은 경우는 로그의 밑이 3 이상이 될 수 있다. 로그의 밑을 명시하지 않는 이유는, 로그함수의 정확한 밑이 중요한 것이 아닌, 시간복잡도가 상수형태보다는 높고 선형형태보다는 낮다는 점이기 때문] * [math(\mathcal{O}(1) )]과 같은 [[상수#s-1]](constant) 형태 * [math(\mathcal{O}(\log n) )]과 같은 [[로그(수학)|로그]](logarithmic) 형태[* 이진 탐색이 대표적인 예이다.] * [math(\mathcal{O}(n) )]과 같은 선형[* 개념의 이해만을 위해 덧붙이자면, 친구네 집 아파트(101동)에 도달했을 때, 친구네 주소(302호)를 알고 있으면 [math(\mathcal{O}(1) )]로 친구네 집에 들어갈 수 있다. 그런데 101동밖에 모른다면, 최악의 경우 그 101동의 모든 호수를 뒤져가며 찾아야지 않겠는가? 이런 경우를 [math(\mathcal{O}(n) )]으로 생각할 수 있겠다.] * [math(\mathcal{O}(n\log n) )] 과 같은 선형로그 형태[* 퀵 정렬, 병합 정렬, 힙 정렬은 이런 시간 복잡도를 가진다.] * [math(\mathcal{O}(n^c) )], [math(\mathcal{O}(n^3) )]과 같은 [[다항식|다차]](polynomial) 형태[* 위의 시간 복잡도 [math(\mathcal{O}(n) )]인 경우에서 파생되어, A아파트 특정 단지, 특정 동, 특정 호에 사는 친구네 집을 찾으려고 한다. (2차) 친구네 집이 몇 단지인지는 아는데, 동·호수를 모른다면 최악의 경우 그 아파트 단지의 모든 동수와 호수를 뒤져가며 찾아야 하므로 (동수)*(호수)의 시간 복잡도를 가지며 이를 [math(\mathcal{O}(n^2) )]으로 생각할 수 있겠다. (3차) 친구네 집이 몇 단지인지도 모른다면, 최악의 경우 A아파트의 모든 단지수와 동수와 호수를 다 뒤져봐야 하므로 (단지수)*(동수)*(호수)의 시간 복잡도를 가지며 이를 [math(\mathcal{O}(n^3) )]으로 생각할 수 있겠다.] * [math(\mathcal{O}(c^n) )], [math(\mathcal{O}(3^n) )]과 같은 [[거듭제곱|지수]](exponential) 형태[* [math(3^n)]은 [math((2^n)^{\log 3})]으로도 쓸 수 있기 때문에 [math(2^n)]의 예시만 드는 경우도 많다.][* 실제 코드에서 생각보다 자주 보게 된다. [[메모이제이션]]을 하지 않은 재귀 함수가 지수 형태의 시간 복잡도를 갖기 때문] * [math(\mathcal{O}(n!) )]과 같은 [[계승(수학)|팩토리얼]](factorial) 형태[* 억지로 만들지만 않는다면 이 이상은 볼 수 없다. 스털링 근사를 이용하면 [math(n!\sim(n/e)^n)]이므로 팩토리얼 이상의 [[테트레이션|[math(\mathcal{O}(n^{n^{n^{\cdots}}}) )]]] 형태의 시간 복잡도를 가진 루프를 만들 수도 있지만, 일반적으로 알고리즘을 다룰 때에는 전수조사([[브루트 포스]])보다 효율적인 것만 다룬다. 대개의 경우 전수조사가 [math(\mathcal{O}(n!) )]이라 [math(n^n)] 같은 것은 다루지 않는다.][* 초당 10조 개의 명령문을 수행하는 컴퓨터가 [math(n=1000)]이고 [math(2^n)]의 작업을 수행한다면 [math(3.4\times10^{280})]년 동안의 시간이 필요한데, 이 정도면 [[빅뱅 우주론#s-6|'''우주가 통째로 멸망하고도 남는다.''']] 참고로 [math(1)] [[아가라#s-3]]가 [math(10^{224})]이다.] 연산의 횟수가 다항식으로 표현될 경우, 계산의 편의성을 위해 불필요한 정보는 모두 버린 후 시간 복잡도를 계산한다. 조금 더 자세하게 말하자면, 해당 식의 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시킨다. 예를 들어 [math(n)]개의 데이터에 대한 연산 횟수가 [math(2n^3-5n^2+n+1)]일 경우 시간 복잡도는 [math(\mathcal{O}(n^3) )]이다. 최고차항의 계수 [math(2)]와 최고차항을 제외한 부분 [math(-5n^2+n+1)]이 시간 복잡도에 영향을 안 끼치는 것은 아니나, 전체적인 관점에서 보면 [math(n)]이 충분히 커질 경우 최고차항이 압도적 영향을 끼치고 그 외의 항들은 그에 비하면 먼지만도 못한 떨거지들(...)이기 때문이다. 잘 납득이 안 된다면 [[점근 표기법#s-3|여기]]에 적힌 설명을 보자. 여기서, 일반적으로 위로 갈수록 알고리즘이 매우 빨라지며[* 다차 형태라 할지라도, [math(\mathcal{O}(n^{1/2}) )] 등 지수가 [math(1)]보다 작은 경우, [math(\mathcal{O}(n^{1/c}) )]은 [math(\mathcal{O}(\sqrt[c]{n}) )]이므로 [math(\mathcal{O}(n) )] 같은 선형보다 항상 빠르다. 소수 판별 등이 이런 상황의 대표적인 경우로, 함수의 인수가 [math(n)]일 때 이를 [math(1)]부터 [math(n)]까지 나눈다면 [math(\mathcal{O}(n) )]의 시간 복잡도를 가진다. 하지만, 모든 합성수 [math(n)]은 [math(n)]의 제곱근보다 작은 소인수를 반드시 하나 이상 가지므로, [math(1)]부터 [math(\sqrt{n})]까지만 나누면 [math(\mathcal{O}(\sqrt{n}) )]의 시간 복잡도를 가지게 되어, 같은 결과를 내면서도 연산 속도가 엄청나게 상승한다.], 아래로 갈수록 [math(n)]의 값이 커지고 '''급격하게''' 알고리즘의 수행 시간이 증가한다. 예를 들어, [math(n)]에 대한 [math(\mathcal{O}(1) )], [math(\mathcal{O}(\log n) )], [math(\mathcal{O}(n) )], [math(\mathcal{O}(n\log n) )], [math(\mathcal{O}(n^2) )], [math(\mathcal{O}(n^3) )], [math(\mathcal{O}(2^n) )], [math(\mathcal{O}(n!) )]를 나열하여 비교하면 다음과 같다. || 시간/n || 1 || 2 || 3 || 4 || 8 || 16 || 32 || 64 || 1000 || || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || || log n || 0 || 1 || 1.58 || 2 || 3 || 4 || 5 || 6 || 9.97 || || '''n''' || '''1''' || '''2''' || '''3''' || '''4''' || '''8''' || '''16''' || '''32''' || '''64''' || '''1000''' || || n log n || 0 || 2 || 4.75 || 8 || 24 || 64 || 160 || 384 || 9966 || || n^^2^^ || 1 || 4 || 9 || 16 || 64 || 256 || 1024 || 4096 || 1000000 || || n^^3^^ || 1 || 8 || 27 || 64 || 512 || 4096 || 32768 || 262144 || 1000000000 || || 2^^n^^ || 2 || 4 || 8 || 16 || 256 || 65536 || 4294967296 || 약 1.844 x 10^^19^^ || 약 1.07 x 10^^301^^ || || n! || 1 || 2 || 6 || 24 || 40320 || 20922789888000 || 약 2.63 x 10^^35^^ || 약 1.27 x 10^^89^^ || 약 4.02 x 10^^2567^^ || [math(n)]의 값이 작을 때는 알고리즘 사이에 큰 차이가 없고, 심지어 시간 복잡도가 복잡한 알고리즘이 시간 복잡도가 낮은 알고리즘보다 부분적으로 빠른 경우도 있지만, 보다시피 [math(n)]이 값이 커지면 커질수록 시간 복잡도가 복잡한 알고리즘은 수행 시간이 급격하게 길어지게 된다. 이를 대표적으로 나타내는 것이 정렬 문제이다. 2중 for문을 사용한 정렬은 시간 복잡도가 [math(n^2)]과 같은 제곱(quadratic) 형태로, sort 함수를 이용한 정렬과 비교했을 때 수행 시간이 엄청나게 길어지게 된다. 비슷한 형태의 시간 복잡도를 가지는 함수는 사실 큰 차이가 없지만, 시간 복잡도 함수의 형태 자체가 다르면 바로 신세계가 열리는 것을 볼 수 있다. [math(n=64)]일 때 [math(n^2)]와 [math(n^3)]은 [math(64)]배 '''밖에''' 차이가 나지 않지만[* [math(64)]배 차이가 큰 차이가 아니라는 것은 사실 이상하지만, 위 표에서 보듯 시간 복잡도의 형태 자체가 달라지면 본문에 비슷하게 서술한대로 안드로메다급 차이가 나기 때문에, 비교적 차이가 '''매우''' 적게 난다는 뜻. 물론 [math(n)]의 값이 커지면 커질수록 이 차이는 더욱 급격하게 벌어진다.], [math(n^2)]와 [math(2^n)]의 차이는 어마어마한 것을 보라.[* 압축 암호찾기 프로그램의 경우, 정해진 글자에 따라 모든 경우를 하나하나 대입하므로 [math(n)]값이 조금만 커져도 수행 시간이 넘사벽으로 나타나는 것을 알 수 있다. 영문자 소문자(26)+대문자(26)+숫자(10)+공백 정도만 해도 총 시간 복잡도가 [math(\mathcal{O}(63^n) = \mathcal{O}(2^{n\log63}) )]의 형태이기 때문에, [math(n = 6)]만 되어도 약 625억 단계의 연산이 필요하다. 즉, 조금만 긴 암호에 대해서는 '''전혀''' 쓸모없는 프로그램이다.] 이로 인해서, 매우 작은 [math(n)]이 입력값으로 들어오는 몇몇 특별한 알고리즘이 아닌 이상, 지수급 이상의 시간 복잡도를 가지는 알고리즘은 어느 정도 큰 [math(n)] 값이 입력으로 들어올 때 성능이 급격하게 떨어지므로 거의 써먹을 수가 없다. 이것을 또 뒤집어 말하면, 알고리즘을 어떻게든 개선해서 [math(2^n)]과 같은 지수 형태의 알고리즘의 코드를 [math(n^c)]의 다항 형태로, 혹은 [math(n^c)]의 다항 형태를 [math(n\log n)]의 로그 형태로 어떻게든 변경한다면, 풀어야 할 문제의 규모가 큰 상황에 적용할 때 프로그램의 엄청난 성능 향상을 기대할 수 있다는 말이 된다. 신호처리에서 [math(\mathcal{O}(n^2))]의 복잡도를 보이는 [[이산 푸리에 변환]](DFT) 대신 [math(\mathcal{O}(n\log n))]로 더 빠른 고속 푸리에 변환(FFT)을 사용하는 것이 좋은 예시이다. [include(틀:문서 가져옴, this=문단, title=점근 표기법, version=70)] == 활용 == 실무 프로그래밍에서 로직의 소요 시간이라는 요소가 가지고 있는 중요성을 생각했을 때, 매우 중요한 요소임에는 틀림 없으나 시간 복잡도는 n이 극한에 가까운 값을 가진 가정을 가진 이론적인 상황에서만 적용되는 내용이라 [[https://en.wikipedia.org/wiki/Galactic_algorithm|galactic algorithm]]처럼 행성만한 컴퓨터가 나오지 않는 한 시간 복잡도만 우월하고 실용적으로 쓰이지 않을 알고리즘도 존재한다. 사실 [[벤치마크]]가 실행 시간에 대한 실험, 통계학적인 근거가 되어 주기 때문에 현업 프로그래머들이 시간 복잡도에 관한 수학적인 논증을 할 필요는 거의 없다고 볼 수 있다. 현대적인 컴퓨터는 CPU, GPU, 메모리, 운영체제가 복잡하게 엮여 동작하기 때문에 아무리 알고리즘을 잘 만들더라도 실제로 실행해 보았을 때는 딴판인 결과를 주는 경우가 많으며, 특히 컴퓨터 메모리 구조가 계층적이기 때문에 여기에 맞추어 튜닝할 수 있는 소수의 전문가들을 빼고는 알고리즘 개선으로 극한의 최적화를 달성할 수 있는 경우가 거의 드물다. == 관련 문서 == * [[P-NP 문제]] [[분류:알고리즘]][[분류:해석학(수학)]]캡챠되돌리기