原创力文档- 1、本文档共28页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
《集合与查找》ppt课件
contents
目录
集合的基本概念
查找算法简介
线性查找算法
二分查找算法
分块查找算法
哈希表查找算法
集合的基本概念
01
总结词：明确性
详细描述：集合是由确定的、不同的元素所组成的，每一个元素在集合中都有其唯一的位置。
总结词
列举法、描述法
详细描述
列举法是通过一一列出集合中的元素来表达集合的方法；描述法则是通过元素的共同特征来表达集合的方法。
并集、交集、差集、子集
总结词
并集是指两个或多个集合中所有元素的集合；交集是指两个或多个集合中共有的元素组成的集合；差集是指从一个集合中去除另一个集合中的元素后剩余的元素组成的集合；子集是指一个集合中的所有元素都是另一个集合中的元素，即一个集合是另一个集合的子集。
详细描述
查找算法简介
02
在数据集合中，根据给定的查询条件，快速定位到目标元素的过程。
查找算法
在尽可能短的时间内找到目标元素，提高查找效率。
查找算法的目标
从数据集合的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个集合。
线性查找
将数据集合分成两半，比较中间元素与目标元素的大小，再根据比较结果决定在左半部分或右半部分继续查找。
二分查找
通过哈希函数将目标元素映射到数据集合中的某个位置，直接访问该位置获取目标元素。
哈希查找
利用树形结构进行查找，如二叉查找树、平衡二叉树、B树等。
树查找
时间复杂度
空间复杂度
稳定性
可扩展性
01
02
03
04
衡量查找算法执行效率的重要指标，表示查找算法在不同规模数据集上的运行时间。
表示查找算法所需额外空间的大小，用于存储查找过程中所需的数据结构。
指查找算法在处理相等的元素时，能否保持原有顺序。
表示查找算法在数据集规模不断增大时，性能的稳定性和可维护性。
线性查找算法
03
在最坏情况下，线性查找的时间复杂度为O(n)，其中n为列表的长度。
线性查找算法适用于元素按顺序排列且元素数量不多的情况。
线性查找算法是一种基本的查找算法，其基本思想是从表的一端开始，顺序扫描，直到找到所查元素为止。
初始化当前位置为0。
从当前位置开始，逐个比较元素，直到找到所查元素或遍历完整个列表。
如果找到所查元素，则返回该元素的位置；否则返回-1表示未找到。
线性查找算法的时间复杂度为O(n)，其中n为列表的长度。
因为线性查找算法需要遍历整个列表才能找到所查元素，所以时间复杂度与列表长度成正比。
在最坏情况下，即所查元素在列表的末尾时，线性查找的时间复杂度达到最大值O(n)。
二分查找算法
04
二分查找算法的前提条件是数组必须是有序的。
二分查找算法是一种在有序数组中查找特定元素的搜索算法。
基本思想是将数组分成两半，比较中间元素与目标值，根据比较结果决定搜索哪一半，然后继续对选定的一半进行同样的操作，直到找到目标值或确定目标值不存在于数组中。
4.如果value[mid]==target，则返回mid。
6.如果value[mid]target，则将搜索范围缩小为右半部分，即更新start=mid+1。
5.如果value[mid]target，则将搜索范围缩小为左半部分，即更新end=mid-1。
7.重复步骤2-6，直到找到目标值或确定目标值不存在于数组中。
01
02
因为每次迭代都将搜索范围减半，所以最多需要log2(n)次迭代即可找到目标值或确定目标值不存在于数组中。
时间复杂度为O(logn)，其中n是数组的长度。
分块查找算法
05
将数据表分成若干块，每块内部有序，块与块之间无序。
查找时，首先确定待查记录所在的块，然后在该块内进行顺序查找。
平均查找长度为块大小加上块内查找长度。
时间复杂度
分块查找的时间复杂度为O(n/b+k)，其中n为数据表的大小，b为每块的大小，k为块内查找长度。
最好情况
待查记录正好在某块的中间位置，此时查找长度为块大小加1。
最坏情况
待查记录正好是某个块的第一个或最后一个记录，此时查找长度为块大小加2。
平均情况
假设每个块的大小相同，则平均查找长度为块大小加1.5倍的块内查找长度。
哈希表查找算法
06
通过哈希函数将键转化为数组下标，实现快速查找。
哈希表是一种数据结构，通过键值对存储数据，其中键是唯一的。
哈希函数将键映射到数组下标，从而实现快速查找。
包括哈希函数、数组和冲突解决策略。
定义哈希表结构
通过哈希函数将键转化为数组下标。
计算键的哈希值
当两个键的哈希值相同时，需要进行冲突处理。常见的冲突处理策略有链地址法和开放地址法。
处理冲突
通过计算键的哈希值，在哈希表中找到对应的值。
查找过程
当所有键的哈希值分布均匀时，时间复杂度为O(1)。
最优情况
最坏情况
平均情况
当所有键的哈希值都相同
文档评论（0）