清华大学出版社 TSINGHUA UNIVERSITY PRESS 813RAM模型的变形与简化 5.判定树 判定树是一棵二叉树。它的每个内结点表示一个形如x:y的 比较。指向该结点左儿子的边相应于ⅹsy,标号为≤。指向该结 点右儿子的边相应于X>y,标号为>。每一次比较耗费一个单位时 间。下图是对a,b,c三个数进行排序的一棵判定树。 在判定树模型下, a. c 算法的时间复杂性 可用判定树的高度 a, c 衡量。最大的比较 次数是从根到叶的 最长路径的长度。 b
11 8.1.3 RAM模型的变形与简化 5. 判定树 判定树是一棵二叉树。它的每个内结点表示一个形如x∶y的 比较。指向该结点左儿子的边相应于x≤y，标号为≤。指向该结 点右儿子的边相应于x>y，标号为>。每一次比较耗费一个单位时 间。下图是对a，b，c三个数进行排序的一棵判定树。 在判定树模型下， 算法的时间复杂性 可用判定树的高度 衡量。最大的比较 次数是从根到叶的 最长路径的长度
清华大学出版社 8.1.3RAM模型的变形与简化 6代数计算树ACT 以X=(X1,X2,…,Xn)为输入的一棵代数计算树T是一棵 二叉树,且 1)每个叶结点表示一个输出结果YES或NO。 (2每个单儿子内部结点(简单结点yv表示下列形式运算指令 fop或/2op,或 f,=√f 其中,和靥别是结点V在树T中的祖先结点Ⅵ1和2处得到 的结果值,或是x的分量;op∈{+,-,×,∧;c是一个常数。 (3)每个有2个儿子的内部结点(分支结点)V,表示下列形式的 测试指令: f0或E0或彐0 其中,厂是结点在树T中的祖先结点1处得到的结果值,或是 X的分 12
12 8.1.3 RAM模型的变形与简化 6. 代数计算树ACT 以x=(x1，x2，…，xn )为输入的一棵代数计算树T是一棵 二叉树，且： (1)每个叶结点表示一个输出结果YES或NO。 (2)每个单儿子内部结点(简单结点)v表示下列形式运算指令： op 或 op 或 其中， 和 分别是结点v在树T中的祖先结点v1和v2处得到 的结果值，或是x的分量；op∈{+，－，×，/}；c是一个常数。 (3)每个有2个儿子的内部结点(分支结点)v，表示下列形式的 测试指令： >0或 ≥0或 =0 其中， 是结点v在树T中的祖先结点v1处得到的结果值，或是 x的分量。 v v1 f = f v2 f f c v = v1 f v v1 f = f v1 f v2 f v1 f v1 f v1 f v1 f
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1.3RAM模型的变形与简化 7代数判定树ADT( Algebraic Decision Tree) 在代数计算树T中,若将所有的简单结点都压缩到其最近 的子孙分支结点处,并将简单结点处的计算在压缩后的分支结点 处同时完成,则计算结果可看作是输入X的一个代数函数f×)。 由此引出另一个称为代数判定树的计算模型。 代数判定树T是一棵二叉树,且 1)每个叶结点表示输出结果YES或NO (2)每个内部结点V表示一个形如fx1,X2,…,X):0的 比较。其中,X=(X1,X2,…,X)是输入,f是一个代数 函数 13
13 8.1.3 RAM模型的变形与简化 7. 代数判定树ADT(Algebraic Decision Tree) 在代数计算树T中，若将所有的简单结点都压缩到其最近 的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点 处同时完成，则计算结果可看作是输入x的一个代数函数f v (x)。 由此引出另一个称为代数判定树的计算模型。 代数判定树T是一棵二叉树，且 (1)每个叶结点表示输出结果YES或NO。 (2)每个内部结点v表示一个形如f v (x1，x2，…，xn )∶0的 比较。其中，x=( x1，x2，…，xn )是输入，f v是一个代数 函数