代数方程和数值计算的复杂性理论简介.ppt

Email guxf 2020年1月22日星期三 计算的复杂性 计算机科学与工程学院 顾小丰 54 2 第一章代数方程和数值计算的复杂性理论简介 代数方程的不动点迭代算法收敛性和复杂性 算法优劣判别的两个层次 54 3 1 1代数方程的不动点迭代算法 我们知道 形如ax2 bx c 0 a 0的一元二次方程 它的两个根可以按照 这个求根公式算出来 54 4 ay3 by2 cy d 0 a 0可作代换x y b 3a化为无平方项的简化形式x3 px q 0 对简化形式作代换x z p 3z 可将其化为z6 qz3 p3 27 0此方程可看作z3的二次方程 不难解出z 再代回去 得到x1 A B x2 A B 2 x3 A 2 B 其中 是 的立方根之一 一元三次方程的求根公式 54 5 x4 ax3 bx2 cx d 0可以配方成 其中t是待定系数 令 上式的左边为 f x t 2型 为了使上式右边为 g x t 2型要选择适当的t 使判别式为0 即 即t3 bt2 ac 4d t a2d 4bd c2 0先解关于t的三次方程 求出t 进而配方得到 g x t 2 再解两个二次方程f x t g x t 0和f x t g x t 0即可得到结果 一元四次方程的求根公式 54 6 上述这种把代数方程的根用方程系数经有限次加 减 乘 除和开方运算表示出来的方法 叫做代数方程的代数解法 或公式解法 但是 数学家已经证明 五次和更高次方程 就找不到普遍适用的代数解法 这就是说 不会有用方程系数经有限次加 减 乘 除和开方运算把方程的根表示出来的公式 这种 无公式解 的本性是和五次以下的方程不同的 由于这个原因 以后我们只把五次和高于五次的代数方程叫做高次方程 高次方程虽然没有普遍适用的代数解法 但是却有一些非代数的或者说非公式的解法 下面先介绍高次方程的不动点迭代解法 高次方程 54 7 不动点迭代法 代数方程都可以表示成f x a0 xn a1xn 1 a2xn 2 an 1x an 0 a0 0这里f x 是一个n次多项式 如果能够把方程f x 0改写成x x 的形式 并能够找到一个x 使得x x 那么 x 就是原代数方程的一个解 54 8 不动点迭代法 把方程f x 0改写成x x 的形式 非常容易 也有许多方式 例如 可以写成x a0 xn a1xn 1 a2xn 2 an 1 1 x an 也可以写成 等等 因为新方程是从f x 0变来的 所以新方程的解就是原方程的解 x 是新方程的解 就是说x x 请看函数 x 一个函数 就表示一个对应 或者说表示一个变换 函数 x 是把x变成 x 的对应 现在x x 就是把x 变成 x x 自己 换一个说法 就是x 经过 这个变换没有动 由于这个原因 使得x x 的点x 叫做函数 的不动点 形如x x 的方程 也就叫做不动点方程 54 9 不动点迭代法 从上面可以看出 把代数方程改写成不动点方程是容易的 难的是怎样得到不动点x 为此 我们采用迭代方法 找一个点 记作x0 代入函数 得到 x0 记作x1 再代入函数 得到 x1 记作x2 如此一直做下去 可以得到一个序列x0 x1 x2 xn 其迭代关系可以表示成xn 1 xn n 0 1 2 有趣的是 这个迭代序列有时候可以帮助我们找到所要的不动点 这就是不动点迭代方法 54 10 不动点迭代法例1 考虑5次方程x5 17x 2 0首先把它变成不动点方程 这里的 表示 选x0 0进行迭代 得 就是 x x 0 1176483就是 的一个不动点 所以是原方程的一个解 熟悉这方面内容的读者可能已经看出 2是原方程的一个解 但是如果你不懂迭代法 或者虽然懂但不去做 就无论如何看不出0 1176483这个解 54 11 不动点迭代法例1 刚才 我们选x0 0开始迭代 获得成功 这是不是巧合 是不是接受了什么暗示 提出怀疑是完全合理的 应当多做几次试验 下面分别从x0 1 x0 1 x0 2 x0 2 开始迭代 4个迭代序列如下 54 12 不动点迭代法例1 到目前为止 5个迭代都是成功的 一共找到2个解 下面 再扩大范围试试 从x0 3和x0 3开始迭代 数据如下 不必再算下去就可以判断 这两个序列都是没有极限的 迭代公式是 当xn已经很大时 xn5就会非常大 最后除以17 仍然保持很大 所以 从x0 3开始的迭代跑向 从x0 3开始的迭代跑向 它们都不收敛 我们说这样的迭代序列发散 54 13 例1的图示 不动点迭代方法非常简单 但不一定能够保证成功 迭代是否成功 怎样使迭代成功 我们等以会儿再讨论 为了进一步把上述迭代的情况研究清楚 可以画一张迭代图帮助我们分析 图1 1 图1 1 1标明了前面所做的7个迭代过程的结果 1个迭代驻守在2这个点不动 4个迭代收敛到0 1176483 另外两个迭代分别向 和 发散 54 14 例1的图启示 从 3开始的迭代发散 从 2开始的迭代收敛 3和 2之间 应当有一个分界点 分界点在哪里 从分界点开始的迭代 究竟怎样进行 从1开始的迭代收敛到0 1176483这个不动点 从2开始的迭代驻守在2这个不动点 它们之间也应当有一个分界点 也有同样的问题 2和3之间也有同样的问题 这个图启发我们提出进一步的问题 54 15 为此 我们做3个迭代 数据如下 看来 点2向右过去一点 迭代就发散到 点2向左过去一点 迭代就收敛到0 1176483 而从 2 1开始的迭代发散到 54 16 更细致的试验 得出以下数据 54 17 两个结论 点2是个孤立的 很不稳定的不动点 迭代出发点x0与点2差一点点 迭代的结果就完全不同问题 1 的分界点在 2 0590与 2 0589之间 下面我们用另一种不但一学就会而且必定成功的迭代法把这个分界点确定下来 这就是分区间迭代法 二分法 现将这种方法介绍如下 54 18 二分法 我们要解的是方程f x 0 如果我们已经知道两点a b 使得f a f b 0 即f a 和f b 符号相反 那么在 a b 中取中点c 计算f c 如果f c 0 则解已求得 不必再迭代下去 否则 如果f a f c 0 知f c 与f b 同号 就扔掉原来的b 把c作为新b 仍如上法迭代 如果f b f c 0 知f c 与f a 同号 就扔掉原来的a 把c作为新a 仍如上法迭代 这就是同符号顶替的原则 这样 每迭代一次 区间 a b 的长度就缩小一半 而在区间的两端 函数f x 的符号总是相反的 于是 根据f x 的连续性 这些每次缩短一半的区间最后套住一个点 这个点一定是f x 0的解 54 19 二分法求解 现在就来试一试 前已知道 2 0590与 2 0589之间应当有一个分界点 我们就拿a 2 0590和b 2 0589开始 f a 3 817 10 3 0 f b 3 469 10 3 0 正好符合f a f b 0 取 a b 中取中点c 2 05895 计算f c 这时不必记录具体结果 只要知道正负就可以了 算得f c 0 与f a 同号 所以按照同号顶替得原则 取c作为新a 下次迭代就取 a b 2 05895 2 05890 如果拘泥于中点 下次就该取c 2 058925 但对分区间有一个好处 c取偏一点关系不大 只要不跑出 a b 就行了 为了不一下子增加数字的长度 我们取c 2 05893 算得f c 0 再取c 2 05894 也得f c 0 接下去 54 20 二分法求解 c 2 058945 f c 0c 2 058947 f c 0c 2 058948 f c 0c 2 0589475 f c 0c 2 0589477 f c 0c 2 0589476 f c 0 这已经很精确了 我们就取c 2 0589476作为f x 0得一个近似解 这时f c 1 2 10 6 54 21 f x 0的三个解 至此 我们找到了f x 0的三个解 也就是迭代的三个不动点 即2 0 1176483和 2 0589476 经过这样一番研究 我们对迭代的收敛情况有更加准确的了解 这些情况 总结如下图 图1 2 54 22 f x 0的三个解 方程f x x5 17x 2 0共有三个不同的实数解 它们是A 2 058976 B 0 1176483和C 2 从不动点迭代的角度来看 A和C都是孤立的 不稳定的不动点 在A和C附近开始迭代 出发点差一点点 迭代结果就会面目全非 如果以迭代的结局来瓜分实数轴 那么 A 是 的地盘 A C 是B的地盘 C 是 的地盘 而A的地盘只有它自己一个点 A C的地盘也只有它自己一个点 C 54 23 第二个例子 考虑代数方程f x x2 3 0 这个方程太简单了 但着眼于方法的讨论 我们为什么非要复杂的方程不可呢 找复杂的方程来演示 会本末倒置 花费许多精力到技术细节上会妨碍我们对问题实质的认识 所以 这里宁愿用简单的方程 我们采用4种方案 把f x 0变成不动点方程 1 x x x2 3 2 x 3 x 3 x x 3 x 2 4 x x x2 3 4将不动点方程右端的表达式看作 x 就可以将迭代公式xn 1 xn 具体写下来 1 xn 1 xn xn2 3 2 xn 1 3 xn 3 xn 1 xn 3 xn 2 4 xn 1 xn x2n 3 4这4个迭代都从x0 2开始 迭代情况如下 54 24 第二个例子 迭代 1 发散到 不收敛 迭代 2 振荡 也不收敛 迭代 3 和 4 都收敛到方程的解 虽然 3 和 4 都收敛 但是很明显 迭代 3 收敛得比迭代 4 快 54 25 结论 大家是否注意到 迭代 1 和 4 都可以表示成统一得形式 那就是 x x c x2 3 当取c 1时就得 1 迭代不收敛 当取c 1 4时就得 4 迭代收敛了 这个c得选择很有讲究 选得好 就收敛 甚至收敛很快 选得不好 就算得很慢 甚至根本不收敛 从上面得例子可以看出 方程f x 0可以改写为多种不 动点方程 同一个不动点方程也可以选取多个初值 那么应当怎样构造不动点方程 怎样选择初值呢 下面我们来建立求方程x x 的根的迭代过程的收敛性定理和误差估计 54 26 定理1 1 设函数 x 在有限区间 a b 上满足如下条件 1 当x a b 时 x a b 即a x b 2 对任意的x1 x2 a b 恒成立 x1 x2 L x1 x2 即 x 在 a b 上满足Lipschitz条件 L称为Lipschitz常数 且L 1 则方程x x 在 a b 上的解 存在且唯一 并且对任意x0 a b 由迭代过程xn 1 xn 产生的序列 xk 收敛到 54 27 定理1 1的证明 首先证明x x 的解存在且唯一 作函数g x x x 显然g x 在 a b 上连续 由条件 1 可知g a a a 0 g b b b 0由连续函数根的存在定理可知 必有 a b 使g 0 即 因此 是方程x x 的解 其次证明唯一性 假设存在两个解 1 2 则 1 1 2 2 1 2 a b 因此 由条件 2 有 1 2 1 2 L 1 2 因为L 1 所以必有 1 2 再证 xk 的收敛性 按迭代过程xn 1 xn 有xk xk 由条件 2 得 xk xk 1 L xk 1 Lk x0 因L 1 所以 54 28 推论1 1 若条件 2 改为 x 在 a b 上有界 且 x L 1 当x a b 时则定理结论成立 上面证明迭代过程的收敛性 理论上要得到精确解 一般需要进行无穷次迭代循环 这当然是不现实的 实际应用中也只需求得满足精度要求得近似值 为此 我们要估计经过n次迭代后的误差 n xn 54 29 定理1 2 设函数 x 在有限区间 a b 上满足如下条件 1 当x a b 时 x a b 即a x b 2 x 在 a b 上满足Lipschitz条件 且L 1 则成立误差估计式 54 30 定理1 2的证明 对任意正整数m n 有 由Lipschitz条件得 xk 1 xk xk xk 1 L xk xk 1 Lk x1 x0 所以 在上式中 令m 由定理1 1 所以 54 31 定理1 2的说明 在实际计算中 上式也可用来估计达到要求精度 所需要的迭代循环次数 由要求 得 这里 表示不大于x的最大整数 54 32 1 2收敛性和复杂性 算法优劣判别的两个层次 数学讨论最终还是要解决实际问题 如果面对的是方程求解问题 那么首先就要回答方程有没有解这个所谓解的存在性问题 方程有多少个解 解在什么地方等等 也都属于这类问题 存在性讨论有两种基本方式 一种是构造性的证明方法 那就是具体设计一种方法把解找出来 从而说明解是存在的 找到了的东西当然是存在的东西 这就是构造性方式的哲学 另一种是非构造性的证明方法 其代表就是反证法 假定没有解 然后通过推理 引出与已知事实的矛盾 54 33 反证法 反证法在逻辑上常常是漂亮的 但是带给人们的信息较少 例如 面对3只雏鸡 你看也不看就可以作出 其中必有两只雏鸡的性别相同 这样一个存在性的判断 因为不然的话 就和鸡只有雌雄两个性别的已知事实矛盾 这个判断过程 就是非构造性的 徜若你是一个识鸡的行家 确实辨认出其中有两只雌鸡或雄鸡 并由此得到 有两只雏鸡的性别相同 的判断 这个判断的论证过程就是构造性的 两相比较 构造性的判断方式具体指出了两只雌鸡或雄鸡 所以提供的信息较多 而前面所说的非构造性的判断 在我们这个雏鸡识别的问题里 没有提供一点有实用价值的信息 54 34 反证法 但是在数学发展的漫长进程之中 非构造性的讨论方法作用很大 功不可没 我们知道 社会要求和内部动力是数学发展的两大激励因素 非构造性的讨论方式 常常就是数学大系统的内部动力的体现 另外 除了没有构造性方法时自然欢迎非构造性方法外 我们还要注意 人类的认识都是相互联系的 非构造性方法得到的结论 常常可以给研究构造性方法指引方向 最典型的例子 就是数学家已经用非构造性的方法证明了 不存在用圆规和直尺三等分任意角的通用方法 不存在高次方程的代数解法 这就使后人可以避免在寻求三等分角和高次方程代数解方面空耗精力 论证某种东西不存在 和论证某种东西存在一样 都属于存在性问题 相反 如果对于一个问题 数学家已经用非构造性方法证明了解是一定存在的 这就指引后人更明确地去寻求把解具体找出来的构造性方法 最典型的例子 就是代数基本定理 54 35 代数基本定理 多项式有没有根 有多少个根 在二百年前就已经清楚了 论述这一事实的定理 就是著名的代数基本定理 任一n次 复系数 多项式恰好有n个 复 根 大家知道 法国数学家高斯从1799年到1850年前后跨越半个世纪的时间里 曾经提出代数基本定理的四种证明 更早 牛顿 麦克劳林 达朗贝尔 欧拉和拉格朗日 都从事过这一工作 他们提供的证明 基本上都是非构造性的证明 主要思路就是如果没有根 会引出什么样的矛盾 54 36 代数基本定理 随着科学的发展 各方面对数学的要求 越来越倾向于构造性的解决办法 构造性的方法虽然作起来有时比较辛苦 但它不仅肯定了 存在 的事实 而且还告诉人们怎样把这个存在找出来 构造性方法虽然计算比较繁复 但随着计算机的发展和普及 繁复 的弱点大半已经不成问题 构造性方法正好可以借助计算机扬长避短 向人们提供满意的答案 我们下一章要介绍的库恩 Kuhn 算法 就是代数基本定理的构造性证明方法 既然我们强调构造性工作的实际应用价值 那么 面对一种算法 第一要问它是否成功 第二要问它的效率如何 不成功的算法不能把解求出来 当然没用 成功但效率很低的算法 也没有多少价值 如果有人告诉你一种算法 并且在数学上证明了按这种算法一定可以找到问题的解 但是求解要在最新的计算机上花费多少万年的时间 你对这样一种实际上无法实现的构造性方法会有什么感想 恐怕是啼笑皆非吧 54 37 收敛性与复杂性 算法是否成功 是收敛性问题 收敛的就成功 不收敛即发散的就不成功 效率如何 是算法的复杂性问题 复杂性是我们介绍的主题 效率的高低 指的是收敛的快慢 这是毫无疑问的 同一种算法 解小规模的问题花时间少 解大规模的问题花时间多 这是很自然的事情 问题是 随着问题规模的增加 所需要的计算时间怎样增加 以代数方程求解来说 如果方程的次数为n 求解所需要的时间 我们把它暂记为T n T n 究竟是n的什么函数呢 即使没有明确的函数关系 也要尽可能把它们的关系反映出来 因为工作量的大小 工作效率的高低 总是可以用工作时间来表示 所以我们称T n 为解法或算法的时间复杂性函数 不同的算法具有很不相同的时间复杂性函数 说它们当中哪些 效率足够高 哪些 效率太低 总要看当时的情况 但是 计算机科学和计算数学科学家们公认一种简单的区别 这种区别对这些问题提供了重要的透彻的分析 这就是多项式时间算法和指数时间算法的区别 54 38 O f n 的定义 定义1 1称一个函数g n 是O f n 小于等于f n 的阶 当且仅当存在一个常数c 0和n0 0 对一切n n0有 g n c f n 成立 也称函数g n 以f n 为界或者称g n 囿于f n 记作g n O f n 按此定义 如果g n O n2 则一定有g n O n3 为了更精确地说明一个算法的复杂性 有时引人记号 f n 表示阶恰好为f n 的函数 54 39 f n 的定义 定义1 2称一个函数g n 是 f n 当且仅当存在常数c1 0和c2 0及一个n0 0 对一切n n0有 g n c1 f n 和 f n c2 g n 成立 记作g n f n 这样 当f n 5n时 可以记作f n O n2 但不能记作f n n2 只能记作f n n 但在一般情况 人们在进行算法分析时 尽量在 f n 的意义下使用O f n 例如当f n 5n 2时 一般记作f n 0 n 而不记作f n 0 n2 54 40 多项式时间算法与指数时间算法 定义1 3时间复杂性函数T n O p n p n 是多项式 的算法 称为多项式时间算法 不能这样限制时间复杂性函数的算法称为指数时间算法 应该注意到 上述定义1 3中包含某些通常不看作指数函数的非多项式时间复杂性函数的算法作为指数时间算法 例如T n nlogn 指数关系为什么这么重要 下面我们讲一个传说 它明确地把一种算法与计算时间的指数增长展现在我们面前 54 41 梵塔问题 古代印度人把佛教圣地贝拿勒斯看作是世界的中心 传说在贝拿勒斯的圣庙里 有块黄铜板 上面竖着3根宝石柱 这些宝石柱 径不及小指 长仅半臂 大梵天王 印度教的一位主神 在创造世界的时候 在其中一根柱上放置了64片中心有插空的金片 这些金片的大小都不一样 大的在下面 小的在上面 从下而上叠成塔形 着就是所谓的梵天宝塔 大梵天王为宝塔立下了至尊不渝的法则 这些金片可以从一根柱移到另一根柱 没次只能移动一片 并且要求不管如何时刻 也不管在哪一根柱上 小金片永远在大金片上面 绝不允许颠倒 大梵天王预言 当叠塔形的64片金片都从他创造世界是所放置的那根柱上移到另一根柱上 并且也是大的在下小的在上叠成塔形的时候 世界的末日就要来临 一声霹雳将梵塔 庙宇和众生都消灭干净 54 42 梵塔问题 大家可能会想 这个传说未免太不高明了 不就是64片金片吗 顶多几个钟头就可以实现宝塔挪位 到那时候 预言者岂不是要自己掌嘴 我和大家一样 不相信什么世界末日 不过 按照大梵天王的规则把宝塔从一根柱上搬到另一根柱上 可不是容易的事 诚然 传说毕竟是传说 但我们不妨把梵天宝塔作为一种数学游戏 自己动手试一试 按照大梵天王的规则 把一个n层宝塔从A柱移到B柱 至少要移动多少次呢 我们把这个移动次数记作S n n 64是比较多的 我们先从n 1 2 3做起 54 43 梵塔问题 图1 2 1 54 44 梵塔问题 n 1时 把金片直接从A柱移动到B柱就行了 所以S 1 1 n 2时 可以借助C柱 先把小片移到C柱暂住 再把大片直送B柱 最后把小片移到B柱上压在大片上面 三步完成 所以S 2 3 2 S 1 1 n 3时 我们这样来分解任务 先把上面2片移到C柱 再把最底片移到B柱 最后把C柱上的2片移到B柱 这样 3层塔的挪位完成 利用前面讨论的结果 有 S 3 S 2 1 S 2 3 1 3 7 如此这样继续下去 n k时 我们分三步完成 先把上面k 1片移到C柱 再把最底片移到B柱 最后把C柱上的k 1片移到B柱 所以S k S k 1 1 S k 1 2 S k 1 1 54 45 梵塔问题 因此 我们可以得到如下的递归序列 故有 S n 2 S n 1 1 2 2 S n 2 1 1 22 S n 2 2 1 22 2 S n 3 1 21 20 23 S n 3 22 21 20 23 2 S n 4 1 22 21 20 24 S n 4 23 22 21 20 2n 1 S 1 2n 2 2n 3 23 22 21 20 2n 1 2n 2 2n 3 22 21 20 54 46 梵塔问题 至此我们知道 把一个n层梵塔按照大梵天王的规则从一根柱上搬到另一根柱上 至少要移动金片S n 2n 1次 假如你手脚非常麻利 一秒钟可以移动一次金片 那么 n 1时 1秒钟就可以完成任务 n 2时 3秒钟就可以完成任务 n 3时 7秒钟就可以完成任务 n 4时 需要15秒钟 n 5时 31秒钟 n 6时 26 1 60 1 05分钟 n 7时 27 1 60 2 12分钟 n 8时 28 1 60 4 25分钟 54 47 梵塔问题 看起来没什么了不起 可是当n 64变成真正的梵天宝塔时 就需要S 64 264 1 18 446 744 073 709 551 615秒钟才能完成移塔的任务 我们知道 平均一年约365 24天 每天24小时 每小时3600秒 所以一年大约31 557 000秒 由此可以看出 需要大约 264 1 31557000 584 600 000 000年的时间才能完成移动任务 我们所面临的宝塔移位问题 问题的规模就是宝塔的层数n 问题的规模只从n 1增加到n 64 为了解决这个问题所需要的时间却从1秒钟增加到约5846亿年 这就是指数增长的厉害 54 48 梵塔问题 按照近代天体物理学的一种理论 太阳系是在大约30亿年前由处于混沌状态的物质逐渐演变而成的 太阳的核子燃料还能使用100 150亿年 如果这种理论正确 那么很容易算出太阳系的寿命不会超过200亿年 这些数据不应当成为 世界末日 的证明 远在太阳系的寿命结束之前 人类文明该早已找到新的寄托 新的载体 新的可以更加大显身手的广阔天地 值得我们惊叹的是 古印度先贤们对指数增长竟有如此深刻的了解 64是一个小小的很平凡的数字 可是通过指数关系 64层梵天宝塔所赋予的期限 却原来如此之长 这个期限比太阳系的寿命还长得多 谁还能企求更多呢 54 49 几种算法的速度比较 表1 1几个多项式的和指数的时间复杂性函数的对比 假定都用1微秒 10 6秒 能够完成一次运算的高速计算机 54 50 算法速度增长分析 从表中可以看出 对于多项式时间复杂性函数 工作量随问题规模n增长而增长的速度都比较温和 但对于指数时间复杂性函数 这种增长到后来就非常激烈 列表的n 60 还不如前面的梵塔问题n 64 随着社会经济的发展和科学技术的进步 应用问题的规模数达到几百几千是常有的事 例如 投入产出的经济分析 就经常要对付几百各经济变量 这个 几百 就是投入产出分析问题的规模 大型线性规划问题要对付上千个方程和上千个约束条件 等式或不等式 这里的 几千 就是线性规划的规模 大家也许会想 虽然问题的规模越来越大 但计算机的运算速度也会越来越快 所以没什么可担心的 其实不然 我们还是以上述6种算法为例 试作分析 假定这6种算法用现有的计算机在1小时内可以解决的问题的最大规模是n 1000 这样做 是为了把6种算法都放在同一条起跑线上 便于做公平的比较 表1 2告诉我们 如果发明了速度等于现有计算机100倍或1000倍的计算机 那么在1小时内可以解决的问题的规模如何变化 54 51 改进技术对多项式和指数的时间算法的影响 表1 2改进技术对几种多项式的和指数的时间算法的影响 1小时内可解的最大的问题实例的规模 54 52 好的 算法 我们看到 对于2n算法 如果计算机速度提高1000倍 在一小时内可解的最大的问题的规模从1000增加到1010 只增加百分之一 而对于n5算法 这个规模从1000增加到3980 差不多增加了3倍 基于上述讨论分析 我们就可以明白 为什么在计算机科学和计算数学中都把多项式时间算法看作是 好的 算法 科学研究的一个重要内容 就是判别和论证现有的各种算法是不是多项式时间算法 或者寻找和设计新的多项式时间算法 既然多项式时间算法是好的算法 那么是否凡是指数时间算法都是不好的算法呢 54 53 小结 这个问题不那么简单 回忆上一节讲的不动点迭代xn 1 xn5 2 17 这是解方程x5 17x 2 0的一种算法 大家已经体会到这个算法相当好 但是 这个算法是多项式时间算法吗 不是 按多项式时间算法的定义 解规模为n的问题所需要的时间不超过cnk 这里c是一个正常数而k是一个固定的非负整数 我们记得 上述迭代如果从n 3开始 就根本不收敛 不解决问题 这就是说 不论迭代多少时间 问题总不能解决 所以 按cnk确定时限的c和k不存在 这就说明它不时多项式时间算法 54 54 小结 但是如果从比较好的地方开始迭代 它又算得很好 令人十分满意 所以 面对一个非多项式时间算法 我们并不立即判断它是不好得算法而完全抛弃 而是要研究它什么时候不好 为什么不好 更要研究它什么时候会表现出好的行为 可以解决我们面对的问题 本来 只有当一种算法是收敛的时候 才可以说它是多项式时间算法或指数时间算法 上述不动点迭代从很多地方开始都不收敛 我们尚且不能笼统说它不好 那么如果是收敛的算法但收敛得比较慢 指数时间 更不能马上说它不好 这是一个更深一步的问题