我们面对一个 Problem，如排序问题时，我们会想到相应的候选算法如快速排序（Quicksort），归并排序（Merge sort）和堆排序（Heapsort）等，然后我们会去分析它们相应的时间复杂度和空间复杂度，以选取符合我们应用场景和需求的一个作为 Solution。
但在我们实现算法后，往往我们不知道或者不会去做的一步是证明算法的正确性。
为什么要证明算法的正确性
假设计算机运行速度无限快，内存无限大，那么是否还有必要学习算法呢？答案是肯定的，我们必须确保算法的正确性，否则无论你的算法运行得多么快，如果是错误的算法，得到错误的答案，那么一点用处都没有。
在实现算法后，我们可以写单元测试去验证它是否如期运行，写多种情况下的 test case。但对于某些算法我们不可能写出所有输入-期望输出对，例如一个排序算法接受一个 list 的参数，这个 list 的长度是为自然数的，也就是它可以为无穷大，因此单元测试实际上不可能覆盖所有输入-期望输出对。
而正确性可以从理论层面上证明算法在接受 domain 内任意输入后，能产生期望的正确的输出。
证明算法正确性的方法
算法内部计算使用的方式，一般有循环和递归，分别可以使用循环不变量和结构归纳来证明它的正确性，在未来几篇文章里会讲解它们的概念和用法。
网友评论