查找算法的简单总结.docx
- 文档编号:14720486
- 上传时间:2023-06-26
- 格式:DOCX
- 页数:8
- 大小:23.34KB
查找算法的简单总结.docx
《查找算法的简单总结.docx》由会员分享,可在线阅读,更多相关《查找算法的简单总结.docx(8页珍藏版)》请在冰点文库上搜索。
查找算法的简单总结
查找算法的简单总结
查找算法的简单总结一、顺序查找条件:
无序或有序队列。
原理:
按顺序比较每个元素,直到找到关键字为止。
时间复杂度:
O二、二分查找条件:
有序数组原理:
查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空,则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度:
O三、二叉排序树查找条件:
先创建二叉排序树:
1.若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;2.若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;3.它的左、右子树也分别为二叉排序树。
原理:
在二叉查找树b中查找x的过程为:
1.若b是空树,则搜索失败,否则:
2.若x等于b的根节点的数据域之值,则查找成功;否则:
3.若x小于b的根节点的数据域之值,则搜索左子树;否则:
4.查找右子树。
时间复杂度:
四、哈希表法条件:
先创建哈希表原理:
根据键值方式进行查找,通过散列函数,定位数据元素。
时间复杂度:
几乎是O,取决于产生冲突的多少。
五、分块查找原理:
将n个数据元素按块有序划分为m块。
每一块中的结点不必有序,但块与块之间必须按块有序;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,。
然后使用二分查找及顺序查找。
递归与分治策略...............................................................................................................................1.递归..............................................................................................................................2.递归函数......................................................................................................................3.阶乘函数........................................................................................................................4.斐波那契数列..............................................................................................................5.整数划分......................................................................................................................6.分治法..........................................................................................................................7.大整数的乘法..............................................................................................................8.矩阵乘..........................................................................................................................9.合并排序........................................................................................................................10.棋盘覆盖....................................................................................................................11.循环赛日程表..............................................................................................................12.快速排序......................................................................................................................13.贪心算法....................................................................................................................14.贪心算法基本要素....................................................................................................15.活动安排问题............................................................................................................1016.0-1背包问题与背包问题.........................................................................................110-1背包问题..................................................................................................................110-1背包问题改进算法..................................................................................................1117.最优装载..................................................................................................................1118.单源最短路径............................................................................................................1219.Dijkstra算法..............................................................................................................1320.最小生成树..............................................................................................................1321.多机调度算法............................................................................................................1722.备忘录方法..............................................................................................................1724.凸多边形最优三角剖分..........................................................................................1825.长公共子序列............................................................................................................1926.多边性游戏................................................................................................................027.二分搜索技术............................................................................................................1递归与分治策略1.递归递归,就是在运行的过程中调用自己。
构成递归需具备的条件:
函数嵌套调用过程示例1.子问题须与原始问题为同样的事,且更为简单;2.不能无限制地调用本身,须有个出口,化简为非递归状况处理。
在数学和计算机科学中,递归指由一种简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。
例如,下列为某人祖先的递归定义:
某人的双亲是他的祖先。
某人祖先的双亲同样是某人的祖先。
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:
1、1、2、3、5、8、13、21.....I[1]斐波纳契数列是典型的递归案例:
2.递归函数递归方法汉诺塔3.阶乘函数下面是求10的阶乘,你参考下:
voidmain{intfn=1,i=1;intn=10;//下面就是求10的阶乘for{fn=fn*i;}printf;}4.斐波那契数列即定义两个数字,后面的数字是前两个数字之和a1=1,a=1,a=,......an=an-1+an-2斐波那契数列很有趣,每一个数都是整型数,可是它的通项公式却由无理数进行表达。
斐波那契数列的通用表达是:
第一个数和第二个数是1,从第三个数开始,每一个数都是它的前两个数的和。
a1=1,a=1,a=,......an=an-1+an-2,用C言代码可以实现第几个斐波那契数。
5.整数划分◎根据n和m的关系,考虑以下几种情况:
其中n为要划分的正整数,m是划分中的最大加数1.当n=1时,不论m的值为多少的m划分,因此这种划分个数为f;划分中不包含m的情况,则划分中所有值都比m小,即n的划分,个数为f;因此f=f+f;综合以上情况,我们可以看出,上面的结论具有递归定义特征,其中和属于回归条件,和属于特殊情况,将会转换为情况。
而情况为通用情况,属于递推的方法,其本质主要是通过减小m以达到回归条件,从而解决问题。
其递推表达式如下:
f=1;?
f=f;?
1+f;?
f+f;?
6.分治法分治法在每一层递归上都有三个步骤:
分解:
将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;解决:
若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;合并:
将各个子问题的解合并为原问题的解。
分治策略的例子:
合并排序,快速排序,折半查找,二叉遍历树及其相关特性。
7.大整数的乘法设X和Y都是n位的二进制整数,现在要计算它们的乘积XY。
我们可以用小学所学的方法来设计一个计算乘积XY的算法,但是这样做计算步骤太多,显得效率较低。
如果将每2个1位数的乘法或加法看作一步运算,那么这种方法要作O步运算才能求出乘积XY。
下面我们用分治法来设计一个更有效的大整数乘积算法。
x=|A|B|y=|C|D|图6-大整数X和Y的分段我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位,如图6-3所示。
由此,X=A2n/2+B,Y=C2n/2+D。
这样,X和Y的乘积为:
XY==AC2n+2n/2+BD如果按式计算XY,则我们必须进行4次n/2位整数的乘法,以及3次不超过n位的整数加法中的加号),此外还要做2次移位中乘2n和乘2n/2)。
所有这些加法和移位共用O步运算。
设T是2个n位整数相乘所需的运算总数,则由式,我们有:
T=1T=4T+O由此可得T=O。
因此,用式来计算X和Y的乘积并不比小学生的方法更有效。
要想改进算法的计算复杂性,必须减少乘法次数。
为此我们把XY写成另一种形式:
XY=AC2n+[+AC+BD]2n/2+BD虽然,式看起来比式复杂些,但它仅需做3次n/2位整数的乘法),6次加、减法和2次移位。
由此可得:
T=1T=3T+cn用解递归方程的套用公式法马上可得其解为T=O=O。
利用式,并考虑到X和Y的符号对结果的影响,我们给出大整数相乘的完整算法MULT如下:
functionMULT;{X和Y为2个小于2n的整数,返回结果为X和Y的乘积XY}经典包分类算法总结1RFC算法1.1RFC算法介绍RFC算法[1]是一种多维IP分类快速查找算法,通过对实际的过滤规则数据库的考察,发现数据库中的过滤规则都有内在的结构和冗余度,这个特点可以为分类算法所利用。
RFC算法的主要思想是将IP分类问题看成一个将包头中的S比特数据到T比特的classID的一个映射。
如果预先计算出包头中的这S位共2s种不同情况中每种情况所对应的classID值。
那么每一个包只需要一次查表,即一次内存访问就可以得到相应的classID,但是这样会消耗极大的空间。
RFC的思想是映射不是通过一步来完成,而是通过多个阶段完成,如图1.1所示。
每个阶段的结果是将一个较大的集合映射成一个较小的集合,称其为一次缩减。
RFC算法共分P个阶段,每个阶段由一些列的并行的查找组成。
每个查找的结果值比用于查找的索引值要短。
图1RFC的基本构思图一个四阶段的RFC缩减树图1.2中建立了一种4阶段的缩减树,对IP包查找过程如下:
1)在第一阶段,包头中的K个域被分成若干个块,每个块被用来作为并行查找的索引;2)在后面的几个阶段,每次查找内存的索引值都是由前几个阶段的查找结果合并而成的。
一种简单的合并办法就是将查找结果按二进制串连接起来,但还有更好的方法可以节省空间;3)在最后一个阶段,查找的结果得到一个值。
由于我们进行了预先的计算,这个值就是该包对应的classID。
1.RFC算法性能分析RFC算法受到两个参数的影响:
1)选取的阶段的数目P2)在给定P的情况下,缩减树的形状.也就是后面的阶段的索引值从前面哪几个阶段的查找结果进行合并。
在给定P的情况下,给出一种严格的判定方法来选择最优的缩减树很困难。
[1]中给出了两种启发性原则:
1)尽可能合并具有一定相关性的块。
如我们尽可能早的将同一个IP地址的两个块进行合并。
因为具有相关性的两个块往往在同一条规则或者在少数几个规则中集中出现。
尽早对其进行合并,可以避免后续合并产生不必要的扩展;2)在不引起内存激增的情况下.尽可能合并多的块。
在P和缩减树固定的情况下,随着过滤规则树N的增加,消耗的内存量也增加。
同时,对于同样的过滤规则数据库,P=3比P=4消耗更多的内存,但是查找速度前者比后者要快。
RFC算法的优点:
易于并行处理,处于同一阶段的预处理表和交叉乘积表可被并行地索引,处于不同阶段的表也可被并行的索引,这些表各自独立,处于不同的存储单元。
与其他算法相比,更适用于实际的网络中。
RFC算法的缺点:
缺乏一般性,因为它与分类器的结构有关,因此需要针对不同的分类器来进行微调才能达到理想中的最佳工作状态。
一般的解决方法是在算法设计时便留有许多的参数供日后设定,像在RFC算法中所需要的阶段数,每一阶段中所做的化简比例等都是可以在执行时期设定的。
Set-prunningtrie2.1HierarchicalTries分层查找树算法就是将分类字段的每一个维分成一层构造一个分层查找树,实际上就是对一维查找树的简单扩展,使用递归方式来生成分层查找树。
基本思想是:
设一个分类器C={Rj}有k个域,如果k1,开始构建第一维的查找树,将其称之为F1-trie,它所对应的是分类器中每一条规则第一个域的前缀集{Rjl}。
F1-trie中的每个结点表示一个前缀front,然后在front处进行递归构建一个维的分层查找树Tp。
前缀节点front使用下一级查找树的指针next指向下一级分层树Tp。
由表2.1的规则库得出的分层查找树如图2.1所示。
假设D是树中一个结点,如果D是D的前缀,一般称D是D的祖先。
如果D是D的最长前缀,则称D是D的最小祖先。
分类过程:
进入分类算法的IP报文D,分层查找树算法首先根据Dl在F1-trie树上进行遍历,从而找到Dl的一条最佳匹配前缀,记下最后一个匹配结点为Z,然后沿着下一级查找树的指针next继续遍历维的分层查找树,记录下这条路径上所有匹配的规则。
接着要回溯到Z的最小祖先Z,所谓的最小祖先就是指设Z是树中一个结点,如果Z是Z的最长前缀,则称Z是Z的最小祖先。
继续沿着Z的下一个查找树的指针next进行遍历,直到Z节点的所有祖先都被遍历一次为止。
最后,选择匹配规则中优先级最高的规则为进入分类报文的最佳匹配规则。
如图给出了二元组D的分层查找树,其中虚线表示整个查找的过程。
表2.1规则库实例算法基础题一、常见查找算方法总结1.基本概念数据:
数据即信息的载体,是对客观事物的符号表示,指能输入到计算机中并被计算机程序处理的符号的总称。
数据项:
数据项是数据具有独立意义的不可分割的最小单位,是对数据元素属性的描述。
数据元素:
数据元素是数据的基本单位,是对一个客观实体的数据描述。
查找表:
进行查找的数据元素通常是同一类型的数据元素或记录,由它们构成的集合称查找表。
查找:
查找也称检索,是根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。
若表中存在一个这样的记录,则称查找成功,反之查找失败。
2.查找分类2.1线查找1).顺序查找a.算法思想:
设查找表是由n个元素组成的,从第一个元素开始,顺序查找给定元素,若找到查找成功,反之失败。
b.算法实现:
intsearch{inti;ifreturn-1;//查找失败for{ifreturni;//查找成功}return-1;//查找失败}c.时间复杂度:
O2).折半查找//又称二分查找a.算法思想:
在有序表中,取中间元素作为比较对象,若给定元素与中间元素相等,则查找成功。
若给定元素小于中间元素,则在中间元素的左半区继续查找,若给定元素大于中间元素,则在中间元素右半区继续查找,不断重复上述查找过程。
b.算法实现:
intbinarySearch//查找序列必须有序{intlow,mid,high;ifreturn-1;//查找失败low=0;while{mid=/;ifreturnmid;//查找成功elseifhigh=mid-1;elselow=mid+1;}return-1;//查找失败}c.时间复杂度:
O3).分块查找//又称索引顺序查找,它是顺序查找的一种改进,是一种性能介于顺序查找和二分查找之间的查找方法。
a.算法思想:
将n个数据元素按块有序划分为m块。
每一块中的结点不必有序,但块与块之间必须按块有序,即前一块中任一元素的关键字都必须小于后一块中任一元素的关键字。
同时根据所有块建立一张索引表,索引表中每一项由关键字字段和指针字段组成。
查找分两个部分,先对索引表进行二分查找或顺序查找,以确定待查元素可能在哪一个块中,然后在已确定的块中顺序查找。
b.算法实现:
#include#include#defineB10#defineItypedefchardatatype;//块结点类型定义typedefstructBlockNode{intkey;//关键字域datatypedata;//其它域}blockList;//索引结点类型定义typedefstructIndexNode{intindexKey;//索引关键字域intindexNum;//指向块的第一个元素的下标}indexList;//分块查找intindexSearch{intlow,mid,high,start,end,j;low=0;while{//索引表的查找采用二分查找mid=/;ifhigh=mid-1;elselow=mid+1;}if{//二分查找完毕,low下标的索引项对应的块中可能存在待查找元素。
//确定块起始位置start=i[low].indexNum;//确定块终止位置if{//若带查找元素在最后一个块中end=m-1;}elseend=i[low+1].indexNum-1;//在块内顺序查找for{ifreturnj;//查找成功}}return-1;//查找失败}intmain{intr;blockListlist[B]={{8,a},{14,b},{6,c},{9,d},{10,e},{22,f},{34,g},
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 查找 算法 简单 总结