728x90 반응형 P1 P, NP Polynomial time다항 시간다항 시간이란 알고리즘의 실행 시간이 입력 크기 n에 대한 다항식으로 표현되는 경우를 말합니다. 이는 O(n^k ) (k는 양의 상수)와 같은 형태로 나타나는 시간 복잡도를 의미한다. O(n), O(n²), O(n³ + n² + 3), O(log n), O(1) 등은 모두 다항 시간으로 분류되는데 O(log n), O(1)의 경우 엄밀히 말하면 다항식은 아니지만 다항 시간보다 훨씬 효율적이므로 넓은 의미에서 다항 시간 범주에 포함된다. 반면 O(2ⁿ), O(n!)과 같은 복잡도는 다항 n이 커질수록 기하급수적으로 실행시간이 폭증하여 다항 시간이 아니며, 이런 알고리즘은 대개 비실용적으로 간주한다. 어떤 문제에 대해 다항 시간 내에 항상 정답을 찾을 수 있는 알고리즘이 .. 2025. 7. 8. 이전 1 다음 728x90 반응형