《可视化计算》第五章排序与查找(B).ppt

分块查找的时间复杂度 分块查找的时间复杂度：O（索引表查找+块内查找） O（索引表二分查找+块内顺序查找） O(log2 B) + (M+1）/2 O（索引表顺序查找+块内顺序查找） O（ (B+1）/2 + (M+1）/2） 一般描述：O（ ） 分析： 实际应用中不一定分成大小相等的块，可按表的特征分块（如本例所设计） 提高了顺序查找的效率，但付出了空间的代价（索引表） * 哈希查找 哈希是hash的音译，意为“杂凑”，也称散列 哈希表是一种重要的存储方式，哈希查找技术是一种按照关键字编址的检索方法 哈希查找不同于前面的几种查找方法，它是通过对记录的关键字值进行某种运算，直接求出记录文件的地址 是关键字到地址的直接转换方法，而不需要反复比较，所以计算复杂性为常数阶：O（1） * 哈希查找的实现过程 仍以24点不可计算作为基本查找的数据集 由于哈希查找需要对牌组内的牌面进行计算 注意这一点与分块查找不同 每个牌组内的每张牌面，都必须转变成可以计算的数字 需要设计哈希函数并构建哈希表 * 哈希表查找方法的基本思想 如果在记录的存储位置与它的关键字之间建立一个确定的关系H（） 使每个关键字和一个唯一的存储位置相对应 在查找时，只需要根据对应关系计算出给定的关键字值k对应的值H(k)，就可以得到记录的存储位置 在使用哈希方法解决24点不可计算牌组时，就是将牌面数字计算后查表，可以查到为不可计算；不可查到就是可以计算 * 哈希表的构建 哈希函数（hash function），记录的关键字值与记录的存储位置的对应关系H称为哈希函数，H(k)的结果被称为哈希地址 哈希表（hash table），是根据哈希函数建立的表，以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容 * 哈希冲突与解决 冲突（collision），不同的关键字值其哈希函数计算的哈希地址相同，具有相同函数值的关键字值称为同义词（synonym） 本例中处理同义词冲突的方法是拉链法 ，当发生冲突时，在冲突位置的二维数组行上寻找存放记录的空闲单元 * 24点算法的不可计算案例哈希 设定哈希表的长度为149，H关系为： H(key)=key mod 149 + 1 Key的获取原则为： 所有10牌面模除7余3，再参与其他牌面的计算，例如，10 10 10 10等同3 3 3 3 去掉10以后的所有牌面数：key=d1*1000+d2*100+d3*10+d4 H(Key)=3333 mod 149+1=56 * 计算所得的哈希表（局部） 不可计算牌组直接转换成为字符串； 按哈希规则寻址保存在文件记录中 * 构建哈希表的一些要点 可以采用149行，N列的二数组保存哈希表（也就是将同义词的牌组，按计算顺序在一行中排放） 在运行后，发现最大的冲突数为3，因此该算法的实际哈希表为149*3=447个数据单元 在本例构建的哈希表（hash_1[]）的初始化过程中，所有数组元素皆为数值0，在保存牌组时，首先要检测当前数组元素的数据类型 如果不是数值类型，则说明已经填入了数据，需要寻找邻接的属于数值类型的元素再写入 * 哈希表的应用 在应用时，先载入已准备的哈希表 随机生成24点牌组，应用哈希规则得到哈希表的地址 进行查表操作，可以查到，则为不可计算牌组；不可查到，则为可计算牌组 查找的效率在1到3次之间，时间复杂度为：O（1） * 小结与回顾 查找策略则与数据的排序与否，数据自身的属性有重大关系。 顺序查找针对未排序数据， 二分查找针对已排序数据， 分块查找针对按块有序、块内无序的数据 而最能体现计算机科学精髓的查找方法则是哈希查找，哈希查找是通过计算数据元素的存储地址进行查找的算法 * 但是 ，由于在算法设计之初，无法得知数据冲突的程度， 所以可先随便设置一个数，例如：N=5， 也就是假设冲突的最大次数为5次，然后根据运行结果再作调整。 第5章 排序与查找PART B 《可视化计算》 查找 查找算法和排序算法有密切的联系，因为许多查找算法依赖于要查找的数据集的有序程度 基本的查找算法有以下4种： 顺序查找； 比较查找也称二分查找； 基数查找也称分块查找； 哈希查找 * 顺序查找 顺序查找过程： 通常从表中的第一个（或最后一个）记录开始，将记录的关键字与给定值逐个进行比较 当某个记录的关键字与给定值相等时，即找到所查的记录，查找成功； 反之，若查到最后一个记录，其关键字和给定值的比较都不相等，则表明表中没有所查的记录，查找失败。 * 顺序查找的算法设计 由于顺序查找的数据表，无需将节点实现排序，所以可以直接使用随机数产生一张线形表，进行查找的实验 * 二分查找 基本思想： 将n个元素分成个数大致