算法是什么？
非形式地说，算法(algorithm)是就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样算法就是把输入转换为输出的计算步骤的一个序列。
维基百科对于算法的定义是：“算法，在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法是有效方法，包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。” 算法中的指令描述的是一个计算，它执行时从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。包括随机化算法在内的一些算法，都包含了一些随机输入。
为什么要学习算法？
引用 Linux 内核核心开发者 Robert Love 在 Quora 上的回答：“数据结构与算法的良好基础不是对每个数据结构都知道细节怎么实现，都背下来大 O 复杂度和摊销复杂度，当然知道这些非常好，只是你在工作中很少用到它们，你的职业生涯里几乎不可能让你实现一个红黑树和节点删除算法。但是，你必须知道什么时候 BST(二叉排序树)对于一个问题是个有效的解法”，因此，学习算法的目的，是能够在遇到问题时，选择有效的解决方案。
算法能够解决什么问题？
算法的实际应用可谓比比皆是，当你在互联网上浏览信息时，算法能够为数据传输寻找好的路由；当你打开谷歌地图，算法能够为你确定最短路径；当你在网上进行交易，算法能够保证你的信息收到安全的保护，总而言之，一切可计算的问题都可以通过算法解决。
值得一提的是，许多有趣的算法问题都会有如下两个特征：
- 存在许多候选解，但绝大多数候选解都不能解决手头的问题，因此，需要寻找一个真正的解或一个最好的解，寻找的过程可能是一个很大的挑战。
- 存在实际应用。
算法好坏的衡量标准是什么？
衡量算法好坏的标准可以有很多维度，譬如内存消耗、计算能源消耗、CPU 寄存器资源消耗、通信带宽或计算机硬件，但是通常我们的衡量标准是计算时间。即求解相同问题时，不同算法之间的效率对比。
而在衡量计算时间时，一般会分析最坏情况运行时间，即对规模为 n 的任何输入，算法的最长运行时间。为什么？有如下三点理由：
- 一个算法的最坏情况运行时间给出了任何输入的运行时间的一个上界。知道了这个界，就能确保该算法绝不需要更长的时间。
- 对一些算法，最坏情况经常出现。
- “平均情况”的结果往往与最坏情况的结果大致一样。
在表达式方面，我们一般使用更简化的抽象来使过程的分析更加容易，即我们真正感兴趣的运行时间的增长率或增长量级。如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级，那么我们通常认为前者比后者更与效。
什么是算法分析？
维基百科对于算法分析的定义是：”在计算机科学中，算法分析是分析执行一个给定算法需要消耗的计算资源数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。算法分析是计算复杂度理论的重要组成部分“。
一般情况下，我们所讨论的算法分析，指在选择一种机器模型的前提下，用一种书写和处理都相对简单的方式（例如公式），表明算法资源需求的重要特征。
为什么要进行算法分析？
首先，算法分析能够解决经验分析的缺陷。算法是与平台无关的，算法性能的相对好坏，不能仅仅通过基于运行记录的经验来判断。其次，进行算法分析的过程，其实就是解决问题的过程。首先，我们可以根据待解决问题的特征，确定能够解决问题的几种候选算法，接着，通过分析几种候选算法，抛弃几个较差的算法，最后，对算法进行正确性分析，最终确定问题的解决方案。
如何确定算法的正确性？
循环不变式可以用来帮助我们理解算法的正确性。关于循环不变式，我们必须证明三条性质：
- 初始化：循环的第一次迭代之前，它为真。
- 保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
- 终止：在循环终止时，不变式为我们提供了一个有用的性质，该性质有助于证明算法是正确的。
前两条性质类似于数学归纳法，即为了证明某条性质成立，需要证明一个基本情况和一个归纳步。
第三条性质也许是最重要的，因为我们需要使用循环不变式来证明算法的正确性。
网友评论