| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
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) )]과 같은 선형(linear)[5]
- [math(\mathcal{O}(n\log n) )] 과 같은 선형로그(linear-logarithmic) 형태[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=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)을 사용하는 것이 좋은 예시이다.
시간 복잡도에 계수 a,b,c...는 무시할 수 있다. 예를 들어, 어떤 작업을 했을 때 프로그램 A가 n의 시간이 걸리고 프로그램 B가 2n의 시간이 걸린다 했을 때, 두 프로그램의 성능의 차이는 없다.
그 이유는 두 프로그램의 시간 차이는 프로그램의 차이가 아니라 하드웨어의 차이이기 때문이다. 이는 Blum's Theorum에서 설명되는데, 이 이론에 따른 간단한 예를 들자면, 튜링머신의 테이프의 각 셀을 한 개만 읽을 수 있을 때와 두 개씩 읽을 수 있을 때의 필요한 계산과정이 약 두 배 차이가 남으로, 한번에 읽고 쓸 수 있는 셀의 양에 따라 시간이 1/a로 줄어들게 된다.
이런 이유로 시간복잡도는 각 복잡도의 원형이 되는 함수와 비교하는 Big-O 점근법을 사용한다. 왜냐면 애초에 계수가 복잡도에 영향을 주지 않는다고 가정하기 때문이다.
마찬가지로 공간복잡도는 이론상에서는 신경이 덜쓰이는데, 튜링머신의 테이프가 무한하게 길다고 가정하기 때문이다.
3. 활용
실무 프로그래밍에서 로직의 소요 시간이라는 요소가 가지고 있는 중요성을 생각했을 때, 매우 중요한 요소임에는 틀림 없으나 시간 복잡도는 n이 극한에 가까운 값을 가진 가정을 가진 이론적인 상황에서만 적용되는 내용이라 galactic algorithm처럼 행성만한 컴퓨터가 나오지 않는 한 시간 복잡도만 우월하고 실용적으로 쓰이지 않을 알고리즘도 존재한다.사실 벤치마크가 실행 시간에 대한 실험, 통계학적인 근거가 되어 주기 때문에 현업 프로그래머들이 시간 복잡도에 관한 수학적인 논증을 할 필요는 거의 없다고 볼 수 있다. 현대적인 컴퓨터는 CPU, GPU, 메모리, 운영체제가 복잡하게 엮여 동작하기 때문에 아무리 알고리즘을 잘 만들더라도 실제로 실행해 보았을 때는 딴판인 결과를 주는 경우가 많으며, 특히 컴퓨터 메모리 구조가 계층적이기 때문에 여기에 맞추어 튜닝할 수 있는 소수의 전문가들을 빼고는 알고리즘 개선으로 극한의 최적화를 달성할 수 있는 경우가 거의 드물다.
4. 관련 문서
[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억 단계의 연산이 필요하다. 즉, 조금만 긴 암호에 대해서는 전혀 쓸모없는 프로그램이다.