第十四章下界.ppt

第十四章 下界 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 检索问题 一、检索问题 二、用判定树模型来确定基于比较的检索问题的下界 一、用判定树模型确定基于比较的检索问题的下界 二、用判定树模型确定基于比较的检索问题的下界 14.2.2 排序问题 一、基于比较的排序问题： 数组A是一个具有n个元素的无序数组，把数组A按非增或 非降顺序排序。 14.2.2 排序问题 二、用判定树模型确定基于比较的排序问题的下界 1、工作过程： 判定树的每一个内部结点表示一个判定，每一个叶子结点，表示一 个输出。 在每一个判定中，比较数组中的两个元素A[i]和A[j]， 如果 A[i]≤A[j]，则控制转移到左分支结点； 否则，控制转移到右分支结点。 从根结点开始，判定数组中某两个元素进行判定， 根据判定的结果，转移到某个分支结点， 继续对数组中的某两个元素进行判定， 如此进行，直到叶子结点为止，就得到一个有序的数组。 14.3 代数判定树模型 14.3.1 代数判定树模型及下界定理 14.3.2 极点问题 14.3.1 代数判定树模型及下界定理 一、代数判定树模型 二、下界定理 一 代数判定树模型 代数判定树： 把判定树内部结点的判定功能予以扩大，使判定树内部结点能对个n输入变量的多项式进行计算和比较判定，再根据判定的结果进行分支，用这种方式进行计算和判断所产生的判定树，称为代数判定树。 一、代数判定树模型 一、代数判定树模型 二、下界定理 14.3.2 极点问题 一、极点问题 二、极点问题的下界 一、极点问题 二、极点问题的下界 14.4 线性时间归约 14.4 线性时间归约 14.4.1 凸壳问题 14.4.2 多项式插值问题 一、思想方法 二、步骤 14.4.2 多项式插值问题 一、多项式插值问题 二、多项式插值问题的下界 一、多项式插值问题 二、多项式插值问题的下界 图14.4 把排序问题归约为凸壳 问题 显然，这一变换过程可用线性时间来完成。 * * 图14.1 检索有序数组的判定树 图14.2表示对一个具有3个元素的数组进行排序的一种判定树。 图14.2 排序三个元素的一种判定树 由图14.3，有： 3. 信息论下限： 任何求解某类问题的算法，都必须解决一定数量的不确定 信息， 根据算法必须处理的信息量建立算法的时间下限。 定理14.1和引理14.1根据信息论下限而建立。