算法设计和分析作业.pdfVIP

算法设计与分析作业

姓名：学号：专业：

习题一

1-1函数的渐进表达式

22

3n+10n=O(n);

2nn

n/10+2=O(2);

21+l/n=0(l);

3

logn=O(logn);

n

10log3=O(n)

1-2O⑴和0(2)的区别

分析与解答：根据符号0的定义可知(1)=0(2)用(1)和(2)

表示同一个函数时，差别仅在于其中的常数因子

1-3按渐进阶排列表达式

分析与解答：按渐进阶从低到高，函数排列顺序如下：

2/32n

0(2)0(logn)0(n)0(20n)0(4n)0(3)0(n!)

习题二

算法分析题

2-27个二分有哪些信誉好的足球投注网站算法

分析与解答：(1)与主教材中的算法Binarysearch相比，数组段左、右游

标left和right的调整不正确，导致陷入死循环

(2)数组段左、右游标left和right的调整不正确，导致当x=a[n-l]时返回

错误

(3)数组段左、右游标left和right的调整不正确，导致当x=a[n-l]时返回

错误

(4)数组段左、右游标left和right的调整不正确，导致陷入死循环

()算法正确,且当数组中有重复元素时，返回满足条件的最右元素

(6)数组段左、右游标left和right的调整不正确，导致当x=a[n-l]时返回

错误

(7)数组段左、右游标left和right的调整不正确，导致当x=a⑼时陷入死

循环

2-26修改快速排序算法，使它在最坏情况下的计算时间为0(nlogn).

分析与解答：从一个无序的序列中随机取出一个值q做为支点，然后把大

于q的放到一边，小于q的放到q的另一边，然后再以q为分界点，分别对q的

两边进行排序(快排时直接再对q两边重新取支点，整理，再取支点，…直到支

点两旁都有序也就是支点两旁只有一个数时)

#includestdio.h

#includestdlib.h

intQsort(intp[],intbegjntend)

if(beg+l=end)return0;〃退出递归

intlow,hight,q;

low=beg;

hight=end;

q=p[low];〃q为支点，其实q可以为随机数但相应以下程序就要改了

while(l){

while(lowhightp[hight]q)hight-;

if(low=hight)brea;

p[low++]=p[hight];