是斐波纳契搜索比二进制搜索速度更快？ [英] Is fibonacci search faster than binary search?

问题描述

我看了一些材料，声称斐波那契搜索是比平均二进制搜索速度更快，主要的原因是它只涉及加法和减法，而不是除以2。

我有一些问题：

1.Is斐波搜索比二进制搜索更快，不考虑到运算速度ω作为步骤二进制搜索取较少。

2，除以2可以通过位来实现 - ？移位操作，是不是真的比另外慢

3.什么是斐波那契搜索的优势与二进制搜索比较？

解决方案

  

时的斐波那契数比搜索二进制搜索速度更快，而不考虑   运行速度？作为步骤二分查找取少。

这要看，底层的存储系统就行了。例如 - 想一个磁盘。它是非常便宜，以寻找在相同的$ P $的汽缸的位置pviously读1 - 因为读取臂不必移动。所以，如果您的阅读更接近对方 - 你更有可能需要移动阅读胳膊少 - 所以每次的预期时间磁盘寻求更短。此外，移动整个气缸少读臂同样快于跨多个气缸移动它

在这个例子：

有便宜得多，从移动读臂（1）至（2）比它从（1）至（3）。并且由于（2）是接近（在地址术语），然后（3），更短的跳跃更可能是此类别中。 [由式（1）至（2）阅读手臂不会动弹，只会让磁盘旋转，直到达到它]

  

2的划分可以通过位来实现 - 移位操作，是不是真的   比另外慢？

这主要是硬件（和编译器优化）的问题。我无法想象任何理由制造业不会做出这样的优化，和位移在大多数实现我所知道的是尽可能快地增加。

  

什么是斐波那契搜索的优势与二进制搜索比较？

如上文（1） - 连续的磁盘之间的距离更短的结果的目的在更短的（预期）寻道时间

I read some materials that claims Fibonacci search is faster than binary search on average,and the main cause is "it involves only addition and subtraction,not division by 2".

I have some questions:

1.Is Fibonacci search faster than binary search without regard to the operational speed?As the steps binary search take are less.

2.The division by 2 can be done by bit - shift operation,is it really slower than addition?

3.What's the advantage of Fibonacci search compared with binary search?

解决方案

Is Fibonacci search faster than binary search without regard to the operational speed?As the steps binary search take are less.

It depends, on the underlying storage system for the list. For example - think of a disk. It is much 'cheaper' to look for a location in the same cylinder of the previously read one - since the reading arm does not have to move. So, if your reads are much closer to each other - you are more likely to need to move the reading arm less - so the expected time of each disk-seek is shorter. Also, to move the reading arm across less cylinders is similarly faster than moving it across more cylinders

In the example:

It is much cheaper to move the reading arm from (1) to (2) than it is from (1) to (3). And since (2) is 'closer' (in term of addresses) then (3), shorter jumps are more likely to be in this category. [From (1) to (2) the reading arm won't move at all, it will only let the disk spin until it reaches it]

The division by 2 can be done by bit - shift operation,is it really slower than addition?

This is mainly a hardware (and compiler optimization) issue. I cannot imagine any reason why a manufacture won't make this optimization, and bit-shift in most implementation I am aware of is as fast as additions.

What's the advantage of Fibonacci search compared with binary search?

As mentioned in (1) - shorter distance between consecutive disk seeks results in shorter (expected) seek times.

这篇关于是斐波纳契搜索比二进制搜索速度更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！