NP완전1 2021.6.14 TIL: [알고리즘] NP-완전 (NP-Completeness) 여러 문제들을 분류해 보면 주어진 문제의 해를 구하는 알고리즘이 전혀 존재하지 않는 풀 수 없는 문제들이 존재한다. 그리고 풀 수 있는 문제들이 존재한다. 풀 수 있는 존재들을 분류 하면 현실적인 시간 내에 풀 수 없는 문제들과 현실적인 시간 내에, 즉 합리적인 시간 내에 풀 수 있는 문제들이 있다. 오늘 배운 NP-완전 문제들은 현실적인 시간 내에 풀 수 없는 문제들에 속할 것이라고 추정되는 문제들이다. 현실적인 시간은 다항식 시간(polynomial time)을 의미한다. 입력의 크기를 n이라고 할 때 n의 다항식으로 표시되는 시간을 말한다. 즉, O(n^k) 나 O(3nk + 5nk -1), O(n log n) 등이다. 비다항식 시간의 예로는 O(2^n) 혹은 O(n!) 등이 존재한다. 문제에서 요.. 2021. 6. 14. 이전 1 다음
