算法基础笔记整理

《算法基础笔记整理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法重点总结1.2.算法的特点：确定性,可终止性,可行性，输入，输出_■引言一算法基本概念什么是算法：有限指令序列，对某个问题能够得出正确答案的规则集合3.算法规模：问题实例的大小，输入的大小4.基本运算：主要的、关键的、耗时的最小操作5.算法正确性及复杂度证明方法：反证法、数学归纳法(p(a)成立，且对每个n>a,只要p(n-l)成立，p(n)—定成立)6.算法分析标准：正确性、工作量、占用空间量：算法运行过程中的内存占用情况、简单性和清晰性、最优性(即算法的上界(工作量的上界)等于求解问题的下界(问题固有的复杂度))7.算法选择方法：经验法和理论法

2、(常用)8.法的时间复杂度表示方法：大0表示上界，Q表示下界，0表示同阶9.选择排序:每次选择序列中最小值放在有序序列尾部(与无序数列头部元素交换)10.插入排序：将当前元素与前向有序数列比较”查找插入位置,移动后插入二贪心算法1.贪心算法的一般特性1)优化问题：建立候选对象集2)建立对象集合：划分解对象集和抛弃对象集3)求解终止函数：判断解对象集是否是问题的解或者求解是否结束(未必是最优解)4)可行解函数：判断候选对象集元素是否可以加入到当前解的对象集中(未必是最优解)5)选择函数：指出哪个剩余的候选对象最有可能构成问题的解6)目标函数：给出问题的解

3、functiongreedy(C:set):set构造候选对象集S=0创建解对象集whileC<>cpandnotsolution(S)do循环构造解般集x=select(C)选取C二C{x}去除iffeasible(SU{x})thenS=SU{x}可否加入？ifsolution(S)thenreturnS输出解elsereturn"Nosolution"未找到解3.找零问题的一般特性(1)找最少硬币数，候选对象集{100,25,10,5.1}(2)—选到的硬币集和未被选的硬币集(3)判断解函数(solution)，检查目前已选的硬币集中的金额是否

4、等于要找的钱数(4)如果集合中硬币钱数不超过应找金额，则该集合是可行的(5)选择函数(selection)，从未选硬币集合中找一个面值最大的硬币(6)目标函数(object):计算硬币金额4.图：最小生成树算法的一般特性1)优化问题：建立候选图的边集2)建立集合：已选中的边集MST,未选边集E-MST3)求解终止函数：如果MST构成生成树，则它是一个解4)解存在函数：候选边加入MST构不成回路，则该边可以加入MST5)选择函数:prim算法选择U和V-U之间的最小边加入MST;KrusKal算法从未选边中选最小边加入MST6)目标函数：计算MST中边权

5、值和5.Kruskal算法思想(1)将所有边按权由小到大排列；(2)MST置空;(3)依次取最小边(u,v):法若(u,v)加入MST不构成回路则将(uzv)加入MST;*若MST中的边达到n・l条，则结束；Kruskal算法证明：归纳G的边数归纳基础：当G只有一条边,显然G就是最小生成树；归纳假设：设T中有s

6、。6.Prim算法思想(1)解集合T为空，B为任意顶点(2)从B和V・B之间的边中选一最小边(u,v),u属于B,v属于V・B(3)将(uM加入T,将v加入BPrim算法证明：归纳于T中边的数目,如果T在任何步骤都是有希望的,则往T里加一条边后，仍然是有希望的。7.图：单源最短路径(非负边)Dijkstra算法0(2)FunctionDijkstra(L[l..n,l..n]):array[2..n]arrayD[2..n]C={2/3/..,n}fori=2tondoD[i]=L[lJ]fori=2tondov=someelementofCminim

7、izingD[v]C=C{v}foreachweCdoD[w]=min{D[w]zD[v]+L[v,w]}returnDDijkstra算法证明：(数学归纳法)(a)如果一个顶点i满足iol,且i在S中，则D[i]给出了从源到i的最短路径长度。（b）—个顶点i不在S中，则D[i]给出了从源到i的最短特殊路径长度。（i的前驱在S中）5.贪心算法背包问题（可分割）Functionknapsack(w[l..n]zv[l..n]):array[l..n]fori=ltondox[i]=0weight=0;whileweight

8、mainingobject{seletion}ifweight+w[i]<=Wthenx[i]