自学内容网 自学内容网
自学内容网 > 正文

算法导论第二章

🕗 发布于 2024-11-16 01:56 排序算法  算法  

        从今天开始会陆续更新关于算法导论的啃书相关文章，先从前往后而且比较常用的章节开始讲起，所以可能会有部分不怎么用的着的章节会跳过。由于第一章没讲什么具体内容，所以选择跳过从第二章开始讲起。

2.1插入排序

       这张经典的插入排序打牌的图片也是来源于算法导论，关于插入排序的具体流程算法以及实现已经在前面进行介绍过了，所以这里不再对伪代码进行过多说明。接下来我们着重讲解一下这里的循环不变式，以及对插入排序的正确性的证明。

        我们知道在插入排序的过程中，每一次新的插入之前，前面的数组总是已经有序的，所以随着插入所有的数字就完成了排序，我们一般称这种为增量算法。而我们常常用循环不变式(loop invariant)来证明一个增量算法。一个循环不变式要满足下面三个条件：

1.初始化：循环的第一次迭代之前，它为真。

2.保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍然为真。

3.终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

        至于为什么循环不变式为什么是正确的可行的，本质上是一个数学归纳法。接下来我们利用这个循环不变式来证明插入排序的正确性。

1.初始化：当第一次循环的时候，数组只有一个元素，所以天然是有序的

2.保持：根据上面的伪代码可以知道，每一次循环都会把比新插入元素大的元素往后挪，从而让新插入的元素插入到一个正确的位置，使得数组有序，这也是显然的。

3.终止：由于循环终止的时候j=n+1，所以前n个元素已经变得有序，所以算法正确。

2.2分析算法

        在证明了插入排序的正确性之后，我们来分析插入排序这个算法。在分析之前，必须要有一个描述所用资源及其代价的模型，在这里我们采用一种叫做RAM（random access machine）随机访问机。在RAM模型中，每一条指令都是顺序执行的，没有并发操作，并且包括常见的指令：算数指令（加减乘除，取余，取整),数据移动指令（装入、存储、复制）和控制指令（子程序调用与返回等），像上述的每一条指令我们都看作所需时间为常量。接下来开始分析插入排序：

        每一行代码运行次数和代价都列在了右边，所以由上图我们可以相加得知：

最佳情况：

        当最好的时候也就是数组已经有序的时候，所以里层while循环只会判断一次，并不会执行while里面的语句，也就是tj = 1。所以上述式子就会退化成下面这个式子：

最坏情况：

        也就是数组逆序的时候，这是我们由tj=j，所以根据下面两个公式我们可以化简函数：

\sum_{j=2}^n{j} = \frac{n*(n+1)}{2} -1和 \sum_{j=2}^n{(j-1)} = \frac{n*(n-1)}{2}

平均情况：

        平均情况往往和最坏情况一样差，这里也不例外仍然是一个二次函数。

增长量级：

        当我们谈论增长量级的时候，我们会忽略低阶项和高阶项的系数，因为当n的值很大的时候这些都不重要。需要注意的是这里的高阶和低阶遵循高等数学中极限中的阶数比较，所以据此我们有T(n) = an^2+bn+c = \theta (n^2)。关于这块的具体细节会在下一章进行讲解以及给出精确定义。

2.3设计算法

 分治法：

        很多有用的算法都是递归的，而这些算法都遵循分治法的思想，分治法的主体思路如下：

1.将原问题分解为若干子问题，而这些子问题是原问题的规模较小的实例

2.解决这些子问题，递归地求解各子问题。如果子问题规模足够小 ，则直接求解

3.合并这些子问题的解成原问题的解

归并排序：

分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
解决:使用归并排序递归地排序两个子序列。
合并:合并两个已排序的子序列以产生已排序的答案。

需要注意的是这里有一个小的技巧可以借鉴，用来简化我们的代码，由于归并排序是一个分易合难的算法，所以我们举例分析一下合的步骤。在合并的时候，由于我们不知道哪一边数组已经合并完成，所以我们在每一个数组后面都放一个无穷大，这样就不用像原来那样再用if来判断，如下图：

由于归并排序已经在之前的文章中也实现过了，所以这里具体的实现细节不再讲解，我们注重于分析其正确性。我们注重分析一下合的过程为什么正确，由于第 12~17 行的 for 循环的每次迭代时，子数组按从小到大的顺序形成有序，所以又是一个增量算法，还是用循环不变式来证明。

初始化：当循环的第一次迭代之前，字数组为空，有k=p，所以显然成立。

保持：我们为了方便理解先假设if判断中的L[i]<= R[j]，这是L[i]是未被复制到A数组中的最小元素，所以当它复制到数组中之后，字数组将包含K-P+1个元素并仍然保持有序，所以依然成立。

终止：终止时K=r+1，根据循环不变式字数组A就是从小到大排完序之后的数组，除了两个哨兵位元素不录入以外，其他元素都已经复制回数组A。

分析分治算法：

        分析递归式的运行时间分为两个步骤：

1.假设T(n)规模为n的一个问题的运行时间

2.假设当规模n<=c可以直接解决，否则以D(n）的代价将原问题分为a个规模为\frac{n}{b}的子问题递归解决，最后以C(n）的代价进行合并，由此我们可以得到式子：

将分和合的代价带入上述式子就可得：

我们将递归树直接展开就可以求和得到总代价：

T(n)=(logn+1)*cn=\theta (nlogn)

再完成每一章的讲解之后我们会发布对该章节的习题合思考题的solution，仅供大家参考，谢谢


原文地址：https://blog.csdn.net/heixiu_heixiuhei/article/details/143693508

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024