《算法之美》读书笔记

《算法之美》读书笔记

Helen-Han

在生活中，无论我们有无意识到，我们无时不刻不在利用算法，也许大部分是依靠感觉来判断。很多时候，因为我们对算法的模糊，我们不得不苦恼或者不得不浪费时间在某些事情上。

所谓算法，是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

如果我们在考虑问题时，清晰地了解我们所与之对应的算法，那么就可以更容易地解析问题或者更优地解决问题。

《算法之美》涉及到了11种常见的算法。掌握并熟练使用这些算法可有效地梳理思路，获得更优答案。

算法涉及到各种各样的问题。

平衡性问题，选择合适的平衡点可以事半功倍。

（1）最优停止理论中的37%法则，科学地验证了在单项线的遴选中，停止过早或过完，都会导致不理想的后果，而最佳平衡点37%可以获得更理想的答案。37%法则适用于恋爱、买房（火爆市场中）、停车、选拔等问题。

（2）探索与利用的平衡。生活就是在新鲜事物和传统事物之间、在最新和最棒之间、在勇于冒险和安于现状之间取得平衡。探索与利用问题类似于老虎机问题。此问题可以利用上限置信区间算法，确定目前掌握信息中的最高值（将任何答案数值化），并在未来中选择最可能产生的最高值。在探索与利用中，我们需要不仅要把握当前，同时还要把未来纳入我们的视野，不断尝试新鲜事物，增加我们发现最佳选择的机会。

排序性问题。排序是搜索的准备工作，排序的原因是避免未来花费太多时间在搜索上，因此排不排序，必须提前预估未来有无用途。

排序包括空间与时间的排序。

（1）在空间中，最常见的排序包括图书排序、体育比赛排序、和大数据的排序。如何减少排序的时间，其中的合并排序的分治算法和桶排序算法能够在大规模排序中取得优势。

（2）在时间中，我们可以采用最早到期日和最短加工时间的策略排列我们的任务。在这些策略中，会用到优先级反转和中断联合（尽可能长时间停留在一个任务上，而不是将你的反应降低到最低可接受的限度以下）等，来达到更合理的安排时间。

预测问题。

世界上有两种类型的事物：倾向于某种“自然”价值的事物，以及与之相反的事物。倾向于某种“自然”价值的事物大体遵循正态分度/高斯分布（预测规则为平均规则），如寿命。而与之相反的事物遵循幂律分布（预测规则为相乘法则）或厄兰分布（预测规则为相加规则），如城市规划和行人交通的建设模型中。当然良好的预测最开始要有良好的直觉，要能感觉到我们何时在处理一个正态分布，何时在处理一个密云分布。而良好的直觉需要我们保护我们的先验（如逻辑或一般经验过后的知识常识）丰富我们的知识，开阔我们的视野。

过度拟合问题。

有时我们认为数据越多就越好，但是有时对数据的过度崇拜，会使我们将重心放在能够测量的数据上而不是真正重要的问题上。中国的应试教育就是过度拟合的例子。当一个学校的标准化考试成绩上升，而在“非标准化”（利用抽查方式检测学生对知识点的掌握程度）方面的表现却在相反方向移动，管理人员应该意识到一个明确的警告--应试教育已经出现。而避免过度拟合的交叉验证和套索算法（惩罚复杂性）可以帮我们更好地避免过度拟合带来的不良后果。

当然还有很多其他常见的算法能帮助我们了解分析问题。如博弈论可以帮我们明确我们的判断是否符合事实，而不是是否符合共识；网络中的指数退避算法和和式增加积式减少算法（AIMD）可以帮助我们处理反复出现的同一问题和了解反馈沟通的重要性；随机性中的抽样算法、梅特罗波利斯算法和爬山算法可以帮助我们避免目光短浅招致的不优结果；约束松弛、持续松弛和拉格朗日松弛算法可以让我们在决绝问题上取得的进展……

但是，使用算法并不代表百分之百地获得最优的结果。即是最好的策略有时也会产生不好的结果。如果你遵循了最好的流程，那么你就已经尽了最大的努力，若过节过不顺心，我们也不必责备自己。

在苦难的情况下，最好的算法都是关于在最少的时间内做最合理的事情，这绝对是考虑每一个因素，并把每一次接受算都算到最后。

在复杂的生活中合理地运用算法，可以使我们变得容易一些，简单一些。