排序二叉树时间复杂度_空间复杂度怎么算例题

排序二叉树时间复杂度_空间复杂度怎么算例题二叉排序树(二叉搜索树)的时间复杂度&空间复杂度中科大算法导论实验,包括代码报告和可执行文件,vc++6.0下编程,c语言代码。实验部分一、要求1.算法设计与分析1班,10月21日(周日)开始上课,晚上19:00-22:00。连续八周每周日在明德楼103实验室上实验课。2.实验

二叉排序树(二叉搜索树)的时间复杂度&空间复杂度   中科大算法导论实验,包括代码报告和可执行文件,vc++6.0下编程,c语言代码。   实验部分   一、要求   1.算法设计与分析1班,10月21日(周日)开始上课,晚上19:00-22:00。连续八周每周日在明德楼103实验室上实验课。   2.实验要求独立完成,发现抄袭则实验为0分(包括网上的代码),没有分组。   3.要求提交实验源码,可执行程序以及实验报告。实验报告包括程序的输入,输出,结果,演示界面,算法语言描述,原理等。要求把所有实验打包成一个rar文件后提交到教学系统,并且命名文件格式为学号+姓名(eg. 学号_NAME),不符合命名格式的一律不批改。   4.程序语言不做特别要求,C、C++、JAVA均可   5.实验提交截止时间: 2012/12/16 23:59:00 之前   二、题目   1.(必做题) 常见排序算法的实现与性能比较   问题描述:实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法   实验要求:   A. 在随机产生的空间大小分别为   N = 10, 1000,10000,   的排序样本(取值为[0,1])上测试以上算法。   B.结果输出:   1) N=10时,排序结果。   2) N=1000,10000,时,对同一个样本实例,不同排序完   成所需的时间。   3) N=1000,10000,时,每个排序用不同的样本多试验几   次(最低5次)得出平均时间,比较不同排序算法所用的平均时间。   文档要点:总结对各种排序的性能分析。   2. (必做题) 红黑树、二叉搜索树的实现和性能比较   问题描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。   另外,红黑树实现计算树黑高的算法。   实验要求:   1).插入测试,输入 8,11,17,15,6,1,22,25,27,建立红黑树,按照 红黑树信息输出方式 输出整棵红黑树以及黑高。   2).删除测试,删除1)中红黑树中Key=15的节点,按照 红黑树信息输出方式 输出调整后的整棵红黑树以及黑高。   3).随机产生300,000个不同自然数Key值(1-300,000,每个数出现一次,出现顺序随机),建立红黑树,查找Key=15000的节点,输出查找花费时间。   用上面的数据,建立二叉搜索树,查找Key=15000的节点,输出查找花费时间。   4). 重复3-5次3)中操作,求各自平均时间。   5). 在1)-4)的红黑树算法基础上修改完成P307 14.1-4算法 OS_Key_Rank(T,k). 输入 1,2,3,4,5,6,7,8 建树, k=6, 输出OS_Key_Rank的返回值。   文档要点:总结红黑树和二叉搜索树在查找上的性能分析,描述此类算法的应用。   附: 红黑树信息输出方式(右图)   3. (选做题) 最长递增子序列   问题描述: 随机生成小于等于n的自然数的一个序列,输出其最长递增子序列(任意一个即可)。   n 分别取 1000,3000,10000。   例: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。   提示:参考LCS,思考能否达到时间复杂度(O(nlogn))   文档要点:描述动态规划思想,总结时间和空间复杂度。

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/66724.html

(0)
上一篇 2024年 8月 9日
下一篇 2024年 8月 9日

相关推荐

关注微信