没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全查找算法1

查找算法1

需积分: 0 0 下载量 72 浏览量 2022-08-08 23:13:12 上传评论收藏 116KB DOCX 举报

温馨提示

试读

13页

（2）查找时间复杂度：查找时（查找也是一个算法），需要记录执行代码需要的时间（可以理解为执行多少行代码），而这个执行需要的时间，就是算法的时间复杂度（4）命中

资源详情

资源评论

资源推荐

查找算法

基本概念：

（1）关键字：假如有结构

struct Node //一个结点，存储数据和指针

{

DATA data; //数据属性，用于存储数据

int key; //假设 key 为 int 值，其在整个表里是唯一的

//指针域，具体略，指向其他结点，或者是数组的下标

};

key 值便是关键字，对于每一个结点而言，其 key 值都是不一样的（不一定

必须是 int 值）。因此，当我们查找数据时，只要知道其 key 值，然后对比 key 值

和我们要查找的 key 值是否相同，便能判断是否是我们要查找的数据了。

优点：①数据属性的被更改，不影响查找，而且 key 值通常是不会被更改的；

缺点：①需要更多的空间用于存储 key 值；

（2）查找时间复杂度：

查找时（查找也是一个算法），需要记录执行代码需要的时间（可以理解为

执行多少行代码），而这个执行需要的时间，就是算法的时间复杂度。当数据量

为 n 时，记作 T(n)=O（f(n)），f(n)表示数据量为 n 时的某个函数。

而 O（f(n)）指的是，这个函数在数据量为 n 时，算法的时间复杂度。

他表示随问题规模 n 的增大，算法执行的时间的增长率。这样用大写 O（）

来体现算法复杂度的记法，称为大 O 记法。

一般关心的是大 O 记法的平均时间，和最坏结果的时间。

其常见的几种情况是：

①假如无论数据多少，其查找时间都是一个常数，那么记为 O（1），表示是

常数；

②假如是对数型增长（数据每增长一倍，次数增加 1 次），记为 O（log n），

表示对数；

③假如是线性增长，记为 O（n）。

④假如是乘方增长（和数据量的关系是乘方关系），记为 O（n

）

（3）查找表和查找

查找表：同一个类型的数据的集合（例如树中的结点是同一个类型，树中结

点的集合就是一个查找表）。

查找：根据某个值（key），在查找表中确定一个项（比如树中的一个结点，

比如说得到指向这个结点的指针）。

（4）命中

可以理解为查找到自己要查找的项了。

顺序查找（线性查找）：

（1）适用情况：

绝大多数情况。

（2）原理：

从第一个开始查找，并依次尝试进行匹配，一直到查找到符合要求的值，或

者是最后一个项为止。

（3）算法最佳适用情况：

①数据库较小；

②对时间没有苛刻要求。

（4）算法时间复杂度：

O（n）

二分法查找：

（1）适用情况：

前提：key 是有序的，并且表中顺序由 key 规定，且一般不变（如果变的话

需要重新对表排序）。

（2）原理：

先找查找表中最中间的结点 m，然后比较 m 的 key 值和要查找的 key 值的关

系，如果比 m.key 值大，则找 m 右边的（范围比之前缩小一半）。如果比 m.key

值小，则找 m 左边的（范围依然比之前缩小一半）。如果和 m.key 值一样大，则

命中。

如代码：

Node* find(int last, int key,Node *a) //这里适用的是数组型，a 指的是指向结点数组的指针

{

int f, l, m;

f = 0;

l = last;

while (f <= l) //只要范围左限的下标比右限的下标小即可

{

m = (f + l) / 2;

if (key < a[m].key) //如果比中间结点的 key 值小

l = m - 1; //比中间值小 1（也是出现新范围）

else if (key>a[m].key) //比中间结点的 key 值大

f = m + 1;

else

return a; //命中

}

return NULL; //说明没命中，返回空指针

剩余12页未读，继续阅读

内容反馈

坑货两只

粉丝: 65
资源: 290

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

查找算法1

评论0

最新资源

查找算法1

评论0

第8章查找算法1

排序和查找算法速度排序和查找算法速度

3种查找算法——数据结构实验

数据结构查找算法实验报告.doc

DSAinC++11-查找算法1

二分查找算法

静态查找表。实现有序表的折半查找算法

二分查找算法PPT课件

查找算法的比较

几种常用查找算法的比较

区间表的快速查找算法

二叉 递归二叉查找算法

常用排序查找算法详解

Java排序算法和查找算法

用c语言设计查找算法

查找算法ppt哈工大

java 几种查找算法

折半查找算法的改进和程序实现

十大算法之线性查找算法

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

全面的安全基线核查清单

OpenVAS离线资源

最新资源

二叉递归二叉查找算法