2.3-1 以图2-4为模型,说明合并排序在输入数组A={3,41,52,26,38,57,9,49}上的执行过程。
|
|
|
|
3 |
9 |
26 |
38 |
41 |
49 |
52 |
57 |
|
|
|
|
|
|
3 |
26 |
41 |
52 |
& |
9 |
38 |
49 |
57 |
|
|
|
|
3 |
41 |
& |
26 |
52 |
|
|
|
38 |
57 |
& |
9 |
49 |
|
3 |
& |
41 |
|
52 |
& |
26 |
|
38 |
& |
57 |
|
9 |
& |
49 |
注:&为合并符号。
如果是 对数组 6,4,7,26,38,45,9使用插入排序呢?如下
|
|
|
|
4 |
6 |
7 |
9 |
26 |
38 |
45 |
|
|
|
|
|
|
|
4 |
6 |
7 |
26 |
& |
9 |
38 |
45 |
|
|
|
|
|
4 |
6 |
& |
7 |
26 |
|
|
|
38 |
45 |
& |
9 |
|
|
6 |
& |
4 |
|
7 |
& |
26 |
|
38 |
& |
45 |
|
|
|
=========================================================================
2.3-2 改写MERGE过程,使之不使用哨兵元素,而是在一旦数组元素L或R中的所有元素都被复制回数组A后,就立即停止,再将令一个数组中余下的元素复制回数组A中。
go语言实现的代码:
=========================================================================
2.2-3 利用数学归纳法证明:当n是2的整数次幂时,以下递归式的解是T(n)=nlgn。
最简单和常见的数学归纳法证明方法是证明当n属于所有正整数时一个表达式成立,这种方法是由下面两步组成:
递推的基础:证明当n=1时表达式成立。
递推的依据:证明如果当n=m时成立,那么当n=m+1时同样成立。
这种方法的原理在于第一步证明起始值在表达式中是成立的,然后证明一个值到下一个值的证明过程是有效的。如果这两步都被证明了,那么任何一个值的证明都可以被包含在重复不断进行的过程中。
http://baike.baidu.com/view/284458.htm
证明:
1、当n=2时,T(n)=2lg(2)=2成立。
2、假设当n=2^k(k>1)时,等式成立,即T(2^k)=(2^k)lg(2^k)=k(2^k);
又因为已知:n=2^k(k>1)时,有T(2^k)=2T((2^k)/2)+2^k,
所以:T(2^(k+1))= 2T((2^(k+1))/2)+2^(k+1)= 2T(2^k)+2^(k+1)= 2(k*(2^k))+2^(k+1)= (k+1)*2^(k+1)
3、所以,当n=2^(k+1) (k>1)时,等式也成立。即递归式的解确实为T(n)=nlg(n)。
============================================================================================
2.3-4:插入排序可以如下改写成一个递归过程:为排序A[1..n],先递归地排序A[1..n-1],然后再将A[n]插入到已排序的数组A[1..n-1]中去。对于插入排序的这一递归版本,为它的运行时间写一个递归式。
https://github.com/Airead/excise/blob/master/algorithms/excise/2.3-4.txt
伪代码:
递归式的答案比较糊涂,网上有几个版本:
n
T(n) = Θ(1) n=1 or 2
= T(n-1)+ Θ(n) n>2
https://github.com/Airead/excise/blob/master/algorithms/excise/2.3-4.txt
T(n) = T(n-1) + cn = T(1) + (n-1)cn = 1 + cn(n-1)
T(n) = O(n^2)
============================================================================================
2.3-5 回顾查找问题(参见练习2.1-3),注意到,如果序列A已排好序,就可以将该序列的中点与v进行比较。根据比较的结果,原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程,每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明:二分查找的最坏情况运行时间为Θ(lgn)。
2.1-3的试题如下:考虑下面的查找问题:
输入:一列数A=和一个值v
输出:下标i,使得v=A[i],或者当v不在A中出现时为NIL。
写出针对这个问题的现行查找的伪代码,它顺序地扫描整个序列以查找v。
利用循环不变式证明算法的正确性。确保所给出的循环不变式满足三个必要的性质。
二分查找最坏的情况是直到最后次二分也未找到相应的值,假设总量n等于2的k次方,即n=2^k,每二分一次k减1,当k=0时,之前一次为最后一次二分,即共执行了k次。而k=lg(n),所以,最坏情况的运行时间为Θ(lgn)。
============================================================================================
2.3-6 注意到2.1节中的过程INSERTION-SORT的第5~7行的while循环采用一种线性查找来(反向)扫描已排好序的子数组A[1..j-1]。我们可以使用二分查找(参见练习2.3-5)来把插入排序的最坏情况总运行时间改进到Θ(nlgn)吗?
在最坏情况下,二分查找的时间复杂度是 nlgn,但插入时数组移动的时间复杂度仍是 n2 。
故总体运行时间不能改善为 Θ(nlgn)。(但若排序中采用链表的数据结构,则可改善。)
插入排序的算法
二分法查找,但是数据插入仍然用之前方法,时间复杂度仍然是n^2
用链表的时间复杂度
============================================================================================
*2.3-7 描述一个运行时间为Θ(nlgn)的算法,给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好为x的元素。
算法思路1:
首先对S[1…n]进行非降序排序,然后设置两个指向标i=1,j=n,执行下面的操作:
S[i] + S[j] = X, 返回true
> X, j = j-1
如果 i>j 返回false
正确性说明:很显然,如果S[i] + S[j]那么这个S[a]一定要大于s[j],换句话说a要大于i,
另外一种情况是存在一个a,使得S[i] + S[a] = x,那么这个S[a]一定要大于s[j],换句话说a要大于j,
下面我们说明第二种情况不存在,在执行到j前,因为偏移量总是1,所以必然会执行到a,
这个时候在i之前的所有数,与S[a]相加是要小于X的,根据上面的公式,会移动前半段,即变动i,
直到到达i,所以不存在,同理可以说明>X的情况,因此如果算法返回false的话,
算法可以验证那么对于任意的i,都不存在j使得其和等于X
时间复杂度分析:排序为Θ(nlgn),之后为Θ(n),算法的时间复杂度为Θ(nlgn)
思路2:
思路3:
以算法导论上面的标准答案步骤是这样的:
1)将S中的元素排序。
2)构建另一个集合S‘={z:z=x-y , 其中y属于S}。
3)对S‘中的元素排序。
4)如果S中有元素出现多余一次,则移除多余的,只剩下一个。对于S’也移除重复的元素。
5)合并两个排好序集合S和S‘。
6)只要在合并好的集合中有同样的元素出现两次(它们必然在相邻的位置),则存在和为x的两个数。假定该元素为y,则另一个元素为x-y。
第1,3步所需时间为O(nlgn),2,4,5,6步所需时间为O(n)。所以总的时间为O(nlgn)。
============================================================================================
参考资料:
http://qiemengdao.iteye.com/blog/1328678
https://github.com/Airead/excise/blob/master/algorithms/algorithms.org
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
大家好,我是Edison。 上一篇,我们通过一个点菜的故事快速地了解了MES系统都能做哪些事儿《三分钟快速了解什么是MES系统》,相信大家都有了一个基本的感性认知。本篇,我们将时间拨回几十年前,了解一些MES的发展历程和标准体系。 MES系统的产生背景 在20…