算法与正确性

复习

数据为什么需要组织：数据怎么摆，会直接影响各种操作的代价
抽象数据类型：它把接口和实现分开，便于替换
算法：算法关注步骤怎么走，和数据组织常常配合

TL;DR

算法是有限、明确、可执行的步骤，用来解决一类问题
合格的算法要正确，也要能在可接受的时间内完成
正确性需要论证，不能只靠“跑通几个例子”
把问题本身说清楚，是设计算法的前提

正文

　　数据结构解决“数据怎么摆”，接下来自然要问“步骤怎么走”。后者，就是算法（algorithm）。

算法是什么

　　一个算法，通常要满足几条朴素的品质：

有限：步骤是有限的，且一定会在有限步内结束
明确：每一步都清晰无歧义
可执行：每一步都是能真正做出来的操作
有输入输出：对给定输入，产生确定的输出

　　注意“有限”这一条有多重要。如果一段步骤永远停不下来，它就称不上算法——无论它看起来多聪明。

一个经典例子

　　求两个数的最大公约数，有个流传两千多年的方法——辗转相除法（欧几里得算法）：

当 b ≠ 0：
    (a, b) ← (b, a 除以 b 的余数)
答案就是最后的 a

　　比如求 48 和 18 的最大公约数：

48 ÷ 18 余 12，变成 (18, 12)
18 ÷ 12 余 6，变成 (12, 6)
12 ÷ 6 余 0，变成 (6, 0)
此时 b = 0，答案是 6

　　步骤简单，结果正确。

为什么它一定对

　　可“跑出来对”和“一定对”是两回事。我们凭什么相信，这个方法对任何两个数都成立？

　　关键在于一个事实：两个数的公约数，和“较小数”与“两数相除的余数”的公约数，是完全一样的。 也就是说，把 (a, b) 换成 (b, a mod b)，不会漏掉也不会多出任何一个公约数。既然每一步都保持“公约数集合不变”，而过程又在不断变小、必然终止，那么最终剩下的那个数，就是我们要求的最大公约数。

　　你看，正确的算法，背后往往有一条能讲清楚的理由，而不是碰巧试对了。