是否有任何算法可以在排序数组中搜索复杂度小于 log2(n) 的元素
我编写了一个在排序数组中搜索的算法，复杂度为 log2(n)/5 。它有用吗？
i have coded an algorithm for search in sorted array with complexity log2(n)/5 .Is it useful?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
可以证明，对于仅假设比较操作的搜索，您无法获得低于 O(log(n)) 的结果。 log2(n)/5 的复杂度与 O(log(n)) 相同。
有用性取决于你用它做什么。
It is provable that you can't get lower than O(log(n)) for a search that assumes only compare operations. a complexity of log2(n)/5 is the same thing as O(log(n)).
Usefulness depends on what you use it for.
嗯。 棘手的问题。 为什么不发布你的算法并让我们看看你做了什么。
然而，为了真正的胜利，你应该比 O(log2 log2 (n)) 更好？ 这就是插值搜索的平均作用。
http://en.wikipedia.org/wiki/Interpolation_search
Hm. Tough question. Why don't you post your algorithm and let us see what you do.
However, for a real win you should be better than O(log2 log2 (n))? That's what interpolation search does on average..
http://en.wikipedia.org/wiki/Interpolation_search
除了数组已排序之外，如果没有任何其他关于数组的假设，或者没有任何预计算/数据结构创建，就不可能比 log2n 做得更好。
如果您要查找的元素不在数组中，您建议如何在少于 log2n 步的时间内终止？
It's not possible to do better than log₂n without any other assumptions about the array other than that it's sorted, or without any precomputation / data structure creation.
How do you propose to terminate in less than log₂n steps if the element you are looking for is not in your array?
当然，您始终可以争论非线性搜索是否一定比线性搜索更快：http: //www.ddj.com/184405848
即，如果您正在搜索缓存行，则线性搜索可能比分支搜索更快。
Of course, you can always argue about whether or not a non-linear search is necessarily faster than a linear search: http://www.ddj.com/184405848
I.e., if you are searching a cache line, it can be faster to search it linearly than branching.
我认为，如果它在实践中比其他现有的 O(logn) 搜索算法更快，那将会很有用。 换句话说，如果您的基准测试显示速度有所提高。 然而，对于非常大的输入，恒定时间改进（例如 1/5）不会产生太大差异。 这就是为什么最重要的是算法的渐近复杂性。
I think it would be useful if it is faster than other existing O(logn) search algorithms in practice. In other words, if your benchmark testing shows speed improvements. However, for very large inputs constant time improvements (like 1/5) don't make much of a difference. That's why most importance is given to an algorithm's asymptotic complexity.