4.性能分析 1)空间特性 n+5个空间位置—0(n) 2)时间特性 区分以下情况,并进行相应的分析 >成功检索:所检索的x出现在A中。 成功检索情况共有n种:x恰好是A中的某个元素,A中共有n个元 素,故有n种可能的情况 >不成功检索:所检索的x不出现在A中。不成功检索情况共有n+1 种:x<A(1),或A(i)<x<A(i+1),1≤i<n-1或x>A(n) 成功/不成功检索的最好情况:执行步数最少,计算时间最短 >成功/不成功检索的最坏情况:执行步数最多,计算时间最长 >成功/不成功检索的平均情况:一般情况下的计算时间
4. 性能分析 1）空间特性 n+5个空间位置——О(n) 2) 时间特性 区分以下情况，并进行相应的分析 ➢成功检索：所检索的x出现在A中。 成功检索情况共有n种：x恰好是A中的某个元素，A中共有n个元 素，故有n种可能的情况 ➢不成功检索：所检索的x不出现在A中。不成功检索情况共有n+1 种：x<A(1),或A(i)<x<A(i+1),1≤i<n-1或x>A(n) ➢成功/不成功检索的最好情况：执行步数最少，计算时间最短 ➢成功/不成功检索的最坏情况：执行步数最多，计算时间最长 ➢成功/不成功检索的平均情况：一般情况下的计算时间
实例分析(例31) 频率计数特征 1. while循环体外语句的频率计数为1 2.集中考虑 while循环中的x与A中元素的比较(其它 运算的频率计数与之有相同的数量级) 假定只需一次比较就可确定case语句是三种情况的 哪一种。查找每个元素所需的元素比较次数如下: A 元素 15-6079235482101 成功检索323413234 比较次数 不成功检索3334433344 比较次数
实例分析（例3.1） ❖ 频率计数特征 1. while循环体外语句的频率计数为1 2. 集中考虑while循环中的x与A中元素的比较（其它 运算的频率计数与之有相同的数量级） 假定只需一次比较就可确定case语句是三种情况的 哪一种。查找每个元素所需的元素比较次数如下： A ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼ 元素 -15 -6 0 7 9 23 54 82 101 成功检索 3 2 3 4 1 3 2 3 4 比较次数 不成功检索3 3 3 4 4 3 3 3 4 4 比较次数
9个元素情况下: 今成功检索 最好:1次 最坏:4次 平均:(3+2+3+4+1+3+2+3+4)/9≈2.77次 不成功检索 最好:3次 最坏:4次 平均:(3+3+3+4+4+3+3+3+4+4)10=3.4次
9个元素情况下： ❖成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/9≈2.77次 ❖不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次
二元比较树 算法执行过程的主体是x与一系列 中间元素A(mid)比较。可用一棵 元树描述这一过程,称之为 元比较树。 构造:比较树由内结点和外结点 的两种结点组成: 内结点:表示一次元素比较,用 圆形结点表示,存放一个mid值; 代表一次成功检索; >外结点:表示一种不成功检索的 情况,用方形结点表示。 路径表示一个元素的比较序列。例31的二元比较树
二元比较树 ❖ 算法执行过程的主体是x与一系列 中间元素A(mid)比较。可用一棵 二元树描述这一过程，称之为二 元比较树。 ❖ 构造：比较树由内结点和外结点 的两种结点组成： ➢ 内结点：表示一次元素比较，用 圆形结点表示，存放一个mid值； 代表一次成功检索； ➢ 外结点：表示一种不成功检索的 情况，用方形结点表示。 ➢ 路径:表示一个元素的比较序列。 例3.1的二元比较树 5 2 7 1 3 6 8 4 9
基于二元比较树的分析 口若x在A中出现,则算法的执 行过程在一个圆形的内结点处结 束 口若x不在A中出现,则算法的 执行过程在一个方形的外结点处 结束 外结点不代表元素的比 较,因为比较过程在该外结点的 上一级的内结点处结束。 例31的二元比较树
基于二元比较树的分析 若x在A中出现，则算法的执 行过程在一个圆形的内结点处结 束。 若x不在A中出现，则算法的 执行过程在一个方形的外结点处 结束 ——外结点不代表元素的比 较，因为比较过程在该外结点的 上一级的内结点处结束。 5 2 7 1 3 6 8 4 9 例3.1的二元比较树 6