我已经编写了一种算法，用于在复杂度为 log2(n)/5 的排序数组中进行搜索。它有用吗？
sahil garg
问问题
2159 次
5 回答
12
可以证明，对于仅假设比较操作的搜索，您不能低于 O(log(n))。log2(n)/5 的复杂度与 O(log(n)) 相同。
有用性取决于您使用它的目的。
于 2009-02-13T06:33:43.003 回答
4
嗯。棘手的问题。你为什么不发布你的算法，让我们看看你做了什么。
但是，对于真正的胜利，您应该比 O(log2 log2 (n)) 更好？这就是插值搜索平均所做的事情。
于 2009-02-13T13:39:33.463 回答
2
除了排序之外，如果没有关于数组的任何其他假设，或者没有任何预计算/数据结构创建，不可能比 log2n 做得更好。
如果您要查找的元素不在您的数组中，您如何建议在少于 log₂n 的步骤中终止？
于 2009-02-13T06:57:07.267 回答
1
当然，您总是可以争论非线性搜索是否一定比线性搜索快：http ://www.ddj.com/184405848
即，如果您正在搜索高速缓存行，则线性搜索它可能比分支搜索更快。
于 2009-02-13T07:01:59.313 回答
1
我认为如果它在实践中比其他现有的 O(logn) 搜索算法更快会很有用。换句话说，如果您的基准测试显示速度有所提高。然而，对于非常大的输入，恒定时间改进（如 1/5）并没有太大的区别。这就是为什么最重视算法的渐近复杂度的原因。
于 2009-02-13T13:47:26.033 回答