算法设计与分析第一次作业

2019-10-28 本文已影响0人小菜变大菜

一、渐近增长率分析和比较

(a)将各式化简
$f_{1}=O(n^{3.2})$ $f_{2}=O(n)$ $f_{3}=O(n^{1.25})$ $f_{4}=O(4^{n})$ $f_{5}=O(3^{n})$
因此，按渐近增长大小升序排列有 2<3<1<5<4

(b) $f_{1}=O(n^{10})$ $f_{2}=O(n^{4})$ $f_{3}=O(n)$ $f_{4}=O(n^{n})$
则递增序列为 3<2<1<4

知识点
1. 渐近符号Θ Ω Ο
Θ：渐近紧确界
Ω：渐近下界
Ο：渐近上界
通常情况下，使用Ο（渐近上界），因为当表达式中存在一个上界分析，紧确界和下界将不再适用。
2. 常见大小关系
$O(1)<O(\log n)<O(\log^{2} n)<O(n)<O(n\log n)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})$

二、分治算法与动态规划的区别

分治：解决一个复杂的问题的方法与解决其子问题的方法相同，因此对其子问题分而治之，最终解决这个复杂问题。
DP：复杂问题是其子问题的重复计算的结果。
注意：分治得到的子问题没有关联，而DP的子问题相互重叠。

三、分治算法（递推关系式求解、主定理）

求解递推关系式的三种方法

代入法：猜测一个界，用数学归纳法验证其正确性
递归树法：将递归式转化为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术求解。
主方法：适用于如下的递推关系式
$T(n)=aT(n/b)+f(n)$

其中a≥1，b>1，f(n)是给定的一个函数。它刻画了这样一个分治算法：生成a个子问题，每个子问题的规模都是原问题规模的1/吧，分解和合并步骤总共花费时间为f(n)。
主定理的描述

主定理

直觉我们可以这样认识，两个函数较大者决定了递归式的解，当两者相当时，乘上一个对数因子lgn。
注：这里的比较是多项式意义上的（可以理解成一种渐近关系）。比如，下面这个式子就不能再用主方法求解。 $T(n)=2f(n/2)+O(n\log n)$

回到题目，对于1、3，分别用主定理(1)(2)求解，对于2，需要写出递推关系式，消项求解。
$f(n)=3f(n-2)+O(n)$
$f(n-2)=3f(n-4)+O(n-2)$
$f(3)=3f(1)+O(3)$

最后一项并不一定是f(1)，取1并不影响递归式的渐近性质。
$f_{1}(n)=O(n^{\log_{2}3})$ $f_{2}(n)=O(n\cdot 3^{n})$ $f_{3}(n)=O(n^{2}\lg n)$

四、最长递增子序列（LIS）

(a）递归关系
对于每个元素s[i]，向前找所有小于s[i]的元素。

若存在s[j]<s[i]（j<i），则是L[i] = max{L[j] + 1}
若不存在s[j]<s[i]（j<i）,则s[i]自身构成一个子序列，L[i] = max{L[k]}，k为小于i的整数

(b）最长子序列
L[1]=1, L[2]=1, L[3]=2, L[4]=3, L[5]=4, L[6]=5, L[7]=6, L[8]=6, L[9]=6, L[10]=6, L[11]=7, L[12]=8, L[13]=8, L[14]=8
其中一个最长子序列是{3，6，9，13，14，15，16，20}

详解 https://www.jianshu.com/p/6fc54cec4b4c

五、计算最大流/最小割

最大流和最小割是两个等价的问题，即从S到T能通过的最大流量和切断S-T的连通至少需要割掉的边流量总和。通过不断寻找增广链的方式可以画出最终的剩余图如下，显然最大流为14。

剩余图
思考无向图应该如何构造剩余图，如何求解最大流？