东南大学算法设与分析复习题.doc

什么是基本运算？ 答：基本运算是解决问题时占支配地位的运算（一般1种，偶尔两种）；讨论一个算法优劣时，只讨论基本运算的执行次数。 什么是算法的时间复杂性（度）？ 答：算法的时间复杂性（度）是指用输入规模的某个函数来表示算法的基本运算量。T(n)=4n3 什么是算法的渐近时间复杂性？ 答：当输入规模趋向于极限情形时（相当大）的时间复杂性。 表示渐进时间复杂性的三个记号的具体定义是什么？ 答：1. T(n)= O(f(n))：若存在c 0，和正整数n0≥1，使得当n≥n0时， 总有 T(n)≤c*f(n)。 （给出了算法时间复杂度的上界，不可能比c*f(n)更大） ??? 2. T(n)=Ω(f(n))：若存在c 0，和正整数n0≥1，使得当n≥n0时， 存在无穷多个n ，使得T(n)≥c*f(n)成立。（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小） ??? 3. T(n)= Θ(f(n))：若存在c1,c20，和正整数n0≥1，使得当n≥n0时， 总有 T(n)≤c1*f(n)，??? 且有无穷多个n，使得T(n)≥c2*f(n)成立， 即：T(n)= O(f(n))与T(n)=Ω(f(n))都成立。（既给出了算法时间复杂度的上界，也给出了下界） 什么是最坏情况时间复杂性？什么是平均情况时间复杂性？ 答：最坏情况时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。 ??? 平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值 （一般均假设每种输入情况以等概率出现）。 一般认为什么是算法？什么是计算过程？ 答：一般认为，算法是由若干条指令组成的有穷序列，有五个特性a.确定性（无二义）b.能行性（每条指令能够执行）c.输入 d.输出 e.有穷性（每条指令执行的次数有穷） 只满足前4条而不满足第5条的有穷指令序列通常称之为计算过程。 算法研究有哪几个主要步骤？主要从哪几个方面评价算法？ 答：算法研究的主要步骤是1)设计2）表示 3）确认，合法输入和不合法输入的处理 4）分 析 5）测试 ??? 评价算法的标准有1）正确性 2）健壮性 3）简单性 4）高效性 5）最优性 关于多项式时间与指数时间有什么样的结论？ 答：1. 多项式时间的算法互相之间虽有差距，一般可以接受。 ???? 2. 指数量级时间的算法对于较大的n无实用价值。 什么是相互独立的函数序列？何时称函数项μk(x)能被其它函数项线性表出？ 答：设{μ0(x), μ1(x), μ2(x), ... ,μn(x), ...}是某一数域上的函数序列， （x的值以及μk(x)（k=0,1,2, ）的值都在同一个数域中） 任取μk(x)（k=0,1,2, ），不存在数域中的数α1，α2，，αp，使得μk (x) = α1μi1(x) + α2μi2 (x) + ，即任何一个函数项μk(x)不能被其它函数项线性表出。 根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？ 答：1.若方程(**)恰有r个互不相同的特征根α1，α2，，αr (即i≠j时有αi≠αj)，则齐次方程(*)的解为 an＝A1+ A2+ 齐通解，即齐次方程的通解) （A1～Ar为待定系数，可由r个连续的边界条件唯一确定） 2．若α1，α2是(**)方程的一对共扼复数根ρ和ρ， eiθeiθ.则这两个根对应的解的部分为Aρncos(nθ)+Bρnsin(nθ) (A,B为实的待定系数) 3．若α是(**)方程的k重根，则α对应的解的部分为 C1αn+ C2 nαn+ C3 n2αn+ ～Ck为待定常数) 4．若(*)方程中的f(n)≠0(非齐次)，且q(n)是(*)的一个解， 则(*)方程的解为： (*)的齐通解（含有待定系数）+ q(n) （非齐特解）， （齐通解中的待定系数由边界条件唯一确定） 求和中的通项与积分中的被积函数之间有什么样的关系？ 答：求和中的通项的表达形式一般就是被积函数，一般用放缩的方法求得通项得上下界。 主定理的内容是什么？根据主定理的结论，可以获得哪些关于算法改进的启示？ 答：T(n)=a*T(n/b)+f(n) 1)???? 若有ε 0, 使f(n)=O() (即f(n)的量级多项式地小于的量级), 则T(n)= Θ ()。 2)???? 若f(n)= Θ() (即f(n)的量级等于的量级), 则T(n) =Θ()。 3)???? 若f(n)= Θ(), 则T(n)=Θ( ) 3) 若有ε0, 使f(n)=?即f(n)的量级多项式地大于的量级), 且满足正规性条件： abLogn存在常数c1, 使得对所有足够大的n，有a*f(n/b)≤c*f(n), 则T(n)=Θ(f(n))。 ??? 正规性条件的直观含义: 对所有