查找算法的简单总结

1 / 42 查找算法的简单总结 五种查找算法总结 一、顺序查找 条件：无序或有序队列。 原理：按顺序比较每个元素，直到找到关键字为止。 时间复杂度： O(n) 二、二分查找 条件：有序数组 原理：查找过程从数组的中间元素开始 ，如果中间元素正好是要查找的元素，则搜素过程结束； 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空，则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。 2 / 42 时间复杂度： O(logn) 三、二叉排序树查找 条件：先创建二叉排序树： 1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 它的左、右子树也分别为二叉排序树。 原理： 在二叉查找树 b中查找 x 的过程为： 1. 若 b是空树，则搜索失败，否则： 2. 若 x等于 b的根节点的数据域之值，则查找成功；否则： 3. 若 x 小于 b 的根 节点的数据域之值，则搜索左子树；否则： 3 / 42 4. 查找右子树。 时间复杂度： 四、哈希表法 条件：先创建哈希表 原理：根据键值方式 (Key value)进行查找，通过散列函数，定位数据元素。 时间复杂度：几乎是 O(1)，取决于产生冲突的多少。 五、分块查找 原理：将 n个数据元素 按块有序 划分为 m块。 每一块中的结点不必有序，但块与块之间必须 按块有序 ；即第 1块中任一元素的关键字都必须小于第 2块中任一元素的关键字； 而第 2 块中任一元素又都必须小于第 3 块中的任一元素， 。 4 / 42 然后使用二分查找及顺序查找。 递 归 与 分 治 策略 . 2 1. 递归 . 2 2. 递归函数 . 2 3. 阶乘函数 . 3 5 / 42 4. 斐 波 那 契 数列 . 3 5. 整数划分 . 3 6. 分治法 . 4 7. 大 整 数 的 乘法 . 5 8. 矩阵乘 .6 / 42 . 6 9. 合并排序 . 7 10. 棋盘覆盖 . 8 11. 循 环 赛 日 程表 . 8 12. 快速排序 . 9 7 / 42 13. 贪心算法 . 9 14. 贪 心 算 法 基 本 要素 . 9 15. 活 动 安 排 问题 . 10 背 包 问 题 与 背 包 问题 . 11 0-1 背包问题 .8 / 42 . 11 0-1 背 包 问 题 改 进 算法 . 11 17. 最优装载 . 11 18. 单 源 最 短 路径 . 12 19. Dijkstra 算法 . 13 9 / 42 20. 最小生成树 . 13 21. 多 机 调 度 算法 . 17 22. 备忘录方法 . 17 24. 凸多边形最优三角剖分 . 18 25. 长 公 共 子 序列 .10 / 42 . 19 26. 多 边 性 游戏 . 20 27. 二 分 搜 索 技术 . 21 递归与分治策略 1.递归 递归，就是在运行的过程中调用自己。 构成递归需具备的条件： 函数嵌套调用过程示例 11 / 42 1. 子问题须与原始问题为同样的事，且更为简单； 2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。 在数学和计算机科学中，递归指由一种简单的基本情况定义的一类对象或方法，并规 定其他所有情况都能被还原为其基本情况。 例如，下列为某人祖先的递归定义： 某人的双亲是他的祖先。某人祖先的双亲同样是某人的祖先。斐波纳契数列，又称黄金分割数列，指的是这样一个数列： 1、 1、 2、 3、 5、 8、 13、 21. I1 斐波纳契数列是典型的递归案例： 2.递归函数 递归方法 汉诺塔 12 / 42 3.阶乘函数 下面是 求 10的阶乘，你参考下： void main int fn =1， i=1; int n = 10; /下面就是求 10的阶乘 for(i=1;i fn = fn * i; printf(10的阶乘 是 %d,fn); 13 / 42 4.斐波那契数列 即定义两个数字，后面的数字是前两个数字之和 a1 = 1， a2 = 1， a3 = 2， . an = an-1 +an-2(n=3) 斐波那契数列很有趣，每一个数都是整型数，可是它的通项公式却由无理数进行表达。斐波那契数列的通用表达是：第一个数和第二个数是 1，从第三个数开始，每一个数都是它的前两 个数的和。 a1 = 1， a2 = 1， a3 = 2， . an = an-1 +an-2(n=3),用 C 言代码可以实现第几个斐波那契数。 5.整数划分 根据 n 和 m 的关系，考虑以下几种情况： 其中 n为要划分的正整数， m是划分中的最大加数 1. 当 n=1 时，不论 m 的值为多少的 m 划分，因此这种划分个数为 f(n-m, m); (2) 划分中不包含 m 的情况，则划分中所有值都比 m 小，即n 的 (m-1)划分，个数为 f(n,m-1);因此 f(n, m) = f(n-m, 14 / 42 m)+f(n,m-1); 综合以上情况，我们可以看出，上面的结论具有递归定义特征，其中和属于回归条件，和属于特殊情况，将会转换为情况。而情况为通用情况，属于递推的方法，其本质主要是通过减小 m 以达到回归条件，从而解决问题。其递推表达式如下： f(n, m)= 1; (n=1 or m=1) ? f(n, m)=f(n, n); (n ? 1+ f(n, m-1); (n=m) ? f(n-m,m)+f(n,m-1); (nm) ? 6.分治法 分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 15 / 42 合并：将各个子问题的解合并为原问题的解。 分治策略的例子：合并排序，快速排序，折半查找，二叉遍历树及其相关特性。 7.大整数的乘法 设 X和 Y都是 n位的二进制整数，现在要计算它们的乘积 XY。我们可以用小学所学的方法来设计一个计算乘积 XY的算法，但是这样 做计算步骤太多，显得效率较低。如果将每 2 个 1位数的乘法或加法看作一步运算，那么这种方法要作 O(n2)步运算才能求出乘积 XY。下面我们用分治法来设计一个更有效的大整数乘积算法。 x = |A|B| y=|C|D| 图 6-3 大整数 X和 Y 的分段 我们将 n位的二进制整数 X和 Y各分为 2段，每段的长为 n/2位 (为简单起见，假设 n 是 2的幂 )，如图 6-3所示。 由此， X=A2n/2+B ， Y=C2n/2+D。这样， X 和 Y的乘积为： 16 / 42 XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1) 如果按式 (1)计算 XY，则我们必须进行 4 次 n/2 位整数的乘法 (AC， AD， BC和 BD)， 以及 3 次不超过 n 位的整数加法 (分别对应于式 (1)中的加号 )，此外还要做 2 次移位 (分别对应于式 (1)中乘 2n 和乘2n/2)。所有这些加法和移位共用 O(n)步运算。设 T(n)是 2个 n 位整数相乘所需的运算总数，则由式 (1)，我们有 : T(1)=1 T(n)=4T(n/2)+O(n) (2) 由此可得 T(n)=O(n2)。因此，用 (1)式来计算 X 和 Y 的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把 XY 写成另一种形式 : XY=AC2n+(A-B)(D-C)+AC+BD2n/2+BD (3) 17 / 42 虽然，式 (3)看起来比式 (1)复杂些，但它仅需做 3次 n/2位整数的乘法 (AC， BD和 (A-B)(D-C)， 6次加、减法和 2 次移位。由此可得 : T(1)=1 T(n)=3T(n/2)+cn (4) 用 解 递 归 方 程 的 套 用 公 式 法 马 上 可 得 其 解 为T(n)=O(nlog3)=O()。利用式 (3)，并考虑到 X和 Y的符号对结果的影响，我们给出大整数相乘的完整算法 MULT 如下 : function MULT(X， Y， n); X 和 Y 为 2 个小 于 2n 的整数，返回结果为 X 和 Y 的乘积 XY 经典包分类算法总 结 1 RFC算法 18 / 42 RFC算法介绍 RFC(Recursive Flow Classification)算法 1是一种多维IP 分类快速查找算法，通过对实际的过滤规则数 据库的考察，发现数据库中的过滤规则都有内在的结构和冗余度，这个特点可以为分类算法所利用。 RFC 算法的主要思想是将IP 分类问题看成一个将包头中的 S 比特数据到 T 比特的classID的一个映射。如果预先计算出包头中的这 S 位共 2s种不同情况中每种情况所对应的 classID值。那么每一个包只需要一次查表，即一次内存访问就可以得到相应的classID,但是这样会消耗极大的空间。 RFC 的思想是映射不是通过一步来完成，而是通过多个阶段完成，如图所示。每个阶段的结果是将一个较大的集合映射成一个较小的集合，称其为一次缩减。 RFC 算法共分 P 个阶段，每个阶段由一些列的并行的查找组成。每个查找的结果值比用于查找的索引值要短。 图 1 RFC 的基本构思 图 2 一个四阶段的 RFC缩减树 19 / 42 图中建立了一种 4 阶段的缩减树，对 IP包查找过程如下： 1）在第一阶段，包头中的 K个域被分成若干个块 (chunks)，每个块被用来作为并行查找的索引； 2）在后面的几个阶段，每次查找内存的索引值都是由前几个阶段的查找结果合并而成的。一种简单的合并办法就是将查找结果按二进制串连接 起来，但还有更好的方法可以节省空间； 3）在最后一个阶段，查找的结果得到一个值。由于我们进行了预先的计算，这个值就是该包对应的 classID。 RFC算法性能分析 RFC 算法受到两个参数的影响： 1）选取的阶段的数目 P 2）在给定 P 的情况下 ,缩减 树的形状 .也就是后面的阶段的索引值从前面哪几个阶段的查找结果进行合并。 20 / 42 在给定 P 的情况下 ,给出一种严格的判定方法来选择最优的缩减树很困难。 1中给出了两种启发性原则： 1)尽可能合并具有一定 “ 相关性 ” 的块。如我们尽可能早的将同一个 IP 地址的两个块进行合并。因为具有 “ 相关性 ”的两个块往往在同一条规则或者在少数几个规则中集中出现。尽早对其进行合并，可以避免后续合并产生不必要的扩展； 2)在不引起内存激增的情况下 .尽可能合并多的块。 在 P 和缩减树固定的情况下，随着过滤规则树 N的增加，消耗的内存量也增加。同时，对于同样的过滤规则数据库， P=3比 P=4消耗更多的内存，但是查找速度前者比后者要快。 RFC算法的优点： (1)易于并行处理，处于同一阶段的预处理表 和 交叉乘积表可被并行地索引，处于不同阶段的表也可被并行的索引，这些表各自独立，处于不同的存储单元。 (2)与其他算法相比，更适用于实际的网络中。 21 / 42 RFC算法的缺点：缺乏一般性， 因为它与分类器的结构有关，因此需要针对不同的分类器来进行微调 (tuning)才能达到理想中的最佳工作状态。一般的解决方法是在算法设计时便留有许多的参数供日后设定，像在 RFC算法中所需要的阶段数，每一阶段中所做的化简比例等都是可以在执行时期设定的。 2 Set-prunning trie Hierarchical Tries 分层查找树算法就是将分类字段的每一个维分成一层构造一个分层查找树，实际上就是对一维查找树的简单扩展，使用递归方式来生成分层查找树。基本思想是：设一个分类器C=Rj有 k 个域，如果 k1，开始构建第一维的查找树，将其称之为 F1-trie，它所对应的是分 类器中每一条规则第一个域的前缀集 Rjl。 F1-trie 中的每个结点表示一个前缀front，然后在 front 处进行递归构建一个 (k 1)维的分层查找树 Tp。前缀节点 front 使用 “ 下一级查找树的指针next指向下一级分层树 Tp。由表的规则库得出的分层查找树如图所示。 假设 D 是树中一个结点，如果 D 是 D 的前缀，22 / 42 一般称 D 是 D的祖先。如果 D 是 D的最长前缀，则称 D是 D 的最小祖先。 分类过程：进入分类算法的 IP报文 D(Dl，D2， ?， Dd)，分层查 找树算法首先根据 Dl 在 F1-trie 树上进行遍历，从而找到Dl的一条最佳匹配前缀，记下最后一个匹配结点为 Z，然后沿着 “ 下一级查找树的指针 next” 继续遍历 (Z 1)维的分层查找树，记录下这条路径上所有匹配的规则。接着要回溯到 Z 的最小祖先 Z ，所谓的最小祖先就是指设 Z是树中一个结点，如果 Z 是 Z 的最长前缀，则称 Z 是 Z的最小祖先。继续沿着 Z 的 “ 下 一个查找树的指针 next” 进行遍历，直到 Z 节点的所有祖先都被遍历一次为止。最后，选择匹配规则中优先级最高的规则为进入分类报文的最佳匹配规则。如图给出了二元组 D(00l， 110)的分层查找树，其中虚线表示整个查找的过程。 表 规则库实例 算法基础题 一、常见 查找算方法总结 23 / 42 1. 基本概念 数据：数据即信息的载体，是对客观事物的符号表示，指能输入到计算机中并被计算机程序处理的符号的总称。 数据项：数据项是数据具有独立意义的不可 分割的最小单位，是对数据元素属性的描述。 数据元素：数据元素是数据的基本单位，是对一个客观实体的数据描述。 查找表：进行查找的数据元素通常是同一类型的数据元素或记录，由它们构成的集合称查找表。 查找：查找也称检索，是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元 素。若表中存在一个这样的记录，则称查找成功，反之查找失败。 2. 查找分类 线查找 1). 顺序查找 24 / 42 a. 算法思想： 设查找表是由 n(n0)个元素组成的，从第一个元素开始，顺序查找给定元素，若找到查找成功，反之失败。 b. 算法实现： int search(int array, int n, int data) int i; if(array = NULL) return -1;/查找失败 for(i = 0; i if(arrayi = data) return i;/查找成功 return -1;/查找失败 25 / 42 c. 时间复杂度： O(n) 2). 折半查找 /又称二分查找 a. 算法思想： 在有序表中，取中间元素作为比较对象，若给定元素与中间元素相等，则查找成功。 若给定元素小于中间元素，则在中间元素的左半区继续查找，若给定元素大于中间元素，则在中间元素右半区继续查找，不断重复上述查找过程。 b. 算法实现： int binarySearch(int array, int n, int data)/查找序列必须有序 int low, mid, high; 26 / 42 if(array = NULL) return -1;/查找失败 low = 0; while(low mid = (low + high) / 2; if(data = arraymid) return mid; /查找成功 else if(data else low = mid + 1; return -1;/查找失败 c. 时间复杂度： O(lgn) 3). 分块查找 /又称索引顺序查找，它是顺序查找的一种改进，是一种性能介于顺序查找和二分查找之间的查找方法。 a. 算法思想： 27 / 42 将 n 个数据元素 按块有序 划分为 m 块 (m n) 。每一块中的结点不必有序，但块与块之间必须 按块 有序 ，即前一块中任一元素的关键字都必须小于后一块中任一元素的关键字。 同时根据所有块建立一张索引表，索引表中每一项由关键字字段 (存放块中最大的元素的关键字 )和指针字段 (存放指向相应块的起始下标 )组成。 查找分两个部分，先对索引表进行二分查找或顺序查找，以确定待查元素可能在哪一个块中，然后在已确定的块中顺序查找。 b. 算法实现： #include #include #define B 10 #define I 2 28 / 42 typedef char datatype; /块结点类型定义 typedef struct BlockNode int key;/关键字域 datatype data;/其它域 blockList; /索引结点类型定义 typedef struct IndexNode int indexKey;/索引关键字域 int indexNum;/指向块的第一个元素的下标 indexList; 29 / 42 /分块查找 int indexSearch(blockList b, int m, indexList i, int n, int key) int low, mid, high, start, end, j; low = 0; while(low mid = (low + high) / 2; if(key else low = mid + 1; if(low start = ilow.indexNum; /确定块终止位置 if(low = n - 1) /若带查找元素在最后一个块中 30 / 42 end = m - 1; else end = ilow + 1.indexNum - 1; /在块内顺序查找 for(j = start; j if(bj.key = key) return j;/查找成功 return -1;/查找失败 int main() 31 / 42 int r; blockList listB = 8, a, 14, b, 6, c, 9, d, 10, e, 22, f, 34, g, 18, h, 19, &39 ;i, 31, j; indexList indexI = 14, 0, 34, 5; r = indexSearch(list, B, index, I, 6); printf(待查元素所在位置下表 :%dn, r); return 0; 树型查找 1). 二叉查找树查找 (B树 ) 32 / 42 a. 二叉查找树定义： 二叉排序树又称二叉查找树，它或者是一棵空树，或者是一棵具有如下性质的非空二叉树： (1).若它的左子树非空，则左子树上的所有结点的关键字的值均小于根结点的值。 (2).若它的右子树非空，则右子树上的所有结点的关键字的值均大于根结点的值。 (3).左右子树本身又各是一棵二叉排序树。 b. 算法思想： 当二叉查找树为空时，查找失败。 如果二 叉查找树根结点关键字等于待查找关键字，则查找成功。 如果二叉查找树根结点关键字小于待查找关键字，则用同样33 / 42 的方法在根结点的右子树上查找。 如果二叉查找树根结点关键字大于待查找关键 字，则用同样的方法在根结点的左子树上查找。 c. 算法实现： typedef int keytype; /二叉查找树结点类型定义 typedef struct BSTNode keytype key; struct BSTNode *lchild, *rchild; bstNode; /非递归查找 bstNode *bstSearch(bstNode *t, keytype k) 34 / 42 bstNode *p, *q; int flag = 0; p = t; while(p & !flag) if(p-key = k) flag = 1; else if(p-key k) p = p-lchild; else p = p-rchild; if(flag) return p; else return NULL; 35 / 42 d. 时间复杂度： 最坏： O(n) 平均： O(lgn) 2). 平衡二叉树查找 a. 平衡二叉树定义： 平衡二叉树，又称 AVL 树。 它除了具备二叉查找树的特征之外，还具有如下的特征： 它的左子树和右子树都是平衡二叉树。 同时左子树和右子树的深度 (高度 )之差的绝对值 (平衡因子 )不超过 1。 b. 平衡因子定义： 36 / 42 平衡因子 (Balance Factor)定义为该节点的左子树的深度减去其右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是 -1、 0和 1。 只要树上有一个节点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的了。 c. AVL树的构造： 构造一棵平衡二叉树，需要动态地调整二叉查找树平衡，其方法为： 每插入一个结点后，首先检查是否破坏了树的平衡性，如果因插入结点而破坏了二叉查找树的平衡，则找出离插入点最近的不平衡结点。 然后将该不平衡结点为根的子树进行旋转操作，我们称该不平衡结点为旋转根，以该旋转根为根的子树称为最小不平衡子树。 失衡状态可归纳为 4 种，它们对应着 4种旋转类型： 1). 绕某元素右旋转 (LL型调整 ) 37 / 42 100 85 / 右旋 / 85 120 - 60 100 / / 60 90 80 90 120 80 a) BST 树 b)