다항 시간

다항 시간(多項時間)은 어떠한 문제를 계산하는 데에 걸리는 시간 m(n)이 문제의 크기 n의 다항식 함수보다 크지 않은 것을 가리킨다.

대문자 O 표기법을 사용하면 m(n) = O(nk)이 된다. 여기서 k는 문제에 따라 다른 상수 값이다.

일반적으로 입력 길이의 다항 시간이 걸리는 경우를 '빠른', 혹은 '다루기 쉬운'(tractable) 경우라고 표현한다. 반대로 다항 시간보다 오래 걸리는 경우를 초다항 시간(超多項時間)으로 부르며, 이 경우는 '다루기 힘든'(intractable) 경우로 표현한다. 초다항 시간에 속하는 예로는 지수 시간이 있다.

결정론적 튜링 기계로 다항 시간에 풀 수 있는 결정 문제의 복잡도 종류는 P이다. 다항 시간에 답이 맞는지 틀린지를 검사할 수 있는 판정 문제의 복잡도 종류는 NP이다. 다시 말하면, NP는 비결정론적 튜링 기계로 다항 시간에 풀 수 있는 판정 문제의 복잡도 종류이다.

다항시간의 종류 

 선형 시간: O(n)
 제곱 시간: O(n2)
 세제곱 시간: O(n3)

같이 보기 
 계산 복잡도 이론
 상수 시간
 지수 시간
 P-NP 문제
 NP
 알고리즘
 점근 표기법
 시간 복잡도

계산 복잡도 이론