gpt4 book ai didi

algorithm - 在排序数组中搜索比二进制搜索复杂度低

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

为了搜索一个非常大的数组,我正在考虑一个复杂度小于 log n 的算法,这意味着不是阶数小于 log n,而是绝对小于 log n。所以我所做的是而不是去中间向前移动 1 步并检查如果数字均匀分布我们必须进一步移动多少,移动到该位置,如果这是解决方案则打破它否则计算我们必须进一步移动多少,迭代执行直到找到解决方案这是一个有效的 Java 代码:-

 public class Search {
public static void main(String[] args) {
int a[]={12,15,16,17,19,20,26,27};
int required=27;
int pointer=0;
int n=1;
int diff;
int count=0;
int length=a.length;
while(a[pointer]!=required){
count++;
if ((pointer+n)>(length-1))
n=length-1-pointer;
if(n==0)
n=-1;
diff=a[pointer+n]-a[pointer];
pointer=pointer+n;
n=(required-a[pointer])*n/diff;


}
System.out.println(pointer);
System.out.println(count);
}

}

P.S- 我有一个接近均匀分布的数组。

我想问一下它真的比二分查找好吗??在什么情况下它会失败?什么是最好的,平均的和最坏的情况复杂度??

最佳答案

您正在使用启发式方法来尝试加速排序。启发式就像猜测。不能保证它是正确的 - 但如果启发式是好的,则可以在一般情况下加速算法。

启发式算法通常不会改善算法在最坏情况下的运行时间。也就是说 - 启发式的某些输入可能是错误的。

我可以看到您正在做的事情的直观吸引力 - 您正在“搜索”更接近您认为目标的位置。

但是你的做法有两个问题:

  1. 将二分搜索中的“拆分”移近目标并不会加快搜索速度。在二进制搜索中,每次将搜索空间分成两半。当你将分割点移近目标时,你还没有找到目标,你的目标很可能在两个不相等空间中较大的一个。

例如,假设您有以下数组。 y 是您的目标,x 是所有其他值:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx

在二分搜索中,您会在前两个决定中将空间分成两半,然后再分成两半:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
^ ^

经过两次决定后,您的 32 值数组缩小到 8 个值的搜索空间。但是假设根据您的启发式,在第二个选择之后您将拆分放在 y 之后?

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
^ ^

在您做出第二个决定后,您只稍微缩小了搜索空间。通过添加此启发式算法,您已将最坏情况下的运行时间减少到 N - 因为可以构造输入,让您的启发式算法每次都做出最坏的猜测。

  1. 另一个问题是,加速搜索的启发式方法只有在您对所搜索的内容有所了解时才有用。以字典搜索为例。你知道 z 在字母表的末尾。所以当你得到一个以 z 开头的单词时,你就很清楚 z 单词在字典中的位置。您不必从字典的中间开始。

这是因为您对字典中单词的分布有所了解。但是,如果有人不能保证列表中的单词——那么你就不能保证字典搜索更快——例如,你可能会收到一个包含所有 z 个单词的列表。

在你的情况下,你的启发式并不是特别好。您猜测下一次拆分的位置基于当前拆分与先前值之间的距离。唯一一个好的猜测是列表中的元素是否均匀分布。如果它们间隔不均匀(几乎总是),那么一些猜测总是会超过 split 和其他下冲。

在任何非均匀间隔数字的排序数组中,必然存在比平均间隔更紧密的间隔,以及比平均间隔更稀疏的间隔。您的启发式猜测当前拆分到数组末尾的数字的平均稀疏性。这两件事之间没有关系。

更新:

您的最佳案例时间:O(1) - 例如你马上就猜到了索引。

最坏情况:O(N) - 例如每一个选择都是最糟糕的。

您补充说您的阵列几乎均匀分布并且非常大。我猜测实际上什么是最快的:查找数组中的第一个数字和最后一个数字,以及数组的长度。对目标的偏移量进行有根据的猜测:

offset = floor((( target - first ) / ( last - first )) * length );

在目标周围选择一个合理的搜索空间:

window_start = floor( offset * ( 1 - alpha ));
window_end = floor( offset * ( 1 + alpha ));

对该窗口定义的子数组进行二分查找。

将 alpha 设置为多少取决于您认为数组的规律性。例如。您可以将 设置为 0.05 以搜索大约占估计目标周围总搜索空间 10% 的窗口。

如果您可以对输入的均匀性做出一些保证,您也许可以优化调整 alpha。

关于algorithm - 在排序数组中搜索比二进制搜索复杂度低,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26585931/

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