《集合与查找》课件

《集合与查找》ppt课件contents目录集合的基本概念查找算法简介线性查找算法二分查找算法分块查找算法哈希表查找算法集合的基本概念01总结词：明确性详细描述：集合是由确定的、不同的元素所组成的，每一个元素在集合中都有其唯一的位置。集合的定义总结词列举法、描述法详细描述列举法是通过一一列出集合中的元素来表达集合的方法；描述法则是通过元素的共同特征来表达集合的方法。集合的表示方法并集、交集、差集、子集总结词并集是指两个或多个集合中所有元素的集合；交集是指两个或多个集合中共有的元素组成的集合；差集是指从一个集合中去除另一个集合中的元素后剩余的元素组成的集合；子集是指一个集合中的所有元素都是另一个集合中的元素，即一个集合是另一个集合的子集。详细描述集合的基本操作查找算法简介02在数据集合中，根据给定的查询条件，快速定位到目标元素的过程。查找算法在尽可能短的时间内找到目标元素，提高查找效率。查找算法的目标查找算法的定义从数据集合的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个集合。线性查找将数据集合分成两半，比较中间元素与目标元素的大小，再根据比较结果决定在左半部分或右半部分继续查找。二分查找通过哈希函数将目标元素映射到数据集合中的某个位置，直接访问该位置获取目标元素。哈希查找利用树形结构进行查找，如二叉查找树、平衡二叉树、B树等。树查找查找算法的分类时间复杂度空间复杂度稳定性可扩展性查找算法的性能指标01020304衡量查找算法执行效率的重要指标，表示查找算法在不同规模数据集上的运行时间。表示查找算法所需额外空间的大小，用于存储查找过程中所需的数据结构。指查找算法在处理相等的元素时，能否保持原有顺序。表示查找算法在数据集规模不断增大时，性能的稳定性和可维护性。线性查找算法03在最坏情况下，线性查找的时间复杂度为O(n)，其中n为列表的长度。线性查找算法适用于元素按顺序排列且元素数量不多的情况。线性查找算法是一种基本的查找算法，其基本思想是从表的一端开始，顺序扫描，直到找到所查元素为止。线性查找算法的基本思想初始化当前位置为0。从当前位置开始，逐个比较元素，直到找到所查元素或遍历完整个列表。如果找到所查元素，则返回该元素的位置；否则返回-1表示未找到。线性查找算法的实现过程线性查找算法的时间复杂度为O(n)，其中n为列表的长度。因为线性查找算法需要遍历整个列表才能找到所查元素，所以时间复杂度与列表长度成正比。在最坏情况下，即所查元素在列表的末尾时，线性查找的时间复杂度达到最大值O(n)。线性查找算法的时间复杂度分析二分查找算法04二分查找算法的前提条件是数组必须是有序的。二分查找算法是一种在有序数组中查找特定元素的搜索算法。基本思想是将数组分成两半，比较中间元素与目标值，根据比较结果决定搜索哪一半，然后继续对选定的一半进行同样的操作，直到找到目标值或确定目标值不存在于数组中。二分查找算法的基本思想

二分查找算法的实现过程1.确定搜索范围的起始和结束索引。2.计算中间索引mid=(start+end)/2。3.比较中间元素value[mid]与目标值target。4.如果value[mid]==target，则返回mid。6.如果value[mid]<target，则将搜索范围缩小为右半部分，即更新start=mid+1。5.如果value[mid]>target，则将搜索范围缩小为左半部分，即更新end=mid-1。7.重复步骤2-6，直到找到目标值或确定目标值不存在于数组中。二分查找算法的实现过程0102二分查找算法的时间复杂度分析因为每次迭代都将搜索范围减半，所以最多需要log2(n)次迭代即可找到目标值或确定目标值不存在于数组中。时间复杂度为O(logn)，其中n是数组的长度。分块查找算法05将数据表分成若干块，每块内部有序，块与块之间无序。查找时，首先确定待查记录所在的块，然后在该块内进行顺序查找。平均查找长度为块大小加上块内查找长度。分块查找算法的基本思想分块查找算法的实现过程将数据表分成若干块，每块大小可变，但每块内部有序。记录每个块中的最大值和最小值，以及该块的起始位置和结束位置。根据待查记录的键值，确定其所在块。然后在该块内进行顺序查找。找到则返回记录的地址或值，未找到则返回空或错误信息。1.分块2.建立索引3.查找4.返回结果时间复杂度分块查找的时间复杂度为O(n/b+k)，其中n为数据表的大小，b为每块的大小，k为块内查找长度。最好情况待查记录正好在某块的中间位置，此时查找长度为块大小加1。最坏情况待查记录正好是某个块的第一个或最后一个记录，此时查找长度为块大小加2。平均情况假设每个块的大小相同，则平均查找长度为块大小加1.5倍的块内查找长度。分块查找算法的时间复杂度分析哈希表查找算法06通过哈希函数将键转化为数组下标，实现快速查找。哈希表是一种数据结构，通过键值对存储数据，其中键是唯一的。哈希函数将键映射到数组下标，从而实现快速查找。哈希表查找算法的基本思想包括哈希函数、数组和冲突解决策略。定义哈希表结构通过哈希函数将键转化为数组下标。计算键的哈希值当两个键的哈希值相同时，需要进行冲突处理。常见的冲突处理策略有链地址法和开放地址法。处理冲突通过计算键的哈希值，在哈希表中找到对应的值。查找过程哈希表查找算法的实现过程当