结构推理
顺序检索时间为O(n),二分法检索时间为O(log2n),散列检索时间为O(1)。为什么有了高效率的检索方法而低效率的方法并未被淘汰?
【正确答案】(1)不同检索方法有各自的适用条件,需要依赖于不同的存储结构。
顺序检索需要顺序存储或者链接存储;二分法检索需要顺序存储并且排序;散列检索需要散列存储。
这说明不同的检索算法需要不同的空间开销。例如,散列表能提高检索的效率,但也付出了较大的空间代价。如果系统的空间资源不允许用这样的空间开销来换取时间的效率,系统就不能采用散列的结构存储数据了。
(2)存储结构的选择不能仅依赖于检索的效率,而要综合考虑各种操作的综合效率。
例如,虽然二分检索法平均效率较高,但在排序的顺序表中做插入和删除的操作需要花费许多时间来保证排序,因而不适用于经常做插入和删除操作的结构。
(3)高效的算法通常结构比较复杂,并且只有在问题规模比较大时才能体现其效率。顺序检索虽然效率不高,但是算法简单,在n较小时,特别是当字典元素以查找效率高低的顺序排列时,效率可能会比某些高效率的算法还要高。
【答案解析】