当前位置:首页 » 数据结构精品文章 » 正文

查找相关术语

1522 人参与  2018年09月03日 22:44  分类 : 数据结构精品文章  评论

1、静态查找表相关概念

数据对象:同类元素集,具可识别比较的关键字

存储结构:查找表采用顺序,记录按逻辑顺序存放

查找方法:逐个比较表中的各个记录的关键字

2、顺序表等几率查找的算法思想和性能分析。

对数据元素按顺序存储结构存储的查找。

算法思想:

image.png 

算法:

设哨兵,保证可以停下来,提高效率。

此算法最简单直观,但显示出查找最基本的要做的事。

原始算法: 

image.png


静态查找——查找表的内容不变

动态查找——查找表的内容受插入,删除的影响。

性能分析(同类好坏评比用数据论说)

时间/空间r[0..n],i=n+2

时间复杂性:时间主要耗于何处?看算法主要工作量干了些什么?

image.png

平均查找长度ASL

查找成功时的=n+1/2

查找不成功时的= n+1

查找算法平均查找长度=n+1*3/4

平均查找长度ASL 查找所需要比较次数的期望值

n记录的表,成功查找的image.png;不成功,n+1次。

pi要查元素处于第i位的几率。

cii元素时已做比较次数。

image.png

设要查元素位于何处是等几率的,即

3、顺序表查找结论

优点 简单,要求低,附加空间少,方法直截了当、适应面广;

缺点 等几率不科学。

从头做起太呆板。对已有序的key,不能利用。费时。

适于 无序、简单、小表情况;

可用于数组,链表表示的线性表、分类/分类的均可用。

改进 成功率高的元素置放位置前提。

改步长,大踏步快点。

4、有序表折半查找的思想和性能分析

有序表:静态查找表中,各个记录按关键字大小顺序排列。

当表中key已有序的情况下顺序法不够聪明

折半查找法:通过与中间位置上的元素进行比较,每次确定待查记录的所在范围,将比较元素的范围缩小一半,逐次比较直到找到或找不到该记录为止。

image.png 

例:李咏“幸运52”猜价格1000~120011801,3,5,7,9key=7,顺序4次,折半2次。

性能分析 

查找过程可以借助二叉树(称为判定二叉树)来描述,分析

构造判定二叉树:以中间元素为例,所有小于中间元素的数据组成左子树,大于中间元素的数据组成右子树。

513,19,21,37,56,64,75,80,88,92

image.png 

内结点:成功查找,在树中

外结点:不成功查找,不在树中。

查找记录的过程恰好走了一条从根到该结点的路径,比较次数=路径上的结点数=此结点所在的层数。


来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=201

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!