算法设计与分析学习提纲第十四章下界.doc

第十四章 下界14.1 平凡下界平凡下界：用直观的方法就可以推导出来。例14.1 检查个元素的整数数组中，其值为偶数的元素个数。需要对数组中的每一个元素进行判断和累计。对每一个元素进行判断需要时间，对个元素进行判断，就需要时间。因此，是求解这个问题的所有算法的下界。例14.2 检查具有个顶点的有向图的可达性矩阵问题。个顶点的有向图的可达性矩阵是一个的矩阵，需要检查个元素，每检查一个元素至少需要时间，则检查个元素，至少需要时间。因此，是求解这个问题的所有算法的下界。1.4.2 判定树模型一、判定树模型判定树是一棵二叉树：内部结点，相应于形式为的比较。如果关系成立，则控制转移到左儿子结点；否则，控制转移到右儿子结点。叶子结点，表示问题的一个结果。二、用判定树模型建立问题的下界 从根结点开始执行，根据比较操作的结果，将控制转移到它的儿子结点。上述过程一直进行，直到叶子结点为止判定树的高度与问题的时间复杂性有关忽略解题时的所有算术运算，只集中考虑分支执行时的转移次数。14.2.1 检索问题一、检索问题：数组是一个具有个元素的有序数组，给定元素，确定是否在数组中。二、用判定树模型来确定基于比较的检索问题的下界用二叉树表示数组的检索过程，树中的每个结点表示元素和数组中某个元素的一次比较。每次比较有三种可能的结果：、及。假定，如果，则算法检索成功而终止；如果，则算法的执行转移到二叉树的左分支；如果，则算法的执行转移到二叉树的右分支。算法的执行沿左右分支推进，直到叶子结点，若都找不到使的，则算法检索失败而终止。因为检索过程是从根结点开始，直到叶结点为止的。因此，比较与判定的次数是树的高度加1。当被检索元素的个数为时，因为元素是有序的，判定树的内部结点至多为个，其中。如果所有结点都集中在树的第层及其较低的层上，那么，树的高度至少为，由此得到，检索个元素，在最坏情况下，至少需要进行次比较。显然，这也是检索问题的下界。由此可以得到下面的定理：定理14.1 检索具有个元素的有序数组，在最坏情况下的比较次数是。因此，检索问题的下界是，而二叉检索算法是检索问题中的最优算法。例如，则二叉检索问题的判定树如图14.1所示：图14.1 检索有序数组的判定树14.2.2 排序问题一、基于比较的排序问题数组是一个具有个元素的无序数组，把数组按非增或非降顺序排序。二、用判定树模型来确定基于比较的排序问题的下界1、工作过程判定树的每一个内部结点表示一个判定，每一个叶子结点，表示一个输出。在每一个判定中，比较数组中的两个元素和，如果，则控制转移到左分支结点；否则，控制转移到右分支结点。从根结点开始，判定数组中某两个元素进行，根据判定的结果，转移到某个分支结点，又对数组中的某两个元素进行判定，如此进行，直到叶子结点为止，就得到一个有序的数组。图14.2表示对一个具有3个元素的数组进行排序的一种判定树。图14.2 排序三个元素的一种判定树如果被排序的元素个数为， 个元素有种排列，判定树中的叶子结点个数为个。2、判定树的高度引理14.1 若是至少具有个叶子结点的二叉树，则的高度至少为：证明：令为二叉树的高度，第层的叶子结点数目至多为。是至少具有个叶子结点，所以，有，即。因为由图14.3，有：图14.3 计算的近似值定理14.2 任何基于比较的排序算法，对个元素进行排序时，在最坏情况下的时间下界为。14.3 代数判定树模型代数判定树：使判定树内部结点能对个输入变量的多项式进行计算和比较判定，再根据判定的结果进行分支，用这种方式进行计算和判断所产生的判定树，称为代数判定树。14.3.1 代数判定树模型及下界定理一、代数判定树模型1、代数判定树模型个输入变量的代数判定树是一棵二叉树：用如下形式的测试语句标记内部结点的语句：如果成立，则转移到左儿子结点；否则，转移到右儿子结点。其中，是三个关系运算符中的任何一个。用答案或标记叶子结点的语句。2、阶代数判定树对某个，标记内部结点的语句，与其相关的多项式至多是阶多项式，3、线性代数判定树，或线性判定树。标记内部结点的所有语句，与其相关的所有多项式都是线性的，二、下界定理1、判定问题的成员点集是判定问题，是该判定问题的输入实例。的每一个输入实例，看成是维空间中的一点，则对维空间中的子集，如果，当且仅当问题对输入实例的答案为，则称为判定问题的成员点集。2、代数判定树判定中的成员把点作为输入参数，在代数判定树的根结点上开始计算，最终到达代数判定树的叶子结点为，当且仅当，称代数判定树判定中的成员。3、下界定理的引理。引理14.2 令是由下面的阶多项式方程所定义的点集，：（14.3.1）令是在中所具有的连通分支个数，则。其中，：多项式方程中，最高阶多项式的阶数；：多项式方程中自变量的个数，即维空间中的维数；：多项式方程中不等式方程的个数。点集在中的连通分支个数，与多项式方程中等式的个数无关。4、下界定理定理14.2 令是维空间中的任意一个子集，对任一正整数阶的代数判定树模型，判定中成员问题的计算复杂性的下界为。 证明：令是维空间中的任意一个点集，是关于判定中成员的代数判定树。假定，的高度为，从的根结点到叶结点的路径为，其中，是根结点，是中相应于一个答案的叶子结点。对中的点，如果以该点作为的输入，算法在中沿路径到达叶结点，就称该点属于叶结点。令是所有属于叶结点的中的点集。下面估计点集的连通分支个数与的高度之间的关系。算法在根结点接受输入进行计算时，将得到一个计算结果，该结果将可能参予下一结点的计算。一般地，在的每一个结点处所作的计算，是根据输入变量，或其祖先结点的计算结果来进行的。若将结点处的计算结果也用一个变量来表示，则沿路径中各结点所作的计算，将得到关于变量及结点处的变量的一组等式方程：在处的运算对应的等式方程：当结点所作的测试是、或、或时，将得到一个等式方程或不等式方程；如果所作的测试是、或时，将得到等式方程，或，或。其中，变量是为计算而人为引入的一个变量。假设是除外新增加的变量，是沿路径的不等式方程的个数。因为在每个结点处可能增加一个新变量、或增加一个不等式方程，所以有。沿路径得到关于变量的一个维空间的代数系统，在这个代数系统中，多项式的阶为2。令是维空间的代数系统的解所组成的集合。则是在维空间中的投影。其相应的投影变换为：。因为投影变换是连续的，所以有：。根据引理14.2有：因为是所有属于叶结点为的结点的点集，的连通分支必然包含在的某个连通分支之中。因此，的连通分支个数不会超过所有的的连通分支个数的总和，而中的叶结点为的结点个数不会超过。因此，的连通分支个数满足。因此有：由此得到：对于具有任意正整数阶的代数判定树，有如下关系：同样可以得到：因为是判定中成员的代数判定树的高度，它反映了判定中成员的算法在最坏情况下的计算复杂性。下界定理由此得到证明。14.3.2 极点问题一、极点问题给定平面上个点的点集，并假定这个点中的任意三点不共线。判定这个点是否都是凸壳上的极点。二、极点问题的下界令点的坐标为，并令，。可把平面点集看成是维空间中的点。于是，极点问题的成员点集可表示为：假定，是极点问题的一个解，并且已按它们在凸壳上的逆时针顺序排列。可用如下方式构造中的个不同的解：令是的一个排列，；令，。，。显然，并且是中的个不同的点。对每一个点构造一个二维数组，使得，其中， 是平面上三角形的有向面积。因为点集中的任意3点不共线，根据三角形有向面积的定义，中的每一个元素取值为+1或-1。因为点集在凸壳上是按逆时针顺序排列的，对任意的，的第行恰好有一个+1，并且，当且仅当。因此，对任意的，如果，则，即和至少有一个元素不同。假定，这个不同的元素是数组中的第行第列的元素，并进一步假定该元素分别为，。因此，有：现在假定，如果是连接和的连续曲线，是曲线上的一点。当点由沿着曲线移动到时，在处的将变成处的。因为的变化是连续的，所以，上必有一点，使得。这表明三点共线，即。因此，和属于的不同连通分支。因为和是任意的，由此，有。由定理14.2，可得极点问题的下界为。14.4 线性时间归约通过归约求问题的下界1、思想方法已知问题的下界，把问题归约为问题，从而建立问题的下界。2、步骤1）把问题的输入，转换为问题的相适应的输入；2）对问题进行求解；3）把问题的输出转换为问题正确的解。如果第一步和第三步可以在时间内完成，为问题的输入规模，为的多项式，称问题和问题是时间等价的；如果为的线性函数，则称问题以线性时间归约于问题，记为，称问题和问题是等价的。称问题和问题具有相同的计算复杂性。则问题的下界即问题的下界。14.4.1 凸壳问题求凸壳问题的下界1、思想方法：已知排序问题SORTING在最坏情况下的时间下界为。排序问题可以线性时间归约于凸壳问题CONVEX HULL，从而，凸壳问题在最坏情况下的时间下界也为。2、步骤：1）正实数集合是排序问题的一个输入。把集合中的每个实数，变换为二维平面上的点，所构造起来的这个点，都在抛物线上，如图14.4所示：图14.4 把排序问题归约为凸壳问题显然，这一变换过程可用线性时间来完成。2）把抛物线上的点作为凸壳问题的输入，用求解凸壳问题的任何一个算法，对这个输入实例进行求解。其结果将输出图14.4的凸壳上极点坐标的一个有序表。3） 按顺序读取极点坐标有序表中每一点的坐标值，得到排序过的原来的实数集。这一过程也用线性时间完成，则凸壳问题的输出也以线性时间变换为排序问题的输出。由此得到：SORTING CONVEX HULL因此，凸壳问题CONVEX HULL在最坏情况下的时间下界也为。14.4.2 多项式插值问题一、多项式插值问题给定对实数，其中，当时，。求阶多项式，使得，。二、多项式插值问题的下界思想方法：构造一个判定问题，使其线性数据归约于多项式插值问题，求取判定问题的下界，则该下界也是多项式插值问题的下界1、多项式的给定考虑阶多项式，当，时，如图14.5所示。图14.5 一个特殊的n 1阶多项式2、构造判定问题上述方程对所有的，存在和，满足，使得，。和分别是方程：的个根。构造判定问题，使得它的成