数据结构怎么使查找效率

Question

如题所述

Answer 1

顺序表查找算法 时间复杂度:O(N) 特点:优点,理解简单,代码写起来也简单;缺点,效率低。 利用下标遍历数组(或其他数据结构)即可,较简单。

顺序查找表算法-优化版 时间复杂度:O(N) 特点:与上一个一样。 主要就是在遍历时加上一个边界条件,之前的版本每次加1以后都要进行判断是否越界,然后再判断是否和输入值相等。

优化版可以减去判断越界这个条件。有序表查找（先排序）特点 ：优点，效率高，从时间复杂度就能看出来；缺点，前提需要有序表顺序存储。对于频繁插入和删除的数据集维护量可能过大。

一半一半的查找，知道这个原理，代码写起来不难，最主要一点是while的边界条件，因为二分，当low=high时还需要计算(low+high)/2 是否等于 find。

因为这个位置还没有比较过。插值查找，特点：优点，一般情况比二分更有效率。缺点，前提需要有序表顺序存储，对于频繁插入和删除的数据集维护量可能过大。

此外如果数据的分别是那种极端情况如{0，1，2，20000，2000001，...}，插值法可能效果也不好。斐波那契查找。

特点：优点，与二分折半相比，平均性能优于二分法。缺点，如果输入的值就在a1，效率比二分都要低。

利用索引查找，索引就是把一个关键字与它对应的记录相关联的过程。线性所以主要包括：稠密索引、分块索引、倒排索引。

这里基本不会写什么代码，因为是索引对应的，把之前的数据封装下就可以，所以面试笔试，问的可能性不大。这块有点偏向数据库，所以如果面试问到也是直接问数据库的问题。