下载此文档

《算法分析与设计》第5次理论作业.docx


文档分类:IT计算机 | 页数:约2页 举报非法文档有奖
1/2
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/2 下载此文档
文档列表 文档介绍
《算法分析与设计》第5次理论作业
作业任务:
1. 简单算法分析题
设n是正整数,给出如下算法的时间复杂度及其推导过程。
void fun(int n)
{
int i= 0;
int s= 0;
while (s < n)
{
i++;
s = s + i;
}
}
2. 复杂算法分析题
求解矩阵乘法采用分块矩阵的方式进行,可以得到递推公式
Tn=O(1)n=1Tn=8Tn2+O(n2)n>1 (2-1)
Strassen改进算法,可以得到递推公式
Tn=O(1)n=1Tn=7Tn2+O(n2)n>1 (2-2)
请给出两个递推公式的推导过程。
3. 算法设计题
(1)自己设计测试用例,分别采用prim算法和kruskal算法构造最小生成树,给出构造过程
(2)自己设计测试用例,给出prim算法和kruskal算法的变量变化表。
(3)自己设计测试用例,给出prim算法和kruskal算法的流程图。
作业要求:
给出推导过程和算法,作业后附亮考帮。变量变化表由自己给出测试用例,不得使用教材、网络和教师使用过的测试用例,流程图用visio绘制,所有内容一起放入一个word中。提交时间为下周三晚上9:30前,9:30-12:30进行作业互评,按时提交,过时不能补交。特别注意,不要把理论和实验作业交错了哟。
特别注意:
严禁抄袭:发现一次抄袭扣3次0分(抄袭者和被抄袭者同时处理),发现3次抄袭则平时成绩记0分,该课程成绩不及格。如果没有能力完成所有作业,可以只完成一部分,只要提交就给及格分3分。
评分标准:
。交错作业
。完成作业的态度敷衍。只完成了第1题,亮考帮敷衍
。完成作业质量一般。完成了第1题和第2题的,亮考帮较好
。完成作业认真,作业质量高、工作量大、难度高。完成了第1题、第2题和第3题,亮考帮内容丰富,写得深刻。

《算法分析与设计》第5次理论作业 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数2
  • 收藏数0 收藏
  • 顶次数0
  • 上传人1017848967
  • 文件大小10 KB
  • 时间2021-12-07
最近更新