gpt4 book ai didi

algorithm - 在最坏的情况下二分查找是最优的吗?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:29:20 26 4
gpt4 key购买 nike

二分查找在最坏情况下是最优的吗?我的老师是这么说的,但我找不到一本书来支持它。我们从一个有序数组开始,在最坏的情况下(该算法的最坏情况),任何算法总是比二分查找需要更多的成对比较

很多人说问题不清楚。对不起!所以输入是任何一般的排序数组。我正在寻找一个证明,证明任何搜索算法在最坏情况下(考虑算法的最坏情况)至少需要 log2(N) 次比较。

最佳答案

是的,二分查找是最优的。

通过诉诸信息论很容易看出这一点。它仅需要 log N 位来识别 N 元素中的唯一元素。但是每次比较只会给你一点信息。因此,您必须执行 log N 比较来识别唯一元素。

更详细...考虑一个假设的算法 X,它在最坏的情况下优于二进制搜索。对于数组的特定元素,运行算法并记录它提出的问题;即,它执行的比较顺序。或者更确切地说,记录这些问题的答案(例如“真、假、假、真”)。

将该序列转换为二进制字符串 (1,0,0,1)。将此二进制字符串称为“关于算法 X 的元素签名”。对数组的每个元素执行此操作,为每个元素分配一个“签名”。

现在是关键。如果两个元素具有相同的签名,则算法 X 无法区分它们!算法对数组的所有了解都是从它提出的问题中得到的答案;即,它执行的比较。如果算法不能区分两个元素,那么它就不可能是正确的。 (换句话说,如果两个元素具有相同的签名,这意味着它们导致算法进行相同的比较序列,那么算法返回的是哪一个?矛盾。)

最后,证明如果每个签名的位数少于log N,则必须存在两个具有相同签名的元素(鸽眼原理)。完成。

[更新]

一个快速的补充评论。上面假设算法除了从执行比较中学到的知识外,对数组一无所知。当然,在现实生活中,有时您确实先验 对数组有所了解。作为一个玩具示例,如果我知道数组有(比方说)10 个元素,都在 1 到 100 之间,并且它们是不同的,并且数字 92 到 100 都存在于数组中......那么显然我不知道即使在最坏的情况下也需要进行四次比较。

更现实地说,如果我知道元素在它们的最小值和最大值之间均匀分布(或大致均匀分布),我同样可以比二分查找做得更好。

但在一般情况下,二分查找仍然是最优的。

关于algorithm - 在最坏的情况下二分查找是最优的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7578709/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com