Counting Sort1 Lecture 5: Linear Sorting Lecture 5: Linear Sorting 1. Review 복습Comparison search lower bound: any decision tree with n nodes has height ≥ ⌈log₂(n+1)⌉−1비교 기반 탐색 알고리즘은 최소한 ⌈log₂(n+1)⌉−1 높이의 결정 트리를 가진다.즉, 어떤 비교 기반 탐색을 사용하더라도 최소 log(n) 만큼은 비교해야 한다 Can do faster using random access indexing: an operation with linear branching factor!"하지만 비교 기반이 아닌 방법, 예를 들어 랜덤 액세스 인덱싱을 사용하면, 브랜칭 팩터가 선형(즉, 한 번에 많은 선택지 접근 가능)이라서 더 빠르게 탐색할 수 있다.. 2025. 6. 6. 이전 1 다음
