第十四章下界

1、第十四章第十四章 下界下界14.1 平凡下界平凡下界14.2 判定树模型判定树模型14.3 代数判定树模型代数判定树模型14.4 线性时间归约线性时间归约14.1 平凡下界平凡下界 平凡下界：平凡下界：用直观的方法就可以推导出来用直观的方法就可以推导出来。14.2 判定树模型判定树模型14.2.0 判定树模型概述判定树模型概述14.2.1 检索问题检索问题14.2.2 排序问题排序问题14.2.0 判定树模型概述判定树模型概述14.2.1 检索问题检索问题一、检索问题一、检索问题二、用判定树模型来确定基于比较的检索问题的下界二、用判定树模型来确定基于比较的检索问题的下界一、用判定树模型确定基于

2、比较的检索问题的下界一、用判定树模型确定基于比较的检索问题的下界二、用判定树模型确定基于比较的检索问题的下界二、用判定树模型确定基于比较的检索问题的下界图14.1 检索有序数组的判定树14.2.2 排序问题排序问题一、基于比较的排序问题：一、基于比较的排序问题： 数组数组A是一个具有是一个具有n个元素的无序数组，把数组个元素的无序数组，把数组A按非增或按非增或 非降顺序排序。非降顺序排序。14.2.2 排序问题排序问题二、用判定树模型确定基于比较的排序问题的下界二、用判定树模型确定基于比较的排序问题的下界 1、工作过程：、工作过程： 判定树的每一个内部结点表示一个判定，每一个叶子结点，表示一判

3、定树的每一个内部结点表示一个判定，每一个叶子结点，表示一 个输出。个输出。 在每一个判定中，比较数组中的两个元素在每一个判定中，比较数组中的两个元素Ai和和Aj， 如果如果 AiAj，则控制转移到左分支结点；，则控制转移到左分支结点； 否则，控制转移到右分支结点。否则，控制转移到右分支结点。 从根结点开始，判定数组中某两个元素进行判定，从根结点开始，判定数组中某两个元素进行判定， 根据判定的结果，转移到某个分支结点，根据判定的结果，转移到某个分支结点， 继续对数组中的某两个元素进行判定，继续对数组中的某两个元素进行判定， 如此进行，直到叶子结点为止，就得到一个有序的数组。如此进行，直到叶子结点

4、为止，就得到一个有序的数组。图图14.2表示对一个具有表示对一个具有3个元素的数组进行排序的一种判定树个元素的数组进行排序的一种判定树。图14.2 排序三个元素的一种判定树由图由图14.3，有：，有：3. 信息论下限：信息论下限： 任何求解某类问题的算法，都必须解决一定数量的不确定任何求解某类问题的算法，都必须解决一定数量的不确定 信息，信息， 根据算法必须处理的信息量建立算法的时间下限。根据算法必须处理的信息量建立算法的时间下限。 定理定理14.1和引理和引理14.1根据信息论下限而建立。根据信息论下限而建立。14.3 代数判定树模型代数判定树模型14.3.1 代数判定树模型及下界定理代数判

5、定树模型及下界定理14.3.2 极点问题极点问题14.3.1 代数判定树模型及下界定理代数判定树模型及下界定理一、代数判定树模型一、代数判定树模型二、下界定理二、下界定理一一 代数判定树模型代数判定树模型代数判定树：代数判定树： 把判定树内部结点的判定功能予以扩大，使判定树内部结点把判定树内部结点的判定功能予以扩大，使判定树内部结点能对个能对个n输入变量的多项式进行计算和比较判定，再根据判输入变量的多项式进行计算和比较判定，再根据判定的结果进行分支，用这种方式进行计算和判断所产生的判定的结果进行分支，用这种方式进行计算和判断所产生的判定树，称为代数判定树。定树，称为代数判定树。一、代数判定树模

6、型一、代数判定树模型一、代数判定树模型一、代数判定树模型二、下界定理二、下界定理14.3.2 极点问题极点问题一、极点问题一、极点问题二、极点问题的下界二、极点问题的下界一、极点问题一、极点问题二、极点问题的下界二、极点问题的下界14.4 线性时间归约线性时间归约14.4 线性时间归约线性时间归约14.4.1 凸壳问题凸壳问题14.4.2 多项式插值问题多项式插值问题一、思想方法一、思想方法二、步骤二、步骤图图14.4 把排序问题归约为凸壳把排序问题归约为凸壳 问题问题显然，这一变显然，这一变换过程可用线换过程可用线性时间来完成性时间来完成。14.4.2 多项式插值问题多项式插值问题一、多项式插值问题一、多项式插值问