with with

Computational Complexity Analysis - Sorting problem 정렬문제를 해결하기 위해 사용할 수 있는 모든 알고리즘의 복잡도의 한계를 알아보자. 즉, 정렬을 Θ(n)에 끝낼 수 있는지 알아보자. (이 것이 불가능하다는 것을 증명) 정렬을 하는 기본적인 방 with611.tistory.com 이전에는 알고리즘이 갖는 한계를 알아봤었다. 이번에는 문제 자체가 갖는 한계를 알아보자. (즉, 어떠한 알고리즘을 써도 이보다 낫게 풀 수 없다는 것) 문제의 종류는 아래의 세 종류가 있다. Polynomial-Time algorithm found 다항식의 차수 시간 복잡도를 갖는 알고리즘으로 문제를 풀 수 있는 경우. - Sorting - Shortest paths problem - ..