1. 从“做事步骤”到“计算过程”这一节先回答一个最基本的问题什么叫算法。算法是一种定义良好的计算过程。它接收一个或一组输入经过有限个明确步骤在有限时间内产生一个或一组输出。也可以说算法就是把输入转换成输出的一套清楚规则。这里有三个关键词输入问题给定的数据过程一系列明确、可执行的步骤输出满足要求的结果所以算法不是“模糊的思路”而是能够真正执行的求解过程。2. 算法是在解决“计算问题”算法总是对应某个计算问题。一个计算问题先要说明输入是什么输出应该满足什么条件算法则负责给出一套具体方法使得每个合法输入都能算出对应的结果。例 1排序问题输入⟨a1,a2,…,an⟩ \langle a_1, a_2, \dots, a_n \rangle⟨a1​,a2​,…,an​⟩输出输入序列的一个重排并且满足从小到大有序。例如输入⟨31,41,59,26,41,58⟩ \langle 31, 41, 59, 26, 41, 58 \rangle⟨31,41,59,26,41,58⟩输出应为⟨26,31,41,41,58,59⟩ \langle 26, 31, 41, 41, 58, 59 \rangle⟨26,31,41,41,58,59⟩这个例子说明了一点算法不是为了“写程序”而存在而是为了把一个问题的输入输出关系真正实现出来。3. 正确算法是什么意思一个正确算法必须满足两个条件(1) 能停下来算法不能无限循环必须在有限时间内结束。(2) 结果是对的结束还不够输出还必须真的是这个问题的正确答案。所以判断一个算法至少要问两个问题它会不会停机它算出来的是不是对的因此正确算法可以理解为对每个合法输入都能在有限时间内停止并输出正确结果的算法。4. 一个问题通常不只有一种算法排序是最好的说明。同样是排序可以有很多不同做法。真正选择哪一种要看很多条件数据量大不大数据是不是已经部分有序元素取值有没有特殊限制机器结构是什么数据放在内存里还是磁盘里这说明算法不是“有没有办法做”而是“用什么方式做更合适”。也正因为这样后面才会学习复杂度分析。因为不同算法虽然都能解决问题但效率可能差得非常大。5. 算法不只出现在教材例子里算法的应用范围非常广。比如生物信息DNA 序列分析互联网路由选择、搜索电子商务公钥密码、数字签名资源分配把有限资源用在最合适的位置还可以看到一些具体问题最短路径给定地图或网络怎样从一个点走到另一个点并且总路程最短。拓扑排序如果一个零件依赖另一个零件应该按照什么顺序安排才能保证前置部分先完成。聚类根据相似性把对象分组例如辅助判断肿瘤更可能属于哪一类。压缩怎样用更短的编码表示信息减少存储空间。这些例子想说明一件事算法不是脱离现实的“数学游戏”而是很多系统真正工作的底层逻辑。6. 数据结构为什么会在这里出现这一节还专门提到数据结构。数据结构是组织和存储数据的方法。学习算法时不能把它和数据结构分开因为很多算法之所以快不只是步骤设计得好还因为数据放得对。例如查找时数组、链表、树的效率不同插入、删除时不同结构成本也不同所以可以先有一个直觉算法解决“怎么做”数据结构解决“数据怎么放”。两者通常是一起决定效率的。7. 不是所有问题都有高效算法有些问题我们知道高效算法比如最短路径。但也有些问题目前没有已知的高效精确算法。典型例子就是旅行商问题。这类问题提醒我们有时候可以求精确解有时候只能求近似解有时候重点不是“最优”而是“足够好且算得快”所以算法学习从一开始就不是“万能解法大全”而是在理解哪些问题容易哪些问题难难问题该怎么处理8. 配图9. 小结算法是定义良好的计算过程输入经过明确步骤在有限时间内变成输出。算法总是对应某个计算问题问题先规定输入输出关系算法再给出具体做法。一个正确算法必须同时满足能停机且结果正确。同一个问题通常有多种算法区别不只在能不能做出来更在效率和适用条件。算法广泛存在于排序、搜索、路由、加密、优化等现实场景中。数据结构和算法密切相关前者影响数据组织方式后者影响求解步骤。并不是所有问题都有高效精确算法算法学习也包含对“难问题”的认识。