3)平均情况下的成功检索的计算时间 利用外部结点和内部结点到根距离和之间的关系进行推导 记, >由根到所有内结点的距离之和称为内部路径长度,记为l; 由根到所有外部结点的距离之和称为外部路径长度,记为E 则有, E=|+2n U(n)是平均情况下不成功检索的计算时间,则 U(n) E/(n+1) >S(n)是平均情况下成功检索的计算时间,则 S(n)=/n+
3）平均情况下的成功检索的计算时间 利用外部结点和内部结点到根距离和之间的关系进行推导。 记， ➢ 由根到所有内结点的距离之和称为内部路径长度，记为I； ➢ 由根到所有外部结点的距离之和称为外部路径长度，记为E。 则有， E=I+2n · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ① 记， ➢ U(n)是平均情况下不成功检索的计算时间，则 U(n) = E/(n+1) · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ② ➢ S(n)是平均情况下成功检索的计算时间，则 S(n) = I/n + 1 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ③
由①②③得: s(n)=(1+1/n)U(n)-1 当n→e,S(m)U(n),而U(n)=(ogn) 所以S(m)=O(logn) 成功检索 不成功检索 最好 平均 最坏 最好 平均 最坏 o(1)O(ogn) O (logn) O(logn) O(logn) @(logn)
由① ② ③得: S(n) = (1+1/n)U(n) -1 当n→∞,S(n) ∝ U(n) ，而U(n) = 所以 S(n) = Θ(logn) Θ(logn) 成功检索 最好 平均 最坏 Θ(1) Θ(logn) Θ(logn) 不成功检索 最好 平均 最坏 Θ(logn) Θ(logn) Θ(logn)
4.以比较为基础检索的时间下界 问题:设n个元素的有序表A(1:n),A(1)<A(2)<…A(n)。检索 给定元素x是否在A中出现 问:是否预计还存在有以元素比较为基础的另外的检索算法,它 在最坏情况下比二分检索算法在计算时间上有更低的数量级? 以比较为基础的算法:假定算法中只允许进行元素间的比较,而不 允许对它们实施其它运算
4. 以比较为基础检索的时间下界 问题：设n个元素的有序表A(1:n)，A(1)< A(2) < …< A(n)。检索一 给定元素x是否在A中出现。 问：是否预计还存在有以元素比较为基础的另外的检索算法，它 在最坏情况下比二分检索算法在计算时间上有更低的数量级? 以比较为基础的算法：假定算法中只允许进行元素间的比较，而不 允许对它们实施其它运算
分析:任何以比较为基础的检索算法,其执行过程都可以用 二元比较树来描述 x;A(1) x A x:A(3n+1 不成功 x:A(2) ac). 22-1)(:A( X 不成功 不成功不成功不成功不成刃不成刃不成功不成功不成功 不成功不成功 图2.2两个检索算法的比较树 (a)模拟线性检索(b)模拟二分检索 内结点:表示一次元素的比较,并代表成功检索情况。每棵比较树中恰 好含有n个内结点,分别与n个不同值相对应; 外结点:代表不成功检索情况。每棵比较树中恰好有n+1个外结点分别 与n+1中不成功检索情况相对应
内结点：表示一次元素的比较，并代表成功检索情况。每棵比较树中恰 好含有n个内结点，分别与n个不同i值相对应； 外结点：代表不成功检索情况。每棵比较树中恰好有n+1个外结点分别 与n+1中不成功检索情况相对应。 分析：任何以比较为基础的检索算法，其执行过程都可以用 二元比较树来描述
以比较为基础的有序检索问题最坏情况的时间下界 定理23设A(1n)含有n(n≥1)个不同的元素,且有 A(1)≤A(2)<..≤A(n) 又设,用以比较为基础的算法去判断给定的x是否有x∈A(1:n) 则,最坏情况下,仼何这样的算法所需的最小比较次数FID() 有:FIND(m)2[og(n+1 证明 ①从模拟求解检索问题算法的比较树可知,FIND(η)不大于树中由根到 个叶子的最长路经的距离 ②在所有的二元比较树中必定有n个内结点分别与x在A中的n中可能的 出现相对应。 ③如果一棵二元树的所有内结点所在的级数小于或等于k,则该树中最 多有2k-1个内结点 故,n≤2k-1,即 FNDm)=k≥「gn+1)
以比较为基础的有序检索问题最坏情况的时间下界 定理2.3 设A(1:n)含有 n(n≥1)个不同的元素，且有 A(1) < A(2) < …< A(n) 又设，用以比较为基础的算法去判断给定的x是否有 则，最坏情况下，任何这样的算法所需的最小比较次数FIND(n) 有： x A(1: n) FIND(n) log(n +1) 证明： ① 从模拟求解检索问题算法的比较树可知，FIND(n)不大于树中由根到 一个叶子的最长路经的距离。 ② 在所有的二元比较树中必定有n个内结点分别与x在A中的n中可能的 出现相对应。 ③ 如果一棵二元树的所有内结点所在的级数小于或等于k，则该树中最 多有2 k -1个内结点。 故，n≤2k-1,即 FIND(n) = k log(n +1)