HeJing(2008) School of Software
3
作业1
2. P32 1.5 ModSelectionSort 解： （a） ModSelectionSort算法赋值的最少次数为0次，在要排序的数
组中的所有元素已按非降序排序的情况下达到最小值。 （b） ModSelectionSort算法赋值的最大次数为3n(n-1)次，在要排序
n lim
f (n) g(n)
c 蕴涵着f (n) (g(n))
HeJing(2008) School of Software
5
作业1
P32 1.16 BubbleSort 解： （a）元素比较最少次数是n-1，当输入数组是非降序排列时，执行一
遍第4行语句，进行n-1次比较后得知后一个元素总是比前一个元 素要大，数组已排好序，sorted=true，则程序结束。 （b）元素比较最多次数是n(n-1)/2，当输入数组是降序排列时， while循环执行n-1次，元素比较次数总和为：n-1+n-2+…+1 （c）赋值主要来自于交换，元素赋值最少次数是0，当输入数组是非 降序排列时，不需要赋值。 （d）元素赋值最多次数是3n(n-1)/2，当输入数组是降序排列时， 每一次比较都要进行交换。 （e）算法运行时间为O(n2)，Ω(n) （f）由于算法运行时间与输入序列有关，从线性到平方排列，因此这 一算法不能用Θ表示。
算法作业解答
任课教师：何婧 Email: hejing@
School of Software, YunNan University
作业1
截至日期：9月21日 上传地址：ftp://113.55.4.20 文件名称：“学号－姓名－作业××” P32 1.1 1.5 1.13 1.16 1.31 硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争
解： n′=100n n12=100n2 求出 n1=10n n13=100n3 求出 n1 3 100 n 4.64n n1!=100n!
HeJing(2008) Scho仅用7次比较完成5个元素排序。请简要写出过程。 解：假设有a,b,c,d,e五个数 （1）2次比较，得到a<b, c<d，将元素分为s1={b,d}, s2={a,c,e} （2）b和d进行1次比较，若b<d,s1={b,d},否则s1={d,b} （3）若：b<d
（a）33 （b）7 （c）70 （d）77
解：根据二分搜索思想，算法最大比较次数为 log 60 1 6
具体分析： （a）33 ；查找次数为：6次，分别查找了40，25，32，36，34，33。 （b）7；查找次数为：5次，分别查找了40，25，17，13，11。 （c）70；查找次数为：6次，分别查找了40，55，63，67，69，70。 （d）77；查找次数为：6次，分别查找了40，55，63，67，69，70。
j 1
6
（a）第6步执行
log n
6 i2 15 log 2 n 70 log n log n(log n 1)(2 log n 1) 15 log 2 n 70 log n i 1
（b）要表示算法的时间复杂性用Θ更合适，因为用公式求出的值能够 得到算法的精确阶。
（c）算法的时间复杂性是Θ(log3n)
2n3+3n 100n2+2n+100
F
T
F
50n+logn 10n+loglogn
T
T
T
50nlogn
10nloglogn
F
T
F
logn n!
log2n 5n
T
F
F
F
T
F
n lim
f (n) g(n)
蕴涵着 f
(n)
O(g(n))
n lim
f (n) g(n)
0蕴涵着f (n) (g(n))
最多7次比较。
HeJing(2008) School of Software
9
作业2
截止日期：9月28日
对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2， n3 和n!的各算法，若用ABC公司的计算机能在1小时内解输入规模为n 的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为 多大的问题？
HeJing(2011) School of Software
2
作业1
1. P32 1.1 令A[1..60]=11,12,…,70，用算法 BinarySearch搜索下列x值时执行了多少次比较运算
a c e //s2中的元素与s1对应，有a<b, c<d （4）按分段逆序插入法：因为a<b，得到的已排序序列为a<b<d （5）e与b比较1次，若e<b，则e和a比，否则e和d比。2次比较得到
a,b,d,e已排序序列。 （6）最后，因为c<d，在当前的已排序序列中，d之前最多有3个元素，
最多经过2次比较就能找到c的合适位置。 （7）因此，5个元素排序，使用分段逆序插入法，无论元素如何排列，
的数组中的所有元素正好是降序排序时，需要的交换次数最多， (n-1)+(n-2)+(n-3)+…+1=n(n-1)/2。一次交换需要三次赋值，所以 赋值次数为3n(n-1)/2。
HeJing(2008) School of Software
4
作业1
P32 1.13
f(n)
g(n)
f=O(g) f=Ω(g) f=Θ(g)
HeJing(2008) School of Software
7
作业1
硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为 其竞争对手ABC公司同类产品的100倍。对于计算复杂性分 别为n，n2， n3和n!的各算法，若用ABC公司的计算机能 在1小时内解输入规模为n的问题，那么用XYZ公司的计算机 在1小时内分别能解输入规模为多大的问题？
HeJing(2008) School of Software
6
作业1
P32 1.31 算法Count4的时间复杂度
解：
第4行的j循环总是执行6次，第5行k的循环与i相关，为i2次，所以
第6行的执行次数为6*12+6*22+….6*(logn)2，根据P49求
和公式
n j2 n(n 1)(2n 1) (n3 )