无论是最好、最坏、还是平均情况, MaxMin所用的比较数都是3n/2-2,比前面 提到的算法(在最坏情况下)节省了25%的时间。实际上,任何一种以元素比较 为基础的找最大最小元素的算法,其元素比较数的下界是「3n/21-2。从这种意 义上来说, MaxMin算法是最优的。然而,由于需要Logn+1级的递归,每次递 归调用需要将i,j, fmax,fmin和返回地址的值保留到栈中,所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销,特别当A中元素的比 较次数和整数i与j的比较次数相差无几时,递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例4.1.2.搜索算法的时间下界 分析上节提到的折半搜索算法,我们已经知道其时间复杂度是O(logn) 事实上,我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9的二元比较树 n=9情况下折半搜索的二元比较树 由图可见,当ⅹ在数组A中时,算法在圆形顶点结束;不在A中时,算法 在方形顶点结束。因为23≤9<24,所以比较树的叶顶点都在4或5级上出现。 因而元素比较的最多次数为4。一般地有:当n∈p22)时,一次成功的折半搜 索至多做k次比较,而一次不成功的折半搜索或者做k-1次比较,或者做k次比 现在假设数组A[1:n满足:A[1]A[2]<…A[n。要搜索元素x是否在 A中。如果只允许进行元素间的比较而不允许对它们进行其它的运算,则所设计无论是最好、最坏、还是平均情况，MaxMin 所用的比较数都是 3n/2-2，比前面 提到的算法(在最坏情况下)节省了 25％的时间。实际上，任何一种以元素比较 为基础的找最大最小元素的算法，其元素比较数的下界是 3n / 2 − 2 。从这种意 义上来说，MaxMin 算法是最优的。然而，由于需要log n +1级的递归，每次递 归调用需要将 i，j，fmax，fmin 和返回地址的值保留到栈中，所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销，特别当 A 中元素的比 较次数和整数i与j 的比较次数相差无几时，递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例 4.1.2．搜索算法的时间下界 分析上节提到的折半搜索算法，我们已经知道其时间复杂度是O(log n) 。 事实上，我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9 的二元比较树： n＝9 情况下折半搜索的二元比较树 由图可见，当 x 在数组 A 中时，算法在圆形顶点结束；不在 A 中时，算法 在方形顶点结束。因为 3 4 2 ≤ 9 < 2 ，所以比较树的叶顶点都在4或5 级上出现。 因而元素比较的最多次数为 4。一般地有：当 [ ) k k n 2 ,2 −1 ∈ 时，一次成功的折半搜 索至多做 k 次比较，而一次不成功的折半搜索或者做 k-1 次比较，或者做 k 次比 较。 现在假设数组 A[1:n]满足：A[1]< A[2]< …< A[n]。要搜索元素 x 是否在 A 中。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计 4 9 5 7 1 3 6 8 2