首页 > 试题广场 >

在有序表中，关于斐波那契查找和折半查找说法错误的是（）

[不定项选择题]

就平均性能而言，斐波那契查找的平均性能比折半查找差

只有有序表中元素个数n等于某个斐波那契数时才能用斐波那契查找算法

在最坏情况下，斐波那契查找的性能比折半查找好

```
折半查找时间复杂度为O(log2n)
```

查看正确选项

UnnnnnnU

我认为这道题目说错了因该是问的是正确的是: D

首先 A：平均性能是斐波纳切黄金分割查找更好

B：有序表长度不需要一定要是一个斐波纳切数才行，是可以补齐成为一个斐波纳切数的补最大的数目直到长度是斐波纳切数

C：最坏情况下斐波纳切查找性能比折半是要差的

这些在书上都有的

这是我认为的

发表于 2019-08-29 20:10:30 回复(0)

learner111111

斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。

斐波那契搜索也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

发表于 2018-12-24 17:58:34 回复(0)