个人兼职做网站,wordpress淘宝商城,推广网页模板,吉林网站建设电话第一章 转自http://www.cnblogs.com/batteryhp/p/4654860.html 思考题 1-1#xff08;运行时间的比较#xff09;确定时间t内求解的问题的最大规模。 上面是网上提供的答案。 注意点#xff1a; 1、最左边一列的是关于n的增长情况描述#xff0c;值得记住的是这些增长的排…第一章 转自http://www.cnblogs.com/batteryhp/p/4654860.html 思考题 1-1运行时间的比较确定时间t内求解的问题的最大规模。 上面是网上提供的答案。 注意点 1、最左边一列的是关于n的增长情况描述值得记住的是这些增长的排列顺序这是非常有用的啊数分学好了会很容易 2、注意1s内能处理的以n为增长量级的规模是10的6次方记住这个结果可以推导出其他增长量级的处理规模 3、注意这里的lg指的是以2为底的对数函数。 顺便做了一张lgn的增长图感受一下 本来想把n和nlgn画在一起可是效果不满意啊如下图 看得出nlgn比n增长的快不少啊貌似 第二章 2.1 2、重写INSERTION-SORT使之按照升序排列。 其实,只要将while步中的改成即可。 //INSERTION-SORT
for j 2 to A.lengthkey A[j]i j - 1while i 0 and A[i] keyA[i1] A[i]i i - 1A[i1] key 3、查找问题在数组中查找一个数线性查找写伪代码并证明循环不变式。 //find some value
for i 1 to A.lengthif v A[i]return ielse return NIL 4、两个二进制数存储在两个数组中将这两个数加和并将和存储到另一个数组中写出形式化描述并且写出伪代码。 写出代码(亲测有效) #include iostreamusing namespace std;
const int Num 10;int main()
{int a[Num] {1,0,1,1,0,1,1,0,1,1};int b[Num] {0,1,1,1,0,1,0,1,1,1};int c[Num 1] {0};int flag 0;int i;for(i Num-1;i 0;i--){c[i1] a[i] b[i] flag;if(c[i1] 1){c[i1] c[i1]%2;flag 1;}elseflag 0;}c[0] flag;for(i 0;i Num;i)cout c[i];cout endl;return 0;
} 2.2 1、theta(n^3) 2、排序一个n个数的数组规则是这样的将最小的跟第一个交换余下最小的的跟第二个交换…一直做下去一直到n-1这个算法叫做选择算法要求写出循环不变式和伪代码写出最好最坏运行时间的量级。 //选择算法伪代码
for i 1 to n - 1min A[i]for j i 1 to nif A[j] minmin A[j]exchange A[i] and min 下面是答案上的一种写法道理是一样的 另外最好和最坏时间要写一下。最好无非是已经排好了这时候也没用啊也要寻找最小值……所以最好最坏都是n^2. 3、考虑2.1-3的线性查找问题假定要查找的元素等可能地为数组中的任意元素平均需要检查输入序列的多少元素最坏情况又如何 解直观想法平均的话就是半数的元素数量最坏就是全部。可以这么想现在要从中选一个元素每个元素出现的概率是1/n需要检查的个数分别为1个2个...n个那么取期望就是123...n/n 为(n1)/2个元素最坏情况就是n个没什么好说的。换句话说都是theta(n)的复杂度。 按照答案上的说法由于一般时间在前一半数组中寻找一半时间在后一半数组中寻找那么那么平均下来就是中间那个值喽~~ 4、我们可以如何修改几乎所有的算法可是使之有最好的运行时间 解想法就是最好的输入呗。。。看一下答案One can modify an algorithm to have a best-case running time by specializing it to handle a bestcase input efciently.哦。。。 2.3 2、重写MERGE当L或者R为空时把另一组的数据全部复制到A中。 //MERGE 伪代码
n1 q - p 1
n2 r - q
Let L[1..n1] and R[1..n2] be new arrays //由于不需要“哨兵牌”无需多出一个元素
for i 1 to n1L[i] A[p i -1]
for j 1 to n2R[j] A[q j]i 1
j 1for k p to rif i n1 //在这里加两个判断while j n2A[k] R[j]k k 1 //不要忘了将k和j递增这里的k和j得分开递增j j 1breakif j n2while i n1A[k] L[i]k k 1i i 1breakif(i n1 and j n2) //注意这里的条件判断不能直接将二级的if else 拿上来否则混乱 if L[i] R[j]A[k] L[i]i i 1else A[k] R[j]j j 1 //没有“哨兵牌”的代码 #include iostream
#include time.hvoid MERGESORT(int*, int,int);
void MERGE(int*,int,int,int);using namespace std;int main()
{clock_t start, end;start clock();int i;int* arr new int[100];for (i 0; i 100; i){arr[i] 100 - i;}MERGESORT(arr,0,99);for (i 0; i 100; i){cout arr[i] ;if (i % 10 9){cout \n;}}delete[]arr;cout __________________ endl;end clock();cout Run time: (double)(end - start) / CLOCKS_PER_SEC s endl;return 0;
} void MERGESORT(int* a, int p, int r)
{int q;if (p r){q (p r) / 2;MERGESORT(a, p, q);MERGESORT(a, q 1, r);MERGE(a, p, q, r);}
}void MERGE(int* arr, int p, int q, int r)
{int n1 q - p 1;int n2 r - q;int* Left new int[n1];int* Right new int[n2];int i, j;for (i 0; i n1; i)Left[i] arr[p i];for (j 0; j n2; j)Right[j] arr[q j 1];i 0;j 0;for (int k p; k r; k){if (i n1){while (j n2){ arr[k] Right[j];k;j;}break;}if (j n2){while (i n1){ arr[k] Left[i];k;i;}break;}if (i n1 j n2){if (Left[i] Right[j]){arr[k] Left[i];i;}else{arr[k] Right[j];j;}}}delete []Left;delete []Right;} 3、利用数学归纳法证明下面的式子成立其中T(n)nlgn: 证明: (1)基本情况n 2时T(n)2lg22成立 (2)假设当n 2^k 时成立即T(2^k) (2^k)lg(2^k),下面证明当 n 2^(k 1)时成立。T(2^(k1)) 2T(2^k)2^(k1)2((2^k)lg(2^k))2^(k1)2^(k1)(lg(2^k)1)2^(k1)(lg(2^k)lg2)2^(k1)(lg(2^k * 2))2^(k1)(lg(2^(k1))),n2^(k1)时也成立。 4、我们可以把插入排序表示为以下一个递归过程。为了排序A[1..n],递归地排序A[1..n-1]然后把A[n]插入到已经排序的数组A[1..n-1]中。为插入排序的这个递归版本的最坏情况写一个递归式。 解我们考虑最倒霉的情况在插入排序中原数组是按照倒序排列的那么每次有一个新的数就得让它跑到已经排好的数组的最前面……那么新插入一个元素时的时间复杂度就是theta(n)因为总要比较n-1次再加上判断下标不越界复杂度就是n了 5、回顾查找问题2.1-3注意到如果A已经被排序了那么新的值v可以先与A的中间元素进行比较那么根据比较的结果原数组中的一半就可以不再考察了。二分查找算法就是不断重复这个过程每次的序列数量减半。写出二分查找的迭代或者递归的伪代码并且证明最坏运行时间为theta(lgn). 解需要注意的是被查找的数组必须是已经排序好的数组。 //递归版本的二分查找
BINARYSEARCH(A,v,p,r)
if p r and A[p] ! vreturn NIL
else q (p r)/2if A[q] vreturn qelse if A[q] vreturn BINARYSORT(A,v,q1,r)else return BINARYSORT(A,v,p,q-1) //递归版本二分查找代码 #include iostream
#include time.husing namespace std;int Binarysearc(int*, int, int, int);int main()
{clock_t start, end;start clock();int* arr new int[100];int v 70;for (int i 0; i 100; i){arr[i] i;}int position Binarysort(arr, v, 0, 99);cout position endl;delete[]arr;cout __________________ endl;end clock();cout Run time: (double)(end - start) / CLOCKS_PER_SEC s endl;return 0;}int Binarysearch(int* arr, int v, int p, int r)
{if (p r arr[p] ! v)return -1;else{int q (p r) / 2;if (arr[q] v)return q;else if (arr[q] v)Binarysort(arr, v, q 1, r);elseBinarysort(arr, v, p, q - 1);}} 关于迭代版本 //迭代版本的二分查找
A is a array
v is a value
p,r are the min and max index of A
ITERATIONSEARCH(A,v,p,r)while(p r)q (p r)/2if A[q] vreturn qelse ifv A[q]r qelsep qreturn NIL //迭代版本的二分查找 #include iostream
#include time.husing namespace std;int Iterattionsearch(int*, int, int, int);int main()
{clock_t start, end;start clock();int* arr new int[100];int v 70;for (int i 0; i 100; i){arr[i] i;}int position Iterattionsearch(arr, v, 0, 99);cout position endl;delete[]arr;cout __________________ endl;end clock();cout Run time: (double)(end - start) / CLOCKS_PER_SEC s endl;return 0;}int Iterattionsearch(int* arr, int v, int p, int r)
{while (p r){int q (p r) / 2;if (arr[q] v)return q;else if (arr[q] v)p q 1;elser q - 1;}} 下面考察其最坏时间的复杂度 元素个数为n的数组最坏需要除2*lgn次2才会得到结果故最坏时间复杂度为theta(lgn).这样考虑m分查找其时间复杂度为m*lgm(n).lgm是以m为底的对数函数那么对于给定的nm是多少时时间最短呢做了一些实验表明m3的时候函数m*lgm(n)最小或者说时间复杂度最低但是效率据说不是最高的。有空试一试~ 6、在插入排序中对于已经排好序的A[1..n-1]需要线性扫描这个已经排好的序列。现在要对插入排序进行优化将这个线性排序的部分改成二分查找的方式使最坏时间变为theta(nlgn)(原来是theta(n^2))如何实现呢 解第一想法不可能吧…毕竟需要一个一个往后挪位置啊…… yep看了看其他人的答案确实是这样的即使可以使用二分查找找到位置但是后面移位的过程时间复杂度仍然是theta(n),整体的复杂度还是theta(n^2). 7、请给出一个复杂度为theta(nlgn)的算法给定n个整数的集合S和另一个整数x该算法能确定S中是否存在两个其和刚好为x的元素。 解自己的想法先排序归并排序然后第一个数从前面开始找那么x减去这个数的结果就是需要找的数再用二分查找去找这个数总的复杂度就是theta(nlgn). yep,看了下答案确实是这样。 截图一下 思考题 2-1在并归排序中对小数组采用插入排序虽然归并排序的最坏运行时间是theta(nlgn)而插入排序的最坏运行时间是theta(n^2)但是插入排序中的常数因子可能使得在n较小时运行时间更短。因此在并归排序中当子问题编的足够小时采用插入排序使得递归的叶变粗是有意义的。考虑对归并排序的修改其中使用插入排序来排序长度为k的n/k个子表然后使用标准的合并机制来合并这些子表这里k是一个特定的值。 a.证明插入排序最坏情况可以在theta(nk)时间内排序每个长度为k的n/k个子表。 b.表明在最坏情况下如何在theta(nlg(n/k))时间内合并这些子表。 c.假定修改后的算法的最坏情况运行时间为theta(nknlg(n/k))要使修改后的算法与标准的归并排序具有相同的运行时间作为n的一个函数借助theta记号k的最大值是什么 d.在实践中我们应该如何选择k 解:打完上面的思考题感觉……跟练习题不是一个次元的卧槽太有挑战性。 a.证明每个子表的时间复杂度为theta(k^2)共有n/k个子表故总时间为theta(nk). b.n/k个列表两两合并合并完继续合并共需要lg(n/k)层每层时间复杂度均为theta(n)所以合并共需要theta(nlg(n/k))的时间。 c.标准的归并排序的时间复杂度为theta(nlgn)需要theta(nlgn)theta(nknlg(n/k))这时候k的最大值只能是ktheta(lgn). d.k的选取标准是长度为k的子列插入排序要比归并排序快。额这么说好像不负责任。。。这里需要用纸来演算一下 网上有一个答案可能靠谱这是个实验问题应该在k的合法范围内测试可能的k用T-INSERTION-SORT(k)表示k个元素的插入排序时间T-MERGE-SORT(k)表示k个元素的合并排序时间。该问题等价于测试求解T-INSERTION-SORT(k)/T-MERGE-SORT(k)比值最小的k值。 下面这段话来自http://blog.kingsamchen.com/archives/715 由反证法可以得到k的阶取值不能大于Θ(logn)并且这个界可以保证插排优化的渐进时间不会慢于原始归并排序。 由于对数函数的增长特点结合实际排序规模k得实际取值一般在10~20间。 在归并中利用插入排序不仅可以减少递归次数还可以减少内存分配次数针对于原始版本。 ps.需要对比验证一下。 2-2冒泡排序的正确性冒泡排序是一种流行但低效的排序算法它的作用是反复交换相邻的未按次序排列的元素。 //冒泡排序伪代码 BUBBLESORT(A)
for i 1 to A.length -1 for j A.length downto i 1if A[j] A[j - 1]exchange A[j] with A[j - 1] a.假设A’是BUBBLESORT(A)的输出。为了证明BUBBLESORT正确我们必须 证明它将终止并且有 A[1] A[2]... A[n] (2.3) 其中nA.length.为了证明BUBBLESORT确实完成了排序我们还需要证明什么下面两部分将证明不等式(2.3)。 b.为第二层的for循环精确地说明一个循环不变式并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式的结构。 c.使用(b)部分证明的循环不变式的终止条件为第一层说明一个循环不变式这个不变式就能证明式子(2.3)。证明中应该使用本章中给出的循环不变式证明的结构。 d.冒泡排序的最坏情况运行时间是多少与插入排序的运行时间相比性能如何 解 b.第二层循环使得将未排序的数组中最小的一个移动到最前面。 初始jn子数组为A[j-1..n]A[n-1..n]有两个元素。在循环内部通过条件交换语句可以保证A[n-1] A[n]成立。因此A[j-1]是A[j-1..n]中的最小元素。
保持每次迭代开始时A[j]是A[j..n]中的最小元素。在迭代操作中当A[j] A[j-1]时交换因此总有A[j-1] A[j]。可知本次迭代操作完成后A[j-1]一定是A[j-1..n]中的最小元素。
终止ji1时退出因此结束时A[i]一定是A[i..n]中的最小元素。http://blog.csdn.net/cppgp/article/details/7161701 c.第一层循环使得不断增加已经排序好的数组元素知道全部排好。 初始i1是A中的第一个元素因此内部循环完成后可以保证A[1]中保存A[1..n]的最小元素。
保持每次递增i时执行内部循环因此A[i]中保存A[i..n]中的最小元素。可知每次内部循环完成后都有 A[1] ≤ A[2] ≤ ... ≤ A[i]
终止ilength[A]时终止此时有 A[1] ≤ A[2] ≤ ... ≤ A[n]。转自http://blog.csdn.net/cppgp/article/details/7161701 d.两个的最坏运行时间都是theta(n^2)但是在插入排序中最好的时间可以达到theta(n),冒泡排序一直是theta(n^2). 2-3(霍纳(Horner)规则的正确性)给定系数a0,a1,a2,…,an和x的值代码片段 y 0
for i n downto 0y ai xy 实现了用于求值多项式 的霍纳规则. ps.在中国这个算法叫做秦九韶算法。 a.借助theta符号实现霍纳规则的以上代码片段的运行时间是多少 b.编写伪代码来实现朴素的多项式求值算法该算法从头开始计算多项式的每项。该算法的运行时间是多少与霍纳规则相比其性能如何 c.考虑以下循环不变式 在第2-3行for循环每次迭代的开始有 把没有项的和式解释为等于0.遵照本章中的循环不变式证明的结构使用该循环不变式来证明终止时有 d.最后证明上面给出的代码片段将正确地求由系数a0,a1,a2,a3…,an刻画的多项式。 解啊啊啊多项式求值的问题原来换一种写法就是一种新规则霍纳规则。 a.这应该是theta(n吧……很显然的n次多项式用到n次加法n次乘法。 b.伪代码如下 //多项式一般求解伪代码
y 0
for i 1 to nbase 1for j 1 to i base base*xy y ai*base
y y a0
return y 上述伪代码的复杂度是theta(n^2)123…n显然霍纳规则比一般算法好得多霍纳算法是theta(n)啊那么问题来了霍纳算法节省了哪一部分的运算呢还能不能更简化呢 自己想一想一般的算法重复计算了好多次x的乘方每一次乘方都需要重新计算而霍纳算法通过改变计算顺序成功避免了这一问题trick在哪里还没想明白。我想到一个办法一般算法的每次结果存起来再用这样的复杂度也是theta(n),不过这也有存储的问题伪代码 //多项式改进伪代码
y 0
arr[n1]
arr[0] 1
for i 1 to n arr[i] a[i-1]*xy y ai * arr[i]
y y a0
return y c.题目的叙述是对的进行了验证除了第一步遇到-1次项外感觉比较巧妙利用循环不变式可以证明。 初始iny[n] 0迭代开始时循环后有y[n] a[n]。
保持对于任意 0 ≤ i ≤ n循环后有y[i] a[i] y[i1] * x a[i] (a[i1] * x a[i2] * x ... a[n] * x^(n-(i1))) * x a[i] a[i1] * x a[i2] * x^2 ... a[n] * x^(n-i)
终止i小于0时终止此时有 y[0] a[0] a[1] * x a[2] * x^2 a[n] * x^n证明和y Σ a[ki1] * x^k的关系k 从0到n-(i1)等价于 0 ≤ k ≤ n-(i1)。因此y Σ a[ki1] * x^k a[i1] a[i2] * x ... a[n-(i1)i1] * x^(n-i) a[i1] a[i2] * x ... a[n] * x^(n-i)由于i1循环之后和i循环之前的值相等用y[i]表示i循环之前的值则有y[i] y[i1]霍纳规则循环不变式的结果表明y[i] a[i] a[i1] * x a[i2] * x^2 ... a[n] * x^(n-i)因此有y[i] y[i1] a[i1] a[i2] * x ... a[n] * x^(n-(i1))令kn-(i1)则nki1所以y[i] a[i1] a[i2] * x ... a[ki1] * x^(ki1-(i1)) a[i1] a[i2] * x ... a[ki1] * x^k用y表示y[i]则有y a[i1] a[i2] * x ... a[ki1] * x^k Σ a[ki1] * x^k其中 k从0到n-(i1)证毕。转自http://blog.csdn.net/cppgp/article/details/7161701 上面的证明很细致再次感谢。 d.这一步把循环不变式写到0就可以了c中已经证明了在第二个证明里。 2-4逆序对假设A[1..n]是一个有n个不同数的数组。若 i j 且 A[i] A[j]则对偶(i,j)称为A的一个逆序对(inversion)。 a.列出数组2,3,8,6,1的5个逆序对。 b.由集合{1,2,…,n}中的元素构成的什么数组具有最多的逆序对它有多少逆序对 c.插入排序的运行时间与输入数组中逆序对的数量之间是什么关系证明你的回答。 d.给出一个确定在n个元素的任何排列中逆序对数量的算法最坏情况需要theta(nlgn)时间。提示修改归并排序 解; a.说白了就是前面比后面大那么就有 (1,5),(2,5),(3,4),(3,5),(4,5). b.啊啊啊都让开让我来回答这个题 哈哈大家记不记得高等代数里面在讲矩阵按行或者按列展开的时候每一项的正负号怎么决定的--对了就是-1的这个元素(所在行所在列)次方好像跟这个题没什么关系哈。。。不过下面这个就很有关系了在近世代数里面在学对换群的时候接触过这方面的内容好吧我忘了是哪一块内容了待我查查或者问问别人。。 那么这个题目呢显然数组逆序排的时候逆序对最多啦~~最多的个数呢就是 从右向左数 123…n-1n(n-1)/2对。 c.这个问题用归纳法想一下没有逆序对的时候时间是n逆序排的时候是n^2那么中间呢啊是这样移动的次数不用考虑只要考虑比较的次数就可以了比较的越多移动的就越多这个比较的次数决定了插入排序的运行时间而且造成比较的原因就是逆序对了所以对于已经排好的A[1..n-1]而言A[n]比A[1..n-1]中小的个数就是比较的次数其实应该是比较次数-1这么说来从第一个数开始想总的逆序对数目就是需要进行比较的总数了。 d.想了半天由于合并总共lgn层那么每一层求逆序对的复杂度就是n从网上看了几个答案好像没有几个好好写的找到了一个挺好说一说想法。加入左右两个子数组已经排好序那么只要从右面数组中选出一个那么现在左边数组中对应的剩下的那一部分都比刚才从右边选出的大那么对应的逆序对就多出左边剩下元素的数量那么多个。ps.在此问题中在子序列合并之前每一个排好的子序列自身数组中的逆序对已经在上一步求出合并的过程是在求子序列之间的逆序对数量。 inversions 0 //全局变量 COUNT-INVERSIONS(A,p,r) if p rq p r/2COUNT-INVERSIONS(A,p,r) COUNT-INVERSIONS(A,p,r) MERGE-INVERSIONS(A,p,q,r) MERGE-INVERSIONS(A,p,q,r)
n1 q - p 1
n2 r - q
let L[1 : : n1 1] and R[1 .. n2 1] be new arrays
for i 1 to n1L[i ] A[p i - 1]
for j 1 to n2R[j] A[q j]
L[n1 1] ∞
R[n2 1] ∞
i 1
j 1for k p to rif L[i] R[j] A[k] R[i] inversiongs inversiongs n1 – i 1 i i 1else A[k] R[j] j j 1 思想转自http://www.cnblogs.com/lilith/archive/2012/11/21/2780319.html自己作了修改。上面的算法还需要程序验证这是下一步的工作下一步要把前面提到的伪代码实现一遍。这一篇写的太长了。转载于:https://www.cnblogs.com/mhpp/p/7657640.html
