xx工业大学算法分析与设计一纸开卷资料.doc

1、如果f(n)=O(s(n)并且g(n)=O(r(n),则f(n)+g(n)=O(s(n)+r(n)如果f(n)=O(s(n)并且g(n)=O(r(n),则f(n)*g(n)=O(s(n)*r(n)根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n= N1，f（n）= N2,g(n) =C2r(n)所以 f（n）+ g(n) = C1s(n)+ C2r(n)，f（n）*g(n)= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1*C2；则：f（n）+ g(n) = C3s(n)+ r(n)=O(s(n)+ r(n) f（n）*g(n) w(v),则将v从

2、T删除之后，T变为两个连同的分支，此时，一定有T的边v1连同这两个分支，否则T将是不连通的。从而将v1加入到T中构成一新的生成树T=T-v+v1。且有w(v1)w(v)w(v),从而w(T”)=w(T-v+v1)w(T)。这与T为最小生成树矛盾。证毕。据此利用prim算法或者Kruskal算法算得G的最小生成树即可1已知背包最大承载重量为C，共有n个物品，每个物品的重量分别为Wi(i=1,2,.,n)，价值为 Vi(i=1,2,.n)。证明：假设第k个物品是最优解中的一个物品，则从中拿出Wk对应的物品后所对应的解一定是其余n-1个物品，装入背包最大承载重量为C-Wk的最优解，否则与假设矛盾。

3、2对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。1. 最大值和最小值问题的最优算法：给定n个实数存放于一维数组A中，试设计一个算法在最坏情况下用3n

4、/2-2次的比较找出A中的最大值和最小值6. 试设计在O(n)时间内求得数组A1.n的中位数的算法。将n个输入元素划分成n/5(上取整)个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(上取整) 个。找出这n/5(上取整)个元素的中位数。如果n/5(上取整)是偶数，就找它的2个中位数中较大的一个。 第1行测试：如果i=n，表示已经搜索到了叶节点。如果从xn-1到xn以及从xn到起点x1有一条边，则找到了一条回路。此时，第3行需要判断该回路是否是目前发现的最优回路。如果是，第4行-6行则更新回路的权和bestw以及最优回路。第7-13行继续回溯，在第8行，如果从xi-1到xj有一条边，且B(i)小于当前最优解的值bestw，则表示可以继续往下搜索，同时更新目前所构造路径的权值cw。第2页 共2页