NP1

• 

  210713 NP vs P Polynomial problems(P) : 다형식 시간으로 해결되는 문제 ex) 정렬 : O(nlog n) , O(n^2) , 등등 Exponential problems(E) : 지수 부분이 n에 따라 무한대로 증가하는 문제 ex) n^n , n^(n^2), 2^n Interactable (Non - Computable) Problems (I) -> 결정할 수 없는 문제 ex) Halting (어떤 프로 그램이 무한 루프에 빠지는지 알아내는 알고리즘) 알고리즘에서 핵심적인 문제 : Exponential 문제를 푸는 법은 아는데 이것을 polynomial time에서 해결하는 방법, 애초에 할 수 있는지를 모름 Ex) 0/1 Knapsack -> O(nW) -> O(2^n) 되면 Exponential 이.. 미가공 필기(알고리즘) 2021. 7. 13.