计算机问题求解 – 论题2-4 - 分治法与递归 2018年03月28日

Mergesort Revisited 问题1: 这个算法究竟是如何“排”序的？

Divide Conquer Conquer Combine 5 2 4 7 1 3 2 6 Divide 5 2 4 7 1 3 2 6 5 2 4 7 1 3 2 6 5 2 4 7 1 3 2 6 Divide Conquer Combine Divide Conquer Divide further, until…

问题2： 人的思维“分而治之” 如何变为算法策略的呢？ 递归：如果分而后的“治”是同样的“治” 叠加：否则。

问题3： 如何考虑分治算法的代 价？ 递归代价与非递归代价

导出递归式 两次递归，理想情况下每次问题规模是原来的一半。 非递归开销

cn log n 这里似乎假设n是2的整次幂，在我们涉及的大多数情况下，这不影响结果。 T(n/2) T(n/2) 确实比插入排序效率高。 递归算法的实际运行效率另行讨论。 这里似乎假设n是2的整次幂，在我们涉及的大多数情况下，这不影响结果。

更一般的情况是 请解释a,b,c的含义，D(n)和C(n)代表什么？ “分”成了多少小问题：a 小问题的规模（通常规模是一样的）：b

问题4： 书上的投资回报问题是怎样 被转化为最大子数组问题 的？ We want to find a sequence of days over which the net change from the first day to the last is maximum.

Maximum subarray

最大投资回报问题：暴力解法 in O(n2) 下面的过程遍历的顺序为： (0,0), (0,1), …, (0,n-1); (1,1), (1,2), …, (1,n-1), …… (n-2,n-2), (n-2, n-1), (n-1,n-1) MaxSum = 0; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } return MaxSum; the sequence i=0 i=1 j i=2 N个元素中任取两个元素子集，C（n，2） in O(n2) i=n-1

用分治法解最大子数组问题 问题5：跨中点的部分如何计算？ Part 1 Part 2 the sub with largest sum may be in: recursion Part 1 Part 2 or: The largest is the result 从mid开始向左扫描到最左边：累加，判断累加后的值是否为最大，记录累加最大时的下标。 Part 1 Part 2 问题5：跨中点的部分如何计算？

O(n log n) 非递归代价：常量 递归，理想状况下问题规模是原来的一半。 非递归代价：线性 非递归代价：常量 T(n)=2T(n)+Θ(n)+c 非递归代价：常量 O(n log n)

矩阵乘法：似乎非得(n3)

问题：你能就以下这句话，说清楚Ω,Θ,О和o的区别吗？ 不会比n3小 一定比n3小

1个n阶方阵相乘的问题可以分解为8个n/2阶方阵相乘的子问题。 N代表的是2维n矩阵，不是n个元素构成的二维矩阵 1个n阶方阵相乘的问题可以分解为8个n/2阶方阵相乘的子问题。

仍然是立方复杂度 问题6： 决定上面的递归代价 比较大的原因是什么？ 因子8不能被“吞啮”掉

问题7： 你能否描述Strassen 方法的基本思想？

复杂的组合为了减少一次乘法 诸Si只需通过加减法计算

这个算法曾经引起轰动 问题8： 你对于这个结果是否有感性认 识？

问题： 两种算法性能的比较 8和7的区别本质上来说是什么 的区别？ 经典矩阵相乘： Strassen算法 T(n)=8T(n/2)+Θ(n2) Strassen算法 T(n)=7T(n/2)+Θ(n2) 问题： 8和7的区别本质上来说是什么 的区别？ 子问题个数的区别

问题9： 为什么降低子问题个数会导致复杂 度的阶下降？是一定的吗？

对应于 T(n)=T(n/2)+T(n/2)+n 的递归树 T(size) nonrecursive cost T(n) n T(n/4) n/4 T(n/2) n/2 所有节点的非递归开销的和就是算法的开销 树的“高度”和“胖度”决定了节点的多寡 在非递归开销不变的情况下，降低“高度”、缩小“胖度”

分治算法的复杂度分析和算法优化  

代入法解(隐式)递归公式 问题：什么叫解递归公式？(在算法分析范畴内) 找出其上界或者下界，或者紧致界

我们猜测解是：     将猜测代入： 验证我们的猜测是否是“合理的”，“可能的”  

证明：   回忆一下： Giving g:N→R+, then Ο(g) is the set of f:N→R+, such that for some cR+ and some n0N, f(n)cg(n) for all nn0. 必须找到合适的c和n0

证明： 奠基： n=1? 选择n0=2进行奠基 归纳：略 T(2)=2T(1)+2=4 当选定c=2时： cnlgn=2*2lg2=4   奠基： n=1? 选择n0=2进行奠基 T(2)=2T(1)+2=4 当选定c=2时： cnlgn=2*2lg2=4 归纳：略 本质上，我们只是找到了T(n)的一个上界nlgn，如果我们需要证明nlgn是T(n)的紧致界，还需做什么？

问题：T(n)的紧致界就是nlgn吗？我们还缺什么？ 猜一个递归式的解，容易吗？ 但是，如果我们猜测解是T(n)=O(n)，会发生什么？得到什么结论？ 将猜测代入：T(n)<=2cn/2+n =cn+n //任取c都不可能满足 T(n)<= cn 但是，如果我们猜测解是T(n)=O(n2)，会发生什么？得到什么结论？ 将猜测代入：T(n)<=2c(n/2)2+n =c/2n2+n //任取C>=2即可满足T(n)<=cn2 本质上，我们只是找到了T(n)的一个上界nlgn，如果我们需要证明nlgn是T(n)的紧致界，还需做什么？证明T(n)=Ω（nlgn） 问题：T(n)的紧致界就是nlgn吗？我们还缺什么？

T(n)=3T(n/4)+(n2) 递归树方法可以直观地帮助我们猜测结果 cn2 3T(n/4) c(¼ n)2 T(n/4)

T(n)=3T(n/4)+(n2) 递归树方法可以直观地 帮助我们猜测结果 Note: Total: (n2) cn2 cn2 log4n c(¼ n)2 c((1/16)n)2 …… …… … Note: T(1) Total: (n2)

分治法一般递归式的递归树分析 一般递归式： T(n) = aT(n/b) + f(n) 递归树扩展到第k层时：

T(n)=aT(n/b)+f(n) a个 a个 f(n) f(n) f(n/b) f(n/b) f(n/b) K=3 aT(n/b3)+f(n/b2) …… aT(n/b3)+f(n/b2) a和b的关系决定了树的“形状” F(n)到nlogba次幂，是递增、递减还是不变，决定了sum是什么量级

T(n)=aT(n/b)+f(n) a个 a个 当递归树扩张结束时： Note: Total ? f(n) f(n) f(n/b) logbn f(n/b2) f(n/b2) f(n/b2) f(n/b2) f(n/b2) f(n/b2) f(n/b2) f(n/b2) f(n/b2) …… …… a和b的关系决定了树的“形状” F(n)到nlogba次幂，是递增、递减还是不变，决定了sum是什么量级 … T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) … T(1) T(1) T(1) Note: Total ?

单纯从左式看，我们可以怎样思考得到它的简单形式？ 问题：当我们将上式和如下递归表达式放在一起时，你能看出上式两个部分分别代表了分治算法中的什么开销吗？ T(n)=aT(n/b)+f(n) 前者是解nlogba个小问题的开销，后者是分解logbn层问题以及合并logbn层解的开销。 从bigO的角度看，比较两者到底“谁的order高”成为关键。 提示：a代表了分治为几块；b代表每块的大小；f(n)代表了分解和合并的开销；其中还有一个隐含的T(1)代表了求解小问题的开销

令 直观上，我们可以“相信”这样一些结论： af(n/b)<=cf(n),将在分治过程中形成一个（小问题分解、小问题解合并）代价的几何递减序列，其综合代价将和f(n)相同阶。

分解综合开销和>原子问题求解开销和 Master定理 分解综合开销和 < 原子问题求解开销和 分解综合开销和 = 原子问题求解开销和 分解综合开销和>原子问题求解开销和 分解综合开销几何递减

Using Master Theorem

Using Master Theorem

问题10： 在比较两个函数大小时， 是什么意思？ Polynomially larger / smaller ε必须存在！

Master定理的条件有空隙 T(n)=2T(n/2)+nlgn a=2, b=2, logba=1, f(n)=nlgn We have f(n)=(n1), but no >0 satisfies f(n)=(n1+), since lgn grows slower that n for any small positive . So, case 3 doesn’t apply. However, neither case 2 applies. 没有覆盖所有可能性！ 1，Case1和3都必须满足多项式大(小):必须存在, 2，Case3的“分解综合开销”呈几何递减趋势！

Open Topics： 请证明master theorem 请介绍Akra-Bazzi method.这个方法是master方法的扩展，请解释：1，扩展表现在哪里？2，AB方法的使用案例；3，证明（if possible）.