algorithm - 为什么k-ary search的比较平均值是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 处。有很多计算机体系结构的原因可以解释为什么三元搜索可能会更快。