《[自制]07工硕算法分析参考资料.doc》由会员分享，可在线阅读，更多相关《[自制]07工硕算法分析参考资料.doc（7页珍藏版）》请在金锄头文库上搜索。
1、算法的知识结构算法概述经典算法分治法递归与分治动态规划贪心法回溯法分支限界法NP完全性理论现代算法简介第一 算法概述1. 什么是算法：l 书本：算法是由若干条指令组成的有穷序列。具有性质：输入、输出、确定性、有限性（程序与算法的主要区别）、能行性。l 课堂：寻找解的过程（Search）；递归反复的寻找最优解（research）。l 算法复杂性：算法所需的计算机资源，包括时间复杂度（T(n)，计算所用的时间）和空间复杂度（S(n)，计算所用的内存空间），n是输入量的规模。l 问题的复杂性与算法复杂性区别：问题复杂性是固定的，涉及NP完全性理论；算法复杂性依据算法不同而不同，一个问题可以有多种算法
2、。2. 复杂度表示方式：(n)渐近复杂度上界 (n)渐近复杂度下界(n)非紧上界 (n)非紧下界(n)/(n)紧渐近界（确界/紧渐近：即上界与下界紧夹住中间范围，使得得到的复杂性分析结果较为精确。）3.算法性质（1）传递性：f(n)= Q(g(n)， g(n)= Q(h(n) f(n)= Q(h(n)f(n)=(g(n)， g(n)=(h(n) f(n)=(h(n)f(n)= W(g(n)， g(n)= W(h(n) f(n)= W(h(n)f(n)=(g(n)， g(n)=(h(n) f(n)=(h(n)f(n)= w(g(n)， g(n)= w (h(n) f(n)= w (h(n)（2）
3、反身性：f(n)= Q(f(n) f(n)=(f(n) f(n)= W(f(n)（3）对称性：f(n)= Q(g(n) g(n)= Q (f(n) （4）互对称性：f(n)= O(g(n) g(n)= W (f(n) f(n)=(g(n) g(n)= w (f(n) （5）算术运算：O(f(n)+O(g(n) = O(maxf(n),g(n)O(f(n)+O(g(n) = O(f(n)+g(n)O(f(n)*O(g(n) = O(f(n)*g(n)O(cf(n) = O(f(n)g(n)= O(f(n) O(f(n)+O(g(n) = O(f(n)4. 复杂度排序：O(1)O(C)O(logl
4、ogn)O(logn)O()O()O(n)O(nlogn) O(n2)O(n3)O(2n)O(3n)O(n!)g(k)=f(2k) 则 g(k)=2g(k-1) +2k-1-1 对此式用递推法就可以解出。第三 各种算法（动态规划、贪心法、回溯法、分支限界法）l 动态规划条件：最优子结构，重叠子问题，备忘录方法解法：根据最优子结构，将问题分解为子问题，求子问题的最优解。由于有些子问题是相同的（重叠子问题），因此通过备忘录方法，将解过的子问题的解用备忘录记录起来，在递归遇到相同问题时则搜索备忘录。搜索备忘录是线性复杂度。优点：带有记忆的算法，可以牺牲空间复杂度，降低时间复杂度，提高效率。缺点：需要
5、满足一定条件。要求整体最优解所以复杂度还是较高。/-解0/1背包问题思路（书上的解法复杂度O(2n)）：分解子问题：只装入一个物品，确定在各种不同载重量的背包下，能够得到的最大价值；然后装入前两个物品，确定在各种不同载重量的背包下，能够得到的最大价值；直到装入n个物体，最后在载重量m的背包下即最大价值。最优子结构：一个物体、j容量的背包问题得到最优解，追加物体、扩大容量用同样的方式也能得到最优解重叠子问题：在增加各种不同载重量的背包中，虽然增加了背包的容量，但增加的容量不足以增加新物品，则子问题重叠；增加一件物品，但当前设定的背包容量已经放不下多余物品，子问题重叠。举例：有5个物品，其重量分别
6、为2,2,6,5,4，价值分别为6,3,5,4,6，背包的载重量为10，要求装入物品重量最少而物品价值最大，求装入背包的物品及其总价值。根据上述思路，列成表格如下：容量物品数量012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515底色灰色并且加下划线的是搜索的过程（在容量为4的背包中放入1个物体，价值最大为6，然后依次到9，再到15）根据这样的思路去列递归式，解得装入背包的物体为x = 1,1,0,0,1/-解旅行商问题（TSPLIB）思路：（书上没有，pd
7、f有，pdf的解法复杂度O(n22n)）分解子问题：如1、2、3、4个城市，则用d (1,2,3,4)表示从城市1到（城市2,3,4所组成的网络）的费用，即d (1,2,3,4) =minc12 + d ( 2,3,4) , c13 + d ( 3,2,4) , c14 + d ( 4,2,3)，c12代表城市1到城市2的费用（和c21不一样），d( 2,3,4)表示城市2到（城市3,4所组成的网络）的费用。又d ( 2,3,4) = minc23 + d ( 3,4) , c24 + d ( 4,3)，再分解得到d ( 3,4) = c34 + d ( 4,) = c34 + c41 其中表
8、示网络出口，即城市4回到城市1的费用。 最优子结构：某城市到剩余各城市所组成网络的最小费用，合起来是整体问题的最小费用。所以从最小的问题即类似d ( 3,4)的最小费用这种情况，倒推回去最后得到d (1,2,3,4)的最小费用。重叠子问题：d ( 4,)、d ( 2,)、d ( 3,)这些问题将会重复出现。举例：4个城市的费用矩阵：解法示意图：比如d ( 3,4) = c34 + d ( 4, ) = c34 + c41 = 2 + 3 = 5，则倒推回去就可以得到按这条路径d (1,2,3,4)会是什么值，最后得到d (1,2,3,4) = min3 + 7 , 6 +10 , 7 +14 = 10 路径顺序是：1,2,3,4
