算法分析笔记.docVIP

第一章 渐进复杂度 函数的渐进性态与渐进表达式：一般来说，当N单调增加且趋于∞时，T(N)也将单调增加趋于∞。 对于T(N)，如果存在函数T(N)，使得当N→ ∞使有(T(N)-T(N))/T(N) →0，那么我们就说T(N)是T(N)当N→ ∞时的渐进性态。 在数学上，T(N)是T(N)当N→ ∞时的渐进表达式。 例如：3N2+4NlogN+7与3N2。 第2章 递归与分治策略 一、什么是分治法? 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 二、分治法使用条件 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 三、排序 1、插入排序 2、归并排序 3、快速排序 分治策略求解问题可以分为三步：分解；递归地解子问题；组合。有的问题分解难而组合容易，如__快速排序____，有的问题分解容易而组合难，如__归并排序___。 四、最近点对问题 S中的点退化为x轴上的n个点x1, x2, …, xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对 (p1, p2) 和(q1, q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min{(p1, p2), (q1, q2)}即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3, q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。 第三章 动态规划 一、算法总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 二、矩阵连乘问题 三、最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。 证明0/1 背包问题具有最优子结构性质 即若背包容量为c时，(y1, y2,··· yn )为待选物品为1到n时knap(1, n, c)的最优解，则(y2, ··· yn )将是物品1作出选择后的子问题knap(2，n ，c)的最优解。 当第一个物品做出决策后，有两种状态 y1=0，则背包容量没有影响，(y2, ··· yn )是kanp(2,n,c)的最优解。 y1=1，则背包容量减少w1，价值增长v1，(y2, ··· yn )是knap(2，n ，c)的最优解。 证明：若(z2, ··· zn )是下述子问题的一个最优解，而(y2, ··· yn）不是它的最优解 已知：p = max(v1x1+v2x2+……+vnxn) ; W1x1+w2x2+……..+wnxn=c-w1x1 则v2z2+v3z3+….vnzny2x2+y3x3+……….ynxn ; 且w1y1+w2v2+….wnvn=c ; Y1y1+v2z2+…….vnzny1y1+y2y2+………ynxn ; 这说明(y1,z2, ··· zn )是所给问题的一个更优解， 从而(y1, y2,··· yn )不是原问题的最优解，矛盾。 背包问题的递归关系 设背包问题的子问题的最优值为m( i, j ),即m( i, j)是背包容量为j，可选择物品为i，i＋1，···, n时的最优值。 当选择第i个物品时， m( i, j) = m(i + 1, j - wi) + vi 如果不选择第i个物品，则m( i, j) = m(i + 1, j)。 由问题的最优子结构性质，我们可以建立计算m( i, j)的递归式如下： 当j=wi时 则有m(i，j) = max(m(i+1 , j) , m(i+1 ， j-wi)+vi ; 当jwi ; 则有m(i , j) = m(i+1 , j) ; 其中：m