반응형 결정 트리1 Introduction to Computational Complexity theory of a Problem: The sorting Algorithm Problem 이전까지는 주어진 문제를 해결하는 알고리즘 분석에 중점을 뒀었다. 즉 문제 자체의 속성보다는 특정 알고리즘의 속성에 초점을 맟췄었다. 예를 들어 순차 탐색 알고리즘의 시간 복잡도를 분석할 때 시간 복잡도는 θ(n)이다. 이것은 당연히 탐색 문제에 θ(n) 알고리즘이 필요하다는 의미가 아니다. T(n)=n 함수는 탐색 문제의 속성이 아닌 문제에 대한 탐색 알고리즘의 속성이다. 이 장에서는 계산 복잡도 이론(computational complexity theory)이라는 이론적인 컴퓨터 과학 분야에 대해 알아볼 것이다. 알고리즘 분석에서는 문제를 해결하기 위해 특정 알고리즘이 필요로 하는 리소스 양을 분석하는데 전념했지만 계산 복잡성 이론은 동일한 문제를 해결하는데 사.. 2021. 12. 13. 이전 1 다음 반응형
