为什么k进制搜索的比较的平均值是k * ln（N）/ ln（k）？

我知道该函数执行ln（N）/ ln（K）次;但是平均来说它是否会进行K次操作？为什么k进制搜索的比较的平均值是k * ln（N）/ ln（k）？

问题：

此外，我相信三元搜索更快;因为我做了一个比较计算机程序。

是三元组更快，因为它更接近'e'。但是，二进制计算机速度更快。如果你有三元电脑，你会想要3. – 2012-02-13 11:24:38

你的问题的第二部分是讨论[这里]（http://stackoverflow.com/questions/3498382/why-use-binary-search-if-theres-三元搜索）。 – dasblinkenlight 2012-02-13 11:24:54

不会，因为正确答案是（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）来证明。
（k-1）/ log k的整数argmin出现在2.有很多计算机体系结构的原因，为什么三元搜索可能会更快。

2012-02-13 12:08:54 wat

回答