§8.1.2检索结构 按检索结构中数据元素是否会增加或减少分类 静态检索结构:操作中不增加或减少元素 动态检索结构:操作中可能增加元素或减少元素
6 • 按检索结构中数据元素是否会增加或减少分类 – 静态检索结构：操作中不增加或减少元素 – 动态检索结构：操作中可能增加元素或减少元素 §8.1 .2 检索结构
§8.13检索算法的时间与空间复杂 度分析 检索算法的空间复杂度分析 在现有结构上进行检索的算法 实现检索算法而构造专门的数据结构的算法 检索算法的时间复杂度分析 以关键字的比较次数为主度量算法的时间复杂度
7 • 检索算法的空间复杂度分析 – 在现有结构上进行检索的算法 – 实现检索算法而构造专门的数据结构的算法 • 检索算法的时间复杂度分析 – 以关键字的比较次数为主度量算法的时间复杂度 §8.1 .3 检索算法的时间与空间复杂 度分析
§8.13检索算法的时间与空间复杂 度分析 待査关键字的位置对算法本身而言是个随机量, 所以要综合测定算法的检索次数,需使用检索 次数的数学期望 ·将检索算法的检索次数的数学期望称为平均检 索长度ASL( Average Search Length) ·对检索成功(关键字在表中)情况其计算式为: ASL=∑pc i=1
8 • 待查关键字的位置对算法本身而言是个随机量， 所以要综合测定算法的检索次数，需使用检索 次数的数学期望 • 将检索算法的检索次数的数学期望称为平均检 索长度ASL（Average Search Length） • 对检索成功（关键字在表中）情况其计算式为： ASL= §8.1 .3 检索算法的时间与空间复杂 度分析 = n i i i p c 1
§8.13检索算法的时间与空间复杂 度分析 ·检索不成功的情况(关键字不在数据元素集 中),平均检索长度即为检索失败对应的比较 次数。 ·检索算法的总的平均检索长度应为检索成功与 失败两种情况的平均检索长度的数学期望
9 • 检索不成功的情况（关键字不在数据元素集 中），平均检索长度即为检索失败对应的比较 次数。 • 检索算法的总的平均检索长度应为检索成功与 失败两种情况的平均检索长度的数学期望。 §8.1 .3 检索算法的时间与空间复杂 度分析
§8.1.4检索算法的判定树 ·判定树中每个结点表示被查数据元素集中的一个元素 (常用元素编号表示) 从树根到某一结点的路径,就表示检索该结点所经历 的过程,路径上各结点为检索中测试(比较)过的结 点 树结点的各个儿子,表示从该结点起下步检索的各选 择分枝 对无儿子结点,表示检索过程进行到它(即与它比较) 后,不能继续进行,应终止
10 • 判定树中每个结点表示被查数据元素集中的一个元素 （常用元素编号表示） • 从树根到某一结点的路径，就表示检索该结点所经历 的过程，路径上各结点为检索中测试（比较）过的结 点 • 树结点的各个儿子，表示从该结点起下步检索的各选 择分枝 • 对无儿子结点，表示检索过程进行到它（即与它比较） 后，不能继续进行，应终止 §8.1.4 检索算法的判定树