算法导论——算法基础
算法导论在学习计算机专业的人心中一直是圣经般的存在。虽然我也阅读过一些数据结构与算法相关的书，但是一直没有机会阅读算法导论。这次当当买书半价，我就下单了算法导论。有可能又会放在书架上当作收藏，但是还是开一个坑，希望能抽时间阅读完这本书，并记录自己的学习过程。 首先第一篇博客，来简单介绍下前两章的内容。第一章是算法在计算中的应用，第二章是算法基础，这些都属于基础知识。算法在计算中的应用，就不必多提了。实际上我们在计算机上的几乎所有操作都离不开算法。选择低效的算法可能干几十年也完成不了的事情，如果运用高效的算法可能几天就能解决。因此我们想设计的是高效的算法。而一个正确的算法，需要对每个输入实例都给出正确的答案，因此它具有有穷性，不会永无休止的计算。 ### NP完全问题 ### 提到算法，还必须提到的就是一个NP完全问题。NP完全问题是计算领域最重要的难题，也不知道在有生之间能不能看到它的解决。NP完全问题到目前为止，没有给出一个有效的解决算法，但是也没有哪个证明，证明出这个有效算法是不存在的。著名的“旅行商”问题就是NP完全问题。实际上我们在学习过程中也会经常遇到NP完全问题，例如机器学习中对于0范数的优化。很多时候如果我们能证明一个问题是NP完全问题，就可以少花功夫，去漫无目的地寻找绝对有效的算法，而是选择设计一个近似算法。
NP完全问题集合有一个特点，那就是只要证明一个NP完全问题有有效的解决方法，那么任何NP完全问题都有有效的算法。这使得NP完全问题非常诱人，解决一个就解决无数个问题。
另外，尽管有很多NP完全问题我们目前还找不到有效地算法，但是近似算法往往不难，可以给出一个距离最优解不远的近似解。例如我们将0范数放宽到1范数，等等。
最坏情况与平均情况
下面就要说到对算法的分析了。分析一个算法的复杂度非常重要，我们在知道数据量的情况下，可以大概估算出算法的运行时间。当然这个时间不是绝对精确的，但是依然有很大的帮助。因为有很多低效的算法，如果想要等待一个结果出来，可能需要几个小时甚至几天，而我们可以根据复杂度的分析来选择及时退出，或者在等结果的这段时间内去喝杯咖啡，或者出去游玩等等。
一般来说，我们分析一个算法的复杂度（主要是时间复杂度），往往是分析它的最坏情况。对算法的分析有最坏情况，平均情况与最好情况。举个例子，比如插入排序算法（从小到大），是一个比较低效的排序算法。对于一个序列\(<a_1,...,a_n>\)，我们从索引2开始，将它插入到左边已经有序的序列的正确位置。为了找到正确的位置，需要从右往左依次对比，来找到第一个比它更小的数。最好的情况，算法已经有序，每次只要一个比较，也不需要交换操作，最坏的情况，算法是反向排序的，每次都要比较到第一个位置，比较的个数是子数组的全部。而平均情况下，比较次数是子数组的一半。从这里，我们就能看出来为什么分析要分析最坏的情况了： 1. 最坏的情况是一个底线，分析最坏情况，那么可以保证算法实际效率一定比最坏的要好 2. 平均情况往往与最坏的情况相差不多，要理解这个，我们需要介绍增长量级的概念。 3. 还有一个原因就是，最好的情况并不一定会出现，但是最坏的情况可能往往会出现，例如在数据库中查找一个不存在的词条。
但是对于一些特定的问题，平均情况也并不具备代表性。在学习统计以及概率之后，往往能通过分析，对一些随机化算法，往往能给出一个期望值。如果最坏的情况很少发生，而大多数时候这个问题都可以被快速解决，那也不失为一个很好的算法。这种情况不在我们这里的讨论范围内，但是对于之前压缩感知的内容，用低纬来恢复高维，实际上就是这种概率分析很好的体现。 ### 增长量级 ### 增长量级是分析的关键，因为在数据量很小的情况下，例如对10个数字排序，不管是插入排序还是快速排序，都是一眨眼的过程罢了。我们更注重的是在数据量\(n\)变大的时候，需要时间的增加的幅度有多快。因此我们往往只关心最高次的内容。如插入排序： 1. 最好情况下，\(n\)次排序需要\(n\)次比较，那么比较次数就是\(n\) 2. 最坏情况下，需要\(1+2+3+...+n-1\)次比较，那么比较次数是\(\frac{n(n-1)}{2}\) 3. 平均情况下，需要次数是\(\frac{1}{2}\cdot\frac{n(n-1)}{2}\)
由于我们更关心增长的速度，因此可以忽略系数以及其他次，只关注最高次，那么最坏情况与平均情况增长量级都是\(n^2\)，记为\(\Theta(n^2)\)。这也就解释了上面的第二条，平均情况与最坏情况往往相差不多。
设计算法
这里主要说明增量法和分治法。插入排序就是典型的增量法，它对已经有序的子序列\(A_1,...,A_j\)进行插入，使得子序列变为\(A_1,...,A_{j+1}\)。而另外一种非常有效的思想是分治法，将大的问题拆分成小问题，然后合并。
遵循分治法的算法都有下面3个步骤：分解，解决，合并。基于分治的思想，另外一种排序算法————归并算法就诞生了。归并算法分为自上而下与自下而上，但是本质都是分治的思想。自上而下，将一个大的序列分成两个，再将子序列继续分，直到一个序列元素个数小于等于2，这时候根据大小交换次序后，开始合并。对两个有序序列的合并是非常快速地，时间复杂度为\(n\)，而基于这种分治策略，对所有元素进行合并需要\(\log _2 ^n\)次，因此归并算法的复杂度为\(\Theta(n\log n)\)。而自下而上也基本一样，只不过一开始就将序列两两分组，之后在合并罢了。因此自上而下更容易写成递归的形式。
分治法是一个非常重要的思想，实际上我们在生活中的很多问题，都可以使用分治法解决。
上述就是阅读前两章后记录的内容。实际上大多数都很简单，因为真正难得部分还在后面，以及各种数学分析。这两章的课后题我也没有多看，对于课后的内容有时间的话我会认真分析。虽然数学太重要了，分析得到一个正确结果往往是人生非常美妙的过程，但是往往一个数学分析需要消耗比较长的时间，因此这系列内容主要还是理解使用各类算法，而对于数学的证明分析优先级次之。