최근 수정 시각 : 2022-08-06 16:54:02

시간 복잡도

이산수학 · 수리논리학
Discrete Mathematics · Mathematical Logic
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
이론
기본 대상 명제 · 집합 · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
명제 논리 · 논증{ 귀납논증 · 연역논증} · 공리 및 공준 · 증명{ 귀류법( 자동정리증명) · 수학적 귀납법 · 반증 · 역산( 검산) · PWW · 더블 카운팅 · 논증의 재구성} · 존재성과 유일성 · · · 대우 · 예비사항( 약어 및 기호) · 논리함수 · 논리 연산 · 동치관계( 등식) · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리 · 양상논리 · 술어 논리
집합 원소 · 공집합 · 집합족( 묶어 세기) · 곱집합 · 멱집합 · 관계 · 서수( 비교하기 · 순서 관계 · 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 구간 · 기수( 초한기수) · 절대적 무한
수열 등차수열( 뛰어 세기 · 등차중항) · 등비수열( 등비중항) · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
알고리즘 순서도 · 시간 복잡도( 점근 표기법) · 자료구조 · 해시 · 오토마타( FSM · 푸시다운 · 튜링 머신 · 콘웨이의 생명 게임) · 동적 계획법( 사전 공격 · 레인보우 테이블) · 프로그래밍( 코딩 · 컴파일링) · 유클리드 알고리즘 · RSA( 쇼어 알고리즘) · 유전 알고리즘
조합 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 스털링 수( 제1종 스털링 수 · 제2종 스털링 수) · 카탈랑 수 · 벨 수 · 라흐 수 · 그래프( 수형도) · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로)
확률 사건 · 가능성 · 확률 변수 · 확률 분포( 정규 분포 · 이항 분포 · 푸아송 분포 · 카이-제곱 분포 · t-분포 · z-분포) · 조건부 확률 · 기댓값 · 도박사의 오류 · 몬티 홀 문제 · 뷔퐁의 바늘
기타 셈 측도 · 비율( 분율) · 진법( 2 · 8 · 10 · 12 · 16 · 60) · 난수 · 암호 · 시행착오( 예상과 확인 · 브루트 포스) · 벤 다이어그램 · 구구단( 네이피어 계산봉) · 주산 · 산가지 · 암산 · 논리 회로 · 인접행렬 · 결합법칙 · 분배법칙 · 교환법칙 · 마크업 언어
정리
4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 베이즈 정리 · 비둘기 집의 원리 · 포함·배제의 원리 · 드모르간 법칙 · 대각선 논법 · 전체 확률의 법칙 · 쾨니히스베르크 다리 건너기 문제 · 상트페테르부르크의 역설 · 러셀의 역설 · 거짓말쟁이의 역설 · 투표의 역설 · 바나흐-타르스키 역설 · 퍼스의 항진명제 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 마르코프 부등식 · 체비쇼프 부등식 · 큰 수의 법칙( 무한 원숭이 정리 · 던파확률의 법칙) · 중심극한정리 · 굿스타인 정리 · 불완전성 정리 · 힐베르트의 호텔 · 정지 문제 · 연속체 가설 · P-NP 문제미해결 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 카오스 이론미해결
분야
집합론 · 조합론 · 범주론 · 정수론 · 확률론 · 전산학 · 암호학 · 통계학 · 수학철학 · 수리사회학
관련 문서
철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 }}}}}}}}}}}}

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

1. 개요

/ Time Complexity

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

2. 설명

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

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

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

여기서, 일반적으로 위로 갈수록 알고리즘이 매우 빨라지며[11], 아래로 갈수록 [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)]배 차이가 나지만[12], [math(n^2)]와 [math(2^n)]의 차이는 어마어마한 것을 보라.[13]

이로 인해서, 매우 작은 [math(n)]이 입력값으로 들어오는 몇몇 특별한 알고리즘이 아닌 이상, 지수급 이상의 시간 복잡도를 가지는 알고리즘은 어느 정도 큰 [math(n)] 값이 입력으로 들어올 때 성능이 급격하게 떨어지므로 거의 써먹을 수가 없다.

이것을 또 뒤집어 말하면, 알고리즘을 어떻게든 개선해서 [math(2^n)]과 같은 지수 형태의 알고리즘의 코드를 [math(n^c)]의 다항 형태로, 혹은 [math(n^c)]의 다항 형태를 [math(c\log n)]의 로그 형태로 어떻게든 변경한다면, 풀어야 할 문제의 규모가 큰 상황에 적용할 때 프로그램의 엄청난 성능 향상을 기대할 수 있다는 말.



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

3. 활용

실무 프로그래밍에서 로직의 소요 시간이라는 요소가 가지고 있는 중요성을 생각했을 때, 매우 중요한 요소임에는 틀림 없으나 어째서인지 양산형 코더들은 물론이거니와 컴퓨터공학 전공자들 중에서도 관심을 가지는 사람이 별로 없다. 그러나, 상용 소프트웨어 개발에서는 [math(n^2)]와 [math(n^3)] 알고리즘의 차이는 단지 몇 초~수 분 차이일 뿐이지만 이를 사용하는 사용자 입장에서는 충분히 느낄 수 있을 정도기에 그 중요성은 매우 크다.

예를 들어, 내부 알고리즘이 느려서 버튼 하나 누를 때마다 5초간 기다리다가 다음 작업을 하는 것과 1초 미만의 시간을 기다리고 다음 작업을 하는 것은 상당히 큰 차이가 있다. 모 게임에서는 [math(n^5)]만큼의 시간 복잡도를 가지는 알고리즘이 적용되어 있던 내부 모듈을 [math(n^3)] 만큼의 시간 복잡도를 가지게 개선하여 유저들의 극 호평을 받은 적이 있다.

'이미 출시되어 있는 알고리즘을 가져다 쓰면 되지 않느냐?' 라고 반문하기도 하는데, 사실 현업에서는 맞는 말이다. 비즈니스 로직에 필요한 정렬/탐색 등의 알고리즘은 이미 수많은 개발자들이 연구하여 인터넷에 공유해 놓았다. 그러나 시간 복잡도의 개념을 이해하지 못한 채 무작정 그걸 갖다 쓰기만 하면 알고리즘을 올바르게 적용하는 것이 힘들어지기 마련이고, 직접 융통성 있게 알고리즘을 짜내야 하는 특수한 상황에서도 엄청난 어려움이 따르게 된다. 게다가 그 알고리즘을 쓰려면 무지막지한 돈을 요구하거나[14], GPL이 걸려 있다면...

아무튼, 정작 컴퓨터에서 매우 중요한 학문인데 대우는 안습한 기초 학문 분야의 한 사례라 할 수 있겠다.


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


4. 관련 문서



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