为什么k元搜索比较平均为k * LN（N）/ LN（K）？ [英] Why is the average of comparisons of k-ary search is k* ln(N) / ln(k)?

问题描述

我知道功能的执行LN（N）/ LN（K）倍;但在平均它使ķ操作

问题：

1. 在没有任何证据证明K * LN（N）/ LN（K）是执行死刑的平均数量？
2. 如果这个公式是正确的，那么三元搜索将是最快的搜索为k / LN（K）将是最小的（整数），因为3是最接近的整数到e（实际最低），这是很容易的为了证明使用的分化。

此外，我认为，三元的搜索速度更快，因为我做了一个比较，计算机程序

。

解决方案

1. 没有，因为正确答案是（K - 1）登录N /日志K + O（1）：唯一的K - 1的比较（实际上只有LG的K + O（1））都需要降低搜索范围的由k的系数大小。这可以通过归纳于复发T（1）= 1，T（2）= 2，T（N）=（K - 1）来证明。+ T（N / K）

2. 的整数argmin（K - 1）/ 1o9氏发生在2。有大量的计算机体系结构原因，三元的搜索可能会更快反正

。

I know that the function is executed ln(N)/ln(K) times;but in average does it make K operations?

Questions:

1. is there any proof that k*ln(N)/ln(K) is the average number of executions?
2. If this formula is correct, then ternary search will be the fastest search as k/ln(k) will be minimum (for integers) because 3 is the closest integer to "e" (the real minimum) which is very easy to prove using differentiation.

Furthermore I believe that ternary search is faster;because I made a comparing computer program.

解决方案

1. No, because the correct answer is (k - 1) log n / log k + O(1): only k - 1 comparisons (really only lg k + O(1)) are needed to reduce the size of the search range by a factor of k. This can be proved by induction on the recurrence T(1) = 1, T(2) = 2, T(n) = (k - 1) + T(n / k).

2. The integer argmin of (k - 1) / log k occurs at 2. There are plenty of computer architectural reasons why ternary search might be faster anyway.

这篇关于为什么k元搜索比较平均为k * LN（N）/ LN（K）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！