下载文档原格式
习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。
解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。
解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。
在某台计算机上实现并完成该算法的时间为t秒。
现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。
习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。
对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。
算法分析与设计第章习题答案第一章习题（1-1,1-2,1-3,1-6）1-1 求下列函数的渐进表达式3n2+10n = O(n2)n2/10+2n = O(2n)21+1/n = O(1)logn3 = O(logn)10log3n = O(n)知识点：如果存在正的常数C和自然数N0，使得：当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时，可以说f(N)的阶不高于g(N)的阶。
1-2 论O(1)和O(2)的区别O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。
1-3 从低到高排列以下表达式（按渐进阶排列以下表达式）结果：2 logn n2/320n 4n23n n! 分析：当n>=1时，有logn< n2/3当n>=7时，有3n < n!补充：当n>=4时，有logn> n1/31-6 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=Θ(g(n))。
知识点：f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=Ω(g(n))；f(n)与g(n) 同阶：f(n)=Θ(g(n)) (1)f(n)= logn2 ; g(n)= logn+5f(n)与g(n)同阶，故f(n)=Θ(g(n)) (2) f(n)= logn2 ; g(n)= n1/2当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。
如依次用n=1, 21, 22, 23, 26, 28, 210 (3) f(n)= n ; g(n)= log2n f(n)=Ω(g(n))(4) f(n)= nlogn+n; g(n)= lognf(n)=Ω(g(n))(5) f(n)= 10 ; g(n)= log10f(n)=Θ(g(n))(6) f(n)= log2n ; g(n)= lognf(n)=Ω(g(n))(7) f(n)= 2n ; g(n)= 100 n2f(n)=Ω(g(n))(8) f(n)= 2n ; g(n)= 3nf(n)=O(g(n))。
算法分析——算法的渐进效率分析⼀、⼤O表⽰法⼀般⽤于界定函数集合的上界，渐进表达式O（g（n））的含义就是，c为正常数，函数集合O中的元素的最⼤值不会超过c.g(n)。
f(n) = O(g(n))的含义是，函数f(n)的属于集合O（g(n)）,因为函数集合O中的最⼤值为c.g(n)，所以f(n)的最⼤值为c.g(n)。
由于只是渐进的上界，所以当函数g（n）的阶数越⼩时，上界越紧确。
下⾯来看下算法导论中是如何描述⼤O表⽰法的。
当函数的⼤⼩只有上界，没有明确下界的时候，则可以使⽤⼤O表⽰法。
f（n）= O（g（n））正式的数学定义：存在正常数c、n、n0，当n>n0的时，对于任意的f（n）对符合0<= f（n）<= c.g（n）。
————————————————直观视觉图如下⽰：⼆、⼤Ω表⽰法⼀般⽤于界定函数集合的下界，渐进表达式Ω（g（n））的含义就是，函数集合Ω中的元素的最⼩值不会低于c.g(n)。
f(n) = Ω（g（n））的含义是，函数f(n)的属于集合Ω（g（n））,因为函数集合Ω中的最⼩值为c.g(n)，所以f(n)的最⼩值为c.g(n)。
算法导论中是如何描述⼤Ω表⽰法的。
当函数的⼤⼩只有下界，没有明确的上界的时候，可以使⽤⼤Ω表⽰法。
f（n）= Ω（g（n））正式的数学定义：存在正常数c、n、n0，当n>n0的时，对于任意的f（n）对符合0<= c.g（n）<= f（n）。
直观视觉图如下所⽰：三、⼤θ表⽰法⽤于界定函数的渐进上界和渐进下界。
当f（n）= θ（g（n））的时候，代表着g（n）为f（n）的渐进紧确界。
⽽θ渐进描述符在所有的渐进描述符中是最严格的⼀个，因为它既描述了函数的上界，有描述了函数的下界。
算法导论中是如何描述⼤θ表⽰法的。
f（n）= θ（c.g（n））正式的数学定义：存在正常数c1、c2、n、n0，当n>n0的时，对于任意的f（n）对符合c1.g（n）<= f（n）<= c2.g（n），c1.g（n）、c2.g（n）都是渐进正函数（当n趋于⽆穷⼤的时候，f（n）为正）。
第一章测试1【判断题】(10分)一个问题的同一实例可以有不同的表示形式A.错B.对2【判断题】(10分)同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
A.错B.对3【判断题】(10分)问题的两个要素是输入和实例。
A.对B.错4【单选题】(10分)算法与程序的区别是（）A.有穷性B.确定性C.输出D.输入5【单选题】(10分)解决问题的基本步骤是（）。
（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明A.(3)(1)(5)(4)(2)B.(3)(4)(1)(5)(2)C.(1)(2)(3)(4)(5)D.(3)(1)(4)(5)(2)6【单选题】(10分)下面说法关于算法与问题的说法的是（）。
A.算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
B.证明算法不正确，需要证明对任意实例算法都不能正确处理。
C.如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
D.同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
7【多选题】(10分)下面关于程序和算法的说法正确的是（）。
A.算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B.程序总是在有穷步的运算后终止。
C.程序是算法用某种程序设计语言的具体实现。
D.算法是一个过程，计算机每次求解是针对问题的一个实例求解。
8【多选题】(10分)最大独立集问题和（）问题等价。
A.最大团B.稳定匹配问题C.区间调度问题D.最小顶点覆盖9【多选题】(10分)给定两张喜欢列表，稳定匹配问题的输出是（）。
A.完美匹配B.最大匹配C.稳定匹配D.没有不稳定配对10【单选题】(10分)问题变换的目的有（）。
(1)复杂变简单(2)未知变已知(3)隐式变显式(4)难解变易解（5）以上都是。
A.（5）B.（1）C.（2）D.（3）E.（4）11【单选题】(10分)按照霍纳法则，计算p(x)=a n x n+a n-1x n-1+…+a1x1+a0的数量级为____。
解忧书店 JieYouBookshop第一周基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界1单选(2分)考虑下述选择排序算法：最坏情况下该算法做次交换运算，这种情况在下列哪种输入条件下发生？A.数列所有元素均相等B.数列中有相同元素且递增（不减）有序C.数列元素各不相等且递减有序D.数列元素各不相等且无序正确答案：C你没选择任何选项2单选(2分)上述算法所执行的加法次数是：A.2n+1B.n-1C.2n-1D.n正确答案：C你没选择任何选项3单选(2分)已知是含有个元素并且从小到大排好序的数组，在中。
如果出现在中第个位置的概率是在前一个位置概率的一半，当充分大时，下述查找算法平均情况下的时间复杂度（）。
（只需给出近似值）A.nB.2C.3D.4正确答案：B你没选择任何选项4单选(2分)下列哪个排序算法在最坏情况下的时间复杂度最低？A.插入排序B.堆排序C.冒泡排序D.快速排序正确答案：B你没选择任何选项5单选(2分)下列有关阶乘函数的表述错误的是？A.B.C.D.正确答案：A你没选择任何选项6单选(2分)与之间的渐近关系是？A.B.无法确定C.D.正确答案：B你没选择任何选项7多选(3分)以下关于函数阶的关系中，哪几项是正确的？A.B.C.D.正确答案：A、C、D你没选择任何选项8填空(2分)下表给出组和函数，使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"") 正确答案：249填空(2分)下表给出组和函数，使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"") 正确答案：123510填空(2分)下表给出组和函数，使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")正确答案：2第二周基础知识（2）：序列求和方法，递推方程求解1单选(2分)递归方程的解的精确值是：A.B.C.D.正确答案：D你没选择任何选项2单选(2分)，的阶是：A.B.C.D.正确答案：B你没选择任何选项3单选(2分)请用主定理确定递归式的渐近的界：A.B.C.D.正确答案：A你没选择任何选项4单选(2分)给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。
