해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다.
3-3장 검색 알고리즘 - 천장함수 (2/5)
천장함수 Ceiling Function
천장함수 = 올림 함수, 내림 함수
검색에 필요한 비교 횟수 평균값 : log n회
(이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이 된다.)
검색 성공 시 : log n - 1회
검색 실패 시 : [log(n + 1)]회
검색 실패 시, 사용한 [ ]은 천장 함수 기호를 나타낸다.
[x]는 x의 천장 함수이고, x보다 크거나 같으면서 가장 작은 정수이다.
ex)
[3.5] = 4
ceil(3.23) = 4
floor(3.23) = 3
'SCHOOL > 알고리즘' 카테고리의 다른 글
| 4-1장 스택과 큐 - 큐 Queue (ing) (1) | 2024.04.15 |
|---|---|
| 4-1장 스택과 큐 - 스택 Stack (1) | 2024.04.15 |
| 3-3장 검색 알고리즘 - 이진검색 (1/5) (1) | 2024.04.15 |
| 3-2장 검색 알고리즘 - 선형(순차)검색 | 보초법 검색 (5) | 2024.04.15 |
| 3-1장 검색 알고리즘 - 검색과 키 그리고 배열 (1) | 2024.04.15 |