如何学习算法

在不知其所以然的情况下，算法只是一堆离散的机械步骤，缺少背后的思想的支撑，
这些步骤之间就没有一个本质层面上的关联（先知亚里士多德早就指出：学习即联接）。
所以就跟背历史书也没多大区别。然而，知道了算法是怎样一步步被推导出来的，我们就一下拥有了大量的记忆提取线索：
对算法发现过程中的任何一个关键步骤（尤其是本质）的回忆都可能使我们能够自己动手推导出剩余的内容。

譬如你知道堆(heap)是怎样由朴素的决策树演化而来的，它又是为了解决什么问题的，你即便忘
记了具体的细节，也可以自己推导出来。

譬如你知道KMP算法的本质在于消除回溯，至于如何消除回溯却并不是那么难以推导的，所以即便
忘了也可以借助于大脑的逻辑演绎能力再现出来。

譬如你知道Tarjan算法其实只是从后序遍历经过两个优化调整而来的（其中并査集的使用其实只
是优化手段——为了能够迅速判断祖先节点是谁——而非算法本质 ——

当然，算法设计的主要任务本来就是通过问题条件中蕴含的知识来“消除冗余计算”和“避免不必要计算”，
所以你也可以说并査集的使用是关乎本质的，只不过，知道了为什么需要引入并査集，就会强烈地感觉
到一切是顺理成章的了），那这个出了名的绕人的算法也就不那么难以理解和记忆了。

譬如你知道排序的本质，就能够对什么是最优排序，为什么它是最优排序有深刻的认识。

揣摩的重要性，是怎么说都不为过的。揣摩的一些指导性的问题有：为什么要这样（为什么这是好的）？
为什么不是那样（有其它做法吗？有更好的做法吗？）？这样做是最好的吗？（为什么？能证明吗？）
这个做法跟其它的什么做法有本质联系吗？这个跟这个的区别是什么？问题的本质是什么？
这个做法的本质又是什么？到底本质上是什么东西导致了这个做法如此..？与这个问题类似的还有其它问题吗？
（同样或类似的做法也适用吗？）等等。

猜数：用二分法： 本质：为什么这种策略具有最优下界？答案也很简单，这个策略是平衡的。
这种策略的本质可以概括成“让未知世界无机可乘”。
二分搜索为什么好，就是因为它每次都将可能性排除一半并且无论如何都能排除一
半（它是最糟情况下表现最好的）。

称球：指导思想——你选择的称法必须使得当天平平衡的时候答案剩下的可能性和天平左倾（右倾）的
时候答案剩下的可能性一样多。实际上，这等同于你得选择一种称法，使得天平输出三种结果的概率
是均等的，因为天平输出某个结果的概率就等同于所有支持这个结果（左倾、右倾、平衡）的答案可
能性的和，并且答案的每个可能性都是等概率的。

排序的本质可以这样来表述：一组未排序的N个数字，它们一共有N!种重排，其中只有一种排列是满足
题意的（譬如从大到小排列）。换句话说，排序问题的可能性一共有N!种。

基排高效的本质原因：假设前i张牌都已经放到了它们对应的位置上，第i+1张牌放出去的时候，实际
上就相当于“一下子”就确立了它和前i张牌的大小关系，用O(1)的操作就将这张牌正确地插入到了
前i张牌中的正确位置上，这个效果就相当于插入排序的第i轮原本需要比较O (i)次的，现在只需要O(1)了。

当i张牌放到位之后，放置第i+1张牌的时候有多少种可能性？大约i+1种，因为前i张牌将13个位置分割成
了i+1个区间——第i+1张牌可以落在任意一个区间。所以放置第i+1张牌就好比是询问这样一个问题：
“这张牌落在哪个区间呢？”而这个问题的答案有i+1种可能性？所以它就将剩下来的可能性均分成了
i+1份（换句话说，砍掉了i/i+1的可能性！）。再看看基于比较的排序吧：由于每次比较只有两种结
果，所以最多只能将剩下的可能性砍掉一半。

只需要一种看问题的本质视角：将排序问题看成和猜数字一样，是通过问问题来缩小/排除
（narrow down）结果的可能性区间，这样一来，就会发现，“最好的问题”就是那些能够均分所有可能
性的问题，因为那样的话不管问题的答案如何，都能排除掉k- 1/k（k为问题的答案有多少种输出——猜
数字里面是2，称球里面是3）种可能性，而不均衡的问题总会有一个或一些答案分支排除掉的可能性
要小于k- 1/k。于是策略的下界就被拖累了。

思想与技术水平都是挂钩的，到了哪一层技术才能有相应的思想。