시간 복잡도

덤프버전 :

'''이론 컴퓨터 과학
{{{#fff

Theoretical Computer Science
'''

[ 펼치기 · 접기 ]
이론
기본 대상
수학기초론(수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론) · 이산수학(그래프 이론) · 수치해석학 · 확률론통계학] · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론
재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론
FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
계산 복잡도 이론
점근 표기법 · 튜링 기계^고전, PRAM, 양자, 비결정론적^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법)
수학적 최적화
조합 최적화
외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화
내부점 방법 · 경사하강법
선형계획법
심플렉스법
정보이론
데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
컴퓨팅 방법론
병렬 컴퓨팅(병렬 아키텍처 · 암달의 법칙 · 병렬 알고리즘) · 분산 컴퓨팅(분산 알고리즘 · 클러스터 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅) · 멀티코어 컴퓨팅 · 대칭형 다중 처리(SMP)
암호학
해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식
블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식
공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
프로그래밍 언어이론
프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초
정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현
배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^, 피보나치 힙^
계산 수론 및 암호학
밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘
계산기하학
볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론
탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학




1. 개요
2. 설명
3. 활용
4. 관련 문서


1. 개요[편집]


/ time complexity

컴퓨터과학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다.[1]


2. 설명[편집]


정의에서 알 수 있는 사실이지만, 시간 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘임을 뜻한다.

위로 갈수록 간단하고, 아래로 갈수록 복잡해지며, [math(\log n)]은 [math(\log_2n)]을 뜻한다.[2][3]
  • [math(\mathcal{O}(1) )]과 같은 상수(constant) 형태
  • [math(\mathcal{O}(\log n) )]과 같은 로그(logarithmic) 형태[4]
  • [math(\mathcal{O}(n) )]과 같은 선형[5]
  • [math(\mathcal{O}(n\log n) )] 과 같은 선형로그 형태[6]
  • [math(\mathcal{O}(n^c) )], [math(\mathcal{O}(n^3) )]과 같은 다차(polynomial) 형태[7]
  • [math(\mathcal{O}(c^n) )], [math(\mathcal{O}(3^n) )]과 같은 지수(exponential) 형태[8][9]
  • [math(\mathcal{O}(n!) )]과 같은 팩토리얼(factorial) 형태[10][11]

연산의 횟수가 다항식으로 표현될 경우, 계산의 편의성을 위해 불필요한 정보는 모두 버린 후 시간 복잡도를 계산한다. 조금 더 자세하게 말하자면, 해당 식의 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시킨다. 예를 들어 [math(n)]개의 데이터에 대한 연산 횟수가 [math(2n^3-5n^2+n+1)]일 경우 시간 복잡도는 [math(\mathcal{O}(n^3) )]이다. 최고차항의 계수 [math(2)]와 최고차항을 제외한 부분 [math(-5n^2+n+1)]이 시간 복잡도에 영향을 안 끼치는 것은 아니나, 전체적인 관점에서 보면 [math(n)]이 충분히 커질 경우 최고차항이 압도적 영향을 끼치고 그 외의 항들은 그에 비하면 먼지만도 못한 떨거지들(...)이기 때문이다. 잘 납득이 안 된다면 여기에 적힌 설명을 보자.

여기서, 일반적으로 위로 갈수록 알고리즘이 매우 빨라지며[12], 아래로 갈수록 [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
n2
1
4
9
16
64
256
1024
4096
1000000
n3
1
8
27
64
512
4096
32768
262144
1000000000
2n
2
4
8
16
256
65536
4294967296
약 1.844 x 1019
약 1.07 x 10301
n!
1
2
6
24
40320
20922789888000
약 2.63 x 1035
약 1.27 x 1089
약 4.02 x 102567
[math(n)]의 값이 작을 때는 알고리즘 사이에 큰 차이가 없고, 심지어 시간 복잡도가 복잡한 알고리즘이 시간 복잡도가 낮은 알고리즘보다 부분적으로 빠른 경우도 있지만, 보다시피 [math(n)]이 값이 커지면 커질수록 시간 복잡도가 복잡한 알고리즘은 수행 시간이 급격하게 길어지게 된다. 이를 대표적으로 나타내는 것이 정렬 문제이다. 2중 for문을 사용한 정렬은 시간 복잡도가 [math(n^2)]과 같은 제곱(quadratic) 형태로, sort 함수를 이용한 정렬과 비교했을 때 수행 시간이 엄청나게 길어지게 된다.

비슷한 형태의 시간 복잡도를 가지는 함수는 사실 큰 차이가 없지만, 시간 복잡도 함수의 형태 자체가 다르면 바로 신세계가 열리는 것을 볼 수 있다. [math(n=64)]일 때 [math(n^2)]와 [math(n^3)]은 [math(64)]배 밖에 차이가 나지 않지만[13], [math(n^2)]와 [math(2^n)]의 차이는 어마어마한 것을 보라.[14]

이로 인해서, 매우 작은 [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)을 사용하는 것이 좋은 예시이다.


파일:CC-white.svg 이 문단의 내용 중 전체 또는 일부는 점근 표기법 문서의 r70에서 가져왔습니다. 이전 역사 보러 가기
파일:CC-white.svg 이 문단의 내용 중 전체 또는 일부는 다른 문서에서 가져왔습니다.
[ 펼치기 · 접기 ]
점근 표기법 문서의 r70 (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)
문서의 r (이전 역사)





3. 활용[편집]


실무 프로그래밍에서 로직의 소요 시간이라는 요소가 가지고 있는 중요성을 생각했을 때, 매우 중요한 요소임에는 틀림 없으나 시간 복잡도는 n이 극한에 가까운 값을 가진 가정을 가진 이론적인 상황에서만 적용되는 내용이라 galactic algorithm처럼 행성만한 컴퓨터가 나오지 않는 한 시간 복잡도만 우월하고 실용적으로 쓰이지 않을 알고리즘도 존재한다.

사실 벤치마크가 실행 시간에 대한 실험, 통계학적인 근거가 되어 주기 때문에 현업 프로그래머들이 시간 복잡도에 관한 수학적인 논증을 할 필요는 거의 없다고 볼 수 있다. 현대적인 컴퓨터는 CPU, GPU, 메모리, 운영체제가 복잡하게 엮여 동작하기 때문에 아무리 알고리즘을 잘 만들더라도 실제로 실행해 보았을 때는 딴판인 결과를 주는 경우가 많으며, 특히 컴퓨터 메모리 구조가 계층적이기 때문에 여기에 맞추어 튜닝할 수 있는 소수의 전문가들을 빼고는 알고리즘 개선으로 극한의 최적화를 달성할 수 있는 경우가 거의 드물다.


4. 관련 문서[편집]




파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-05 07:57:59에 나무위키 시간 복잡도 문서에서 가져왔습니다.

[1] 점근 표기법은 시간 복잡도를 나타낼 때에 주로 사용되는 표기법이기 때문에 많은 이들이 시간 복잡도와 점근 표기법을 구분하지 못하는 경우가 많으나, 엄밀하게는 시간 복잡도와 점근 표기법은 전혀 다른 것이다. 변위라는 물리량을 반드시 미터로만 표기할 필요는 없지만 가장 많이 쓰이는 단위가 미터인 것과 비슷하다.[2] 2를 밑으로 하는 로그는 국제표준규격(ISO 31-11)에서 [math(\rm lb)]로 표기할 것을 권장하고 있지만 대문자 O 표기법에서는 로그의 밑이 의미가 없기 때문에 그냥 [math(\log n)]으로 나타낸다.[3] 대부분의 경우에 [math(\log_2n)] 을 의미한다는 것이지, 항상 그렇지는 않다. BST 같은 halving 알고리즘들이 대다수이기는 하지만, reference 가 3개 이상 있는 트리의 traversal 같은 경우는 로그의 밑이 3 이상이 될 수 있다. 로그의 밑을 명시하지 않는 이유는, 로그함수의 정확한 밑이 중요한 것이 아닌, 시간복잡도가 상수형태보다는 높고 선형형태보다는 낮다는 점이기 때문[4] 이진 탐색이 대표적인 예이다.[5] 개념의 이해만을 위해 덧붙이자면, 친구네 집 아파트(101동)에 도달했을 때, 친구네 주소(302호)를 알고 있으면 [math(\mathcal{O}(1) )]로 친구네 집에 들어갈 수 있다. 그런데 101동밖에 모른다면, 최악의 경우 그 101동의 모든 호수를 뒤져가며 찾아야지 않겠는가? 이런 경우를 [math(\mathcal{O}(n) )]으로 생각할 수 있겠다.[6] 퀵 정렬, 병합 정렬, 힙 정렬은 이런 시간 복잡도를 가진다.[7] 위의 시간 복잡도 [math(\mathcal{O}(n) )]인 경우에서 파생되어, A아파트 특정 단지, 특정 동, 특정 호에 사는 친구네 집을 찾으려고 한다. (2차) 친구네 집이 몇 단지인지는 아는데, 동·호수를 모른다면 최악의 경우 그 아파트 단지의 모든 동수와 호수를 뒤져가며 찾아야 하므로 (동수)*(호수)의 시간 복잡도를 가지며 이를 [math(\mathcal{O}(n^2) )]으로 생각할 수 있겠다. (3차) 친구네 집이 몇 단지인지도 모른다면, 최악의 경우 A아파트의 모든 단지수와 동수와 호수를 다 뒤져봐야 하므로 (단지수)*(동수)*(호수)의 시간 복잡도를 가지며 이를 [math(\mathcal{O}(n^3) )]으로 생각할 수 있겠다.[8] [math(3^n)]은 [math((2^n)^{\log 3})]으로도 쓸 수 있기 때문에 [math(2^n)]의 예시만 드는 경우도 많다.[9] 실제 코드에서 생각보다 자주 보게 된다. 메모이제이션을 하지 않은 재귀 함수가 지수 형태의 시간 복잡도를 갖기 때문[10] 억지로 만들지만 않는다면 이 이상은 볼 수 없다. 스털링 근사를 이용하면 [math(n!\sim(n/e)^n)]이므로 팩토리얼 이상의 [math(\mathcal{O}(n^{n^{n^{\cdots}}}) )] 형태의 시간 복잡도를 가진 루프를 만들 수도 있지만, 일반적으로 알고리즘을 다룰 때에는 전수조사(브루트 포스)보다 효율적인 것만 다룬다. 대개의 경우 전수조사가 [math(\mathcal{O}(n!) )]이라 [math(n^n)] 같은 것은 다루지 않는다.[11] 초당 10조 개의 명령문을 수행하는 컴퓨터가 [math(n=1000)]이고 [math(2^n)]의 작업을 수행한다면 [math(3.4\times10^{280})]년 동안의 시간이 필요한데, 이 정도면 우주가 통째로 멸망하고도 남는다. 참고로 [math(1)] 아가라가 [math(10^{224})]이다.[12] 다차 형태라 할지라도, [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}) )]의 시간 복잡도를 가지게 되어, 같은 결과를 내면서도 연산 속도가 엄청나게 상승한다.[13] [math(64)]배 차이가 큰 차이가 아니라는 것은 사실 이상하지만, 위 표에서 보듯 시간 복잡도의 형태 자체가 달라지면 본문에 비슷하게 서술한대로 안드로메다급 차이가 나기 때문에, 비교적 차이가 매우 적게 난다는 뜻. 물론 [math(n)]의 값이 커지면 커질수록 이 차이는 더욱 급격하게 벌어진다.[14] 압축 암호찾기 프로그램의 경우, 정해진 글자에 따라 모든 경우를 하나하나 대입하므로 [math(n)]값이 조금만 커져도 수행 시간이 넘사벽으로 나타나는 것을 알 수 있다. 영문자 소문자(26)+대문자(26)+숫자(10)+공백 정도만 해도 총 시간 복잡도가 [math(\mathcal{O}(63^n) = \mathcal{O}(2^{n\log63}) )]의 형태이기 때문에, [math(n = 6)]만 되어도 약 625억 단계의 연산이 필요하다. 즉, 조금만 긴 암호에 대해서는 전혀 쓸모없는 프로그램이다.