算法导论课后习题解析 第七章

算法导论课后习题解析 第七章
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码 

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说算法导论课后习题解析 第七章,希望能够帮助大家进步!!!

7.1-1

蓝色部分代表不大于pivot,红色部分表示大于pivot

13 19 9 5 12 8 7 4 21 2 6 11

13 19 9 5 12 8 7 4 21 2 6 11

13 19 9 5 12 8 7 4 21 2 6 11

9 13 19 5 12 8 7 4 21 2 6 11

9 5 13 19 12 8 7 4 21 2 6 11

9 5 13 19 12 8 7 4 21 2 6 11

9 5 8 13 19 12 7 4 21 2 6 11

9 5 8 7 13 19 12 4 21 2 6 11

9 5 8 7 4 13 19 12 21 2 6 11

9 5 8 7 4 13 19 12 21 2 6 11

9 5 8 7 4 2 13 19 12 21 6 11

9 5 8 7 4 2 6 13 19 12 21 11

9 5 8 7 4 2 6 11 13 19 12 21

7.1-2

当所有的元素都相同的时候q=r,这是因为该算法结束后有$a_q \lt a_i, \ (q \lt i \le r)$,所以没有任何元素会在A[q]之后。

将算法变成交替地将等于pivot的元素放到大小两个集合中,这样就能使得$q=\lfloor (p+r)/2 \rfloor$。

Partition(A, p, r) x = A[r] f = 0 i = p - 1 for j = p to r - 1 if x > A[i] or (f > 0 and x == A[i]) i = i + 1 exchange A[i] with A[j] f = f xor 1 exchange A[i + 1] with A[r] return i + 1

7.1-3

由于j从p变为r-1,而循环内的操作运行时间都与输入规模无关为O(1),循环共进行r-p次,所以总的时间复杂度为O(r-p)=O(n)。

7.1-4

只要把比pivot小的元素放到后边,把比pivot大的元素放在前边即可。

Partition(A, p, r) x = A[r] i = p - 1 for j = 1 to r - 1 if A[i] > x i = i + 1 exchange A[i] with A[j] exchange A[i + 1] with A[r] return i + 1

待续。。。

转载于:https://www.cnblogs.com/Jiajun/p/3157708.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29506

发表评论