탐색 문제1 More Computational Complexity theory of a problem :The searching Algorithm 저번 게시글에서는 계산 복잡도 이론에 대해 간단히 알아보고 이에 대한 개념을 일부 정렬 문제에 적용해보았다. 이번에는 탐색 문제에 계산 복잡도 이론을 적용해보자. 다음과 같은 사항들을 이번에는 알아볼 것이다. 키 비교를 이용하는 배열 탐색에 대한 하한 선택 문제: Adversary Arguments 소개 K번째 가장 작은 키 찾기 선택 문제에 대한 확률적 알고리즘 The Searching Problem 탐색 문제는 일부 키 필드의 값을 기준으로 전체 레코드를 검색하는 것을 말한다. 예를 들어보자. 레코드는 개인 정보로 구성되고 키 필드는 주민등록번호라고 할 수 있다. 그렇다면 우리는 해당 키 필드를 이용하여 레코드를 탐색할 수 있는 것이다. 이전에 다뤄본 정렬 문제와 마찬가지로 탐색 문제에서도 하한을 계.. 2021. 12. 21. 이전 1 다음
