算法导论习题答案.doc_第1页
算法导论习题答案.doc_第2页
算法导论习题答案.doc_第3页
算法导论习题答案.doc_第4页
算法导论习题答案.doc_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

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

文档简介

Chapter2 Getting Start2.1 Insertion sort2.1.2 将Insertion-Sort重写为按非递减顺序排序2.1.3 计算两个n位的二进制数组之和2.2 Analyzing algorithms2.2.1将函数用符号表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n个元素已经是最大的元素了.最好时间和最坏时间均为2.3 Designing algorithms 2.3.3 计算递归方程的解（1） 当时，显然有（2） 假设当时公式成立，即，则当，即时， 2.3.4 给出insertion sort的递归版本的递归式2.3-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2.3-7 给出一个算法，使得其能在的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间，然后再进行查找：Search(A,n,x) QuickSort(A,n);i1; jn;while Ai+Ajx and ij if Ai+Ajxii+1 elsejj-1if Ai+Aj=x return trueelse return false 时间复杂度为。或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为。Chapter3 Growth of functions3.1Asymptotic notation3.1.2证明对于,时， 对于，时，存在，当时，对于，3.1-4 判断3.1.6 证明如果算法的运行时间为，如果其最坏运行时间为，最佳运行时间为。最坏时间，即；最佳时间，即3.1.7：证明 定义3.2 Standard notation and common functions3.2.2 证明3.2.3证明 3.2.4与是否多项式有界设lgn=m，则 lgn！不是多项式有界的。3.2.5比较lg(lg*n)与lg*(lgn)lg*(lgn)= lg*n-1设lg*n=x，lgxx-1 lg*(lgn)较大。Chapter4 Recurrences4.1 The recursion-tree4.1.1 证明的解为4.1.2 证明的解为设 ，当4.1.3 将假设改为T(n) = cn lgn +b，只需要在T(1)=1的情况下成立。 4.1.6 计算的解令令T(n)=S(m),则其解为4.2 The recursion-tree method4.2.1 4.2.2 略4.2.3 4.2.5 4.3 The master method4.3.1 略4.3.4 主方法是否适用方程，给出该方程解的一个上界不适用使用递归树方法可以求得其一个上界为4.3.
人人文库> 全部分类> 应用文书 > 研究报告

温馨提示

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

最新文档

评论

0/150

提交评论