常见查找算法有哪些?

10 | 问答知识库用户 |浏览300次
收藏|2014/05/17 22:00
Delphi里怎么样快速查找一个关键字的位置呢?
常见的查找算法有哪些?

满意回答

2014/05/18 22:04

一、静态查找表:

1. 顺序查找,平均查找长度为:(n+1)/2

2. 有序表的查找之折半查找:前提必须是有序表,性能只有在均匀分布的时候才是最优的。

平均查找长度:log2(n+1)-1

当有概率涉及的查找中,将概率高的放在根节点上可以加快查找速度。

3. 索引表:建立两层表,第一层采用顺序记录,第二层分块随机排放,查找时第一层使用折半查找,第二层使用顺序查找。

log2(n/s+1)+(s+1)/2,其中s为每个块内固定的元素个素,每组都能选出一个最大的。

二、动态查找表

二叉排序树查找:通过一系列的查找和插入过程形成的树。之所以叫做排序树,因为按照中序遍历可得一个有序的序列。

二叉排序树的删除是一个性能瓶颈问题。

树排序的最坏情况是单支树。这时的查找长度是(n+1)/2。和顺序查找相同。

在随机情况下,二叉排序树的平均查找长度是和log2n等数量级的。

平衡二叉树:用来平衡二叉排序树的,当二叉排序树的左右子树的差值的绝对值大于1是就需要平衡。

平衡的二叉树才是真正的log2n数量级的!

三、B-树和B+树

B-树常用于文件系统中。

B+树:区别于B-树,有n棵子树的节点中含有n个关键字。叶子节点按序自动排列。B+树可以按序查找也可以从根结点开始随机查找。

热心网友

其他回答(0)
0人关注该问题
待解决问题



+1
 加载中...