1-3
다항 시간
polynomial time
단계 수가 n, n², n³ 처럼 n^k 꼴로 묶이는 빠르기
입력 크기 n 에 대해 어떤 상수 k 가 있어 O(n^k) 단계 안에 끝나는 계산을 말한다. 복잡도 이론에서는 다항 시간을 「효율적으로 풀 수 있음」의 수학적 기준으로 삼는다(코범–에드먼즈 논제). 다항식은 더하고 곱하고 합성해도 다항식이어서, 이 기준은 계산 모형이나 부프로그램 호출 방식에 따라 흔들리지 않는다. 다만 n^100 도 다항 시간이므로 「다항 시간 = 실제로 빠름」은 아니다. 기준이 이렇게 너그러운데도 NP-완전 문제에는 다항 시간 알고리즘이 하나도 알려져 있지 않다.