728x90 반응형 NP2 NP - TSP 외판원 문제(TSP)NP는 정답을 빠르게 검증할 수 있는 문제 집합이다. 즉, 어떤 해답이 주어졌을 때, 그것이 맞는지 다항 시간 내에 확인 가능한 문제들을 말한다. NP-complete는 NP 문제 중 가장 어려운 문제들로, NP에 속하면서 모든 NP 문제로부터 다항 시간 내에 환원이 가능한 문제이다. NP-hard는 모든 NP-complete 이상의 난이도를 포함하는 상위 개념이다. 이 집합은 NP를 포함하지 않을 수도 있으며, 검증조차 다항 시간 내에 불가능할 수 있는 문제까지 포함한다. P ⊆ NP NP-complete ⊆ NP NP-complete ⊆ NP-hard TSP는 하나의 경로가 주어졌을 때, 그 경로가 총얼마의 비용을 갖는지 계산하는 데는 O(n)으로 정답을 빠르게 검.. 2025. 7. 11. 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 반응형