什么是基本运算

《什么是基本运算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、什么是基本运算？什么是算法的时间复杂性（度）？什么是算法的渐近时间复杂性？表示渐进时间复杂性的三个记号的具体定义是什么？什么是最坏情况时间复杂性？什么是平均情况时间复杂性？一般认为什么是算法？什么是计算过程？算法研究有哪几个主要步骤？主要从哪几个方面评价算法？关于多项式时间与指数时间有什么样的结论？什么是相互独立的函数序列？何时称函数项μk(x)能被其它函数项线性表出？根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？求和中的通项与积分中的被积函数之间有什么样的关系？主定理的内容是什么？根据主定理的结论，可以获得哪些关于

2、算法改进的启示？分治法的要领是什么？（分治法可分为哪三个主要步骤？）分治法求最大、最小元算法的主要思想？求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下可以达到下界？如何用分治法求两个n位二进制数x和y的乘积？算法的时间复杂度是多少？用200字概括Select（求第k小元）算法的主要思路。矩阵相乘算法目前最好的时间复杂度是多少？叙述Strassen矩阵相乘算法的主要思路和意义。试用200～300字概述寻找最近点对算法的主要步骤。该算法中有哪几点最为关键？该算法是否可改进？做DFT时，是否总假定有n=2m？

3、什么是快速傅立叶变换（FFT）？如何用FFT来计算2个多项式的乘积？什么是平衡？分治法与平衡有着什么样的关系？分治法与动态规划法之间的相同点是什么？不同之处在哪些方面？简述求矩阵连乘最少乘法次数的动态规划算法（不超过300字）能够用动态规划法求解的问题通常具有什么样的特征？什么是最长公共子序列问题？在求LCS的算法中，C[i,j]是如何计算的？为什么需要这样计算？用200～300字概述求最优二分搜索树算法的主要步骤。算法中有哪几点最为关键？有了Tij的根的序号后，如何构造出最优二分搜索树？FrancisYao的办法为什么会把算法时

4、间复杂度从O(n3)降到O(n2)？用200～300字概述二维流水作业调度算法的主要步骤什么是备忘录方法？它在什么情况下使用较为有效？简单不相交集的合并算法中为什么要引进集合的外部名和内部名？什么是平摊分析？平摊分析常用的手法有哪几种？简单说明这几种手法的要点。为什么树结构下执行O(n)条带路径压缩的Union-Find指令只需要O(n*G(n))时间？树结构下执行O(n)条带路径压缩的Union-Find指令能否降到线性即O(n)时间？用200～300字概述Link(v,r)程序的执行过程。该程序的要点在什么地方？你认为脱线MI

5、N算法的关键点在什么地方？比较LasVegas算法和MonteCarlo算法，它们有什么相同和相异之处？随机算法有哪些优点？简述随机取数算法和找第k小元素的随机算法。什么是Sherwood随机化方法？简述TestingStringEquality算法的误判率分析。计算模型RAM与RASP之间有什么相同和相异之处？AlanTuring是怎样对人类计算过程进行概括的？Church-TuringThesis的内容是什么？它有什么意义？RAM程序、RASP程序与Turing机相互之间的时间复杂度关系是怎样的（考虑两种耗费标准）？RASP程

6、序如何模拟RAM程序？RAM如何模拟Turing机？Turing机如何模拟RAM？Turing机所接受的语言是什么样的语言?各种语言之间有什么样的关系？非确定性Turing机与确定性Turing机的主要区别在什么地方？非确定性Turing机的时间复杂度是如何定义的？Karp多项式规约是如何表述的？它与Cook多项式规约之间的关系如何？什么是NP-完全性语言？什么是NP-完全性问题？什么是NP-hard问题？引入NP-完全性概念有什么意义？列举20个NP-完全性或NP-hard问题。什么是多项式时间近似方案（PTAS）？什么是完全多

7、项式时间近似方案（FPTAS，FPAS）？什么是伪多项式时间的算法？如何用动态规划法求解背包问题？NP的假定之下，可以分成哪4类（举例）？¹NP-hard问题在P为什么当k≥2，k背包问题不存在FPTAS，除非P=NP？