algorithm - 为什么k元搜索的比较平均是k*ln(N)/ln(k)？

Question

我知道该函数执行了 ln(N)/ln(K) 次；但平均而言它执行了 K 次操作吗？

问题:

1. 有没有证据表明 k*ln(N)/ln(K) 是平均执行次数？
2. 如果这个公式是正确的，那么三元搜索将是最快的搜索，因为 k/ln(k) 将是最小值(对于整数)，因为 3 是最接近“e”(实数最小值)的整数，这很容易证明使用微分。

此外，我认为三元搜索更快；因为我制作了一个比较计算机程序。

Answer 1

1. 不，因为正确答案是 (k - 1) log n/log k + O(1):只需要 k - 1 次比较(实际上只需要 lg k + O(1))来减少搜索范围的大小 k 倍。这可以通过对递归 T(1) = 1, T(2) = 2, T(n) = (k - 1) + T(n/k) 的归纳来证明。

2. (k - 1)/log k 的整数 argmin 出现在 2 处。有很多计算机体系结构原因可以说明为什么三元搜索无论如何都可能更快。