2
이 함수는 ln (N)/ln (K) 회 실행된다는 것을 알고 있지만 평균적으로 K 연산을 수행합니까?k-ary 검색의 평균 비교는 왜 k * ln (N)/ln (k)입니까?
질문 :
- 케이 속에는 * (N)/LN (K)의 실행의 평균 개수임을 증거가 있는가?
- 이 공식이 맞다면 3이 가장 쉬운 정수 "e"(실제 최소값)이기 때문에 k/ln (k)가 최소값 (정수)으로 삼차원 검색이 가장 빠를 것입니다 차별화를 사용하여 증명할 수 있습니다.
또한 저는 컴퓨터 프로그램을 비교했기 때문에 3 순위 검색이 더 빠르다고 믿습니다. (1) 비교 (정말에만 LG K + (1) O) 필요가 감소 - 단 k는 : - 정답이기 때문에
예 3자가 더 빠르기 때문에 'e'에 가까워서 빠릅니다. 그러나 컴퓨터는 바이너리에서 더 빠릅니다. 당신은 3 원 컴퓨터가 있다면 3을 원할 것입니다. –
질문의 두 번째 부분은 [여기] (http://stackoverflow.com/questions/3498382/why-use-binary-search-if-theres- 삼항 탐색). – dasblinkenlight