시간 복잡도
From Wikipedia, the free encyclopedia
계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/23px-Disambig_grey.svg.png)
![]() | 이 문서는 영어 위키백과의 Time complexity 문서를 번역하여 문서의 내용을 확장할 필요가 있습니다. |
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, Pan Bubilek이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.
예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다.
시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.
알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력에 대해 걸리는 최대의 시간으로 정의할 수 있다.
그 다음으로 덜 흔하게 쓰이면서, 보통 명확하게 서술되는 측정방법은 평균 시간 복잡도이다.
시간 복잡도는 함수 T(n)의 특성에 의해 분류할 수 있다. 예를 들면, T(n)=O(n)인 알고리즘은 선형 시간 알고리즘이라고 부르며, 몇몇 M ≥ n >1에 대해 T(n)=O(Mn)이고 Mn=O(T(n)) 인 알고리즘은 지수 시간 알고리즘이라고 한다.