8.2.27 连姆塔吊算法与NGA类问题.ppt

文档介绍：,同时,对必须要输出的元素进行计数。这种计数方法产生的是一个连姆塔吊算法(OrdinaryLowerBound).,同时,对必须要输出的元素进行计数。这种计数方法产生的是一个连姆塔吊算法(OrdinaryLowerBound).例:生成n个元素的所有排列对象的算法属于Ω(n!)连姆塔吊算法往往过小而失去意义。例:TSP问题的连姆塔吊算法是Ω(n2),而不去考虑在后面看来这种选择是否合理,而且它还不会改变决定:一旦选出了一张货币,就永远选定。付款问题的合治选择策略是尽可能使付出的货币最快地满足支付要求,其目的是使付出的货币张数最慢地增加,这正体现了设计思想。!和叶子结点的二叉树,则T的高度至少是:nlog2n-=Ω(nlog2n)通常称为信息论下界,说明任何基于比较的对n个元素排序的算法,判定树的高度都不会大于Ω(nlog2n)。因此,Ω(nlog2n)是这些算法的时间下界。,对n个元素进行排序的时间下界为Ω(nlog2n)<a2a1<a2<a3是是是否否否a1<a3a2<a3a2<a1<a3a2<a3a3<a2<a1a2<a3<a1a1<a3a3<a1<a2a1<a3<a2否否是是例:对三个数进行排序的判定树最坏情况下的时间复杂性是从根节点到叶子结点的最长路径长度,它不会超过判定树的高度。,划分成一些规模较小的子问题,以便各个击破,分而治之。更一般地说,将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。:计算an,应用离治技术得到如下计算方法:34323281313**********分解