北京工业大学算法分析与设计一纸开卷资料.doc_第1页
北京工业大学算法分析与设计一纸开卷资料.doc_第2页
北京工业大学算法分析与设计一纸开卷资料.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论