算法正确性

我们在前面的文章中已经知道，算法只是对解决问题的步骤的一种精确描述，通常不依赖于程序员所使用的编程语言。

在算法与数据结构（1）：概念理解中，曾提到了煮方便面食谱，可以看成是一个算法。而这份食谱适合各个国家的人，不管使用什么语言（中文，英文，西班牙语或者罗马语等），都不会影响人们的使用。

但是最关键的一点是，这份食谱必须是正确的，就像算法一样，首先要正确，能够达到预期的结果并且能够解决你想要解决的问题。所以在使用一种算法之前，我们必须要去验证这个算法是否正确。在算法正确之后，我们就可以使用编程语言去实现它。

算法复杂度

算法正确之后，我们往往喜欢效率更高，速度更快的算法。因此我们要进一步的评估，就像煮方便面，我们需要更方便更高效的食谱，能够节约我们的时间。

要去评估算法的快慢，我们很多情况不可能实际去操作，因为有太多的因素需要控制。如果你想在电脑上进行评估，那么如果电脑的配置不一样呢，你的结果就没有价值。如果有些涉及到大型仪器运行的，难道你每次都要去操作这些机器来评估你的算法吗？很明显，这些都不是特别的靠谱，也不太现实。

因为种种的现实限制，计算机科学家就发明了算法复杂度这个概念。复杂度——Complexity，复杂，这里我们不是要强调算法的复杂，而是指出算法的效率，前面已经提到过。所以，算法复杂度，并不是来描述算法的复杂，而是用来描述算法的效率，是两回事。你会发现，有些算法理解起来很难，很复杂，但是复杂度却很低。

如果要用一句话来简单说明算法复杂度，那可以是：
“如果给实现了这个算法的程序一个大小为 N 的输入，那么这个程序将执行的操作的数目的数量级是 N 的一个怎么样的函数（f(N)）呢？”——引用自程序员联盟的文章

要更简单的来理解算法复杂度，那就可以量化成（函数）初始条件与算法执行时间之间的关系。

这里已经开始涉及到一些数学的概念。前面提到的操作，其实就是每一个步骤，比如煮方便面就包含很多个步骤，就是很多个Operation。那么我们到底要选出哪几个操作来进行度量，这个就需要具体问题具体考虑。比如在小鸭子那个例子中，你主要的时间就是花费在来回的路程上，其他都是基本不怎么耗费时间，也就是做这个时间可以作为用来度量算法复杂度。同样地，我们在煮方便面的时候，肯定也有几个步骤是比较耗费时间的，就可以选择这几部进行度量。

“渐进“度量

复杂度是算法的渐近行为的度量。看到这样概念理解，我也是有点懵圈。

当我们的输入（前面提到过）变得非常大，会有两种我们需要忽略：
一方面，有些时间是固定的，是常量，我们就不去考虑这些时间的比较。比如在小鸭子那个例子中，农夫打开车门的时间是固定不变的。
另一方面，常数乘法因子，比如N和2N我们就忽略2这个常数因子。我们看两种算法：
做N次（操作A）和做N次（操作B 然后操作C）
前一种算法是N次，而后一种算法是2N次。但是你没有办法去比较时间，这个取决去操作A，B，C各自需要的时间。因此，这些不一定对算法效率有影响的常数乘法因子不在复杂度的度量中考虑。

当然，有时候这样的忽略也不一定正确，比如有时候常数因子可能起到非常重要的作用。比如农夫完全没有办法打开门，那么就需要花费太多时间在开门上。但是，在大多数情况下，算法复杂度是算法性能的可靠指标。尤其是在输入非常大的时候，性能差距就会越来越明显。

算法真得还是有点难以理解，需要不断地去重复理解这个概念。