东南大学算法设计与分析复习题 2012年
故S1中的数据元素至多有7n/10+6个, 即|S1| 7n/10+6。因此,调用Select(k,S1)的 时间复杂度不超过T(7n/10+6)。
6.b:若|S1|<k |S1|+|S2|,则第k小元素必定在S2中。 因为S2中的元素的值均等于m,故第k小元素就是m。 由于答案已经得到,此时立刻返回第k小元素m。 这部分工作的时间复杂度为O(1)。
6.c:若k>|S1|+|S2|,则第k小元素必定大于m,因此在S3中。 而且此时该元素在S3中应为第k-|S1|-|S2|小的元素。 于是递归调用Select(k-|S1|-|S2|, S3), 就可以获得S中的第k小元素。 因小于等于m的数据元素至少有3n/10-6个
1的情况下,T(n)分别为什么? 1及p+q 时间复杂度为T(n)=T(p*n)+T(q*n)+a*n时,在p+q
答:T(n) a*n*∑k=0∞(p+q)k
矩阵相乘算法目前最好的时间复杂度是多少?
答:目前矩阵乘法最好的时间复杂度是能做到O(n2.376)
叙述Strassen矩阵相乘算法的主要思路和意义。
答:把矩阵A,B分成4个规模为n/2的子矩阵快
C11=A11B11+A12B21, C12=A11B12+A12
C21=A21B11+A22B21, C22=A21B12+A22B22
同时引入下列Mi(i=1,2...7)
则计算两个n阶矩阵的乘法为7对n/2阶矩阵的乘法(时间为7T(n/2)),以及18对n/2阶矩阵的加减法则递归方程为T(n)=7T(n/2)+ Θ(n2),由主定理得T(n)= Θ(n2.81). Strassen矩阵相乘算法意义在于打破了人们认为矩阵乘法得时间复杂度为Θ(n3)得固定看法。
什么是最长公共子序列问题?在求LCS的算法中,C[i,j]是如何计算的?为什么需要这样计算?
答:若Z<X,Z<Y,且不存在比Z更长的X和Y 的公共子序列,
则称Z是X和Y 的最长公共子序列,记为Z∈LCS(X,Y)。如何在低于指数级的时间复杂度内找到LCS称为最长公共子序列问题
C[i,j]=0, 若i=0或j=0
C[I,j]=C[i-1,j-1]+1 若i,j>0且xi=yi
东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...
算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...
算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...
算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...
算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...
算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...
算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...
算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...
算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...
计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....
热门文档