Ch:8: Theory of computational complexity: Searching problem and selection problem as a case study
탐색문제의 lower bound도 확인해보자
- binary search 알고리즘 사용 = worst case = logn인 효율적인 알고리즘
- searching 문제는 여러개의 key field에서 원하는 key를 검색하는 과정이다. 즉, sorting 알고리즘과 유사하게 comparison이 base가 되는 알고리즘이다. = tree구조로 모델링이 가능하다.
d = depth = comparison 횟수
- search problem의 lower bound 도 logn이므로 binary search보다 더 빠른 알고리즘은 존재하지 않는다는 결론을 얻을 수 있다.
'알고리즘 문제 풀이 > 알고리즘 이론 공부' 카테고리의 다른 글
| 부분 집합 이론 정리 (1) | 2023.08.19 |
|---|---|
| 9장 Theory of NP (0) | 2023.07.30 |
| 7장 Theory of computational complexity : Sorting problem (0) | 2023.07.30 |
| 6장 Branch and bound Algorithm (0) | 2023.07.30 |
| 5장 Backtracking Algorithm (0) | 2023.07.30 |
