网站怎么做rss订阅功能,建设手机网站平台,济南网页设计,用asp.net制作网站在不知其所以然的情况下#xff0c;算法只是一堆离散的机械步骤#xff0c;缺少背后的思想的支撑#xff0c; 这些步骤之间就没有一个本质层面上的关联#xff08;先知亚里士多德早就指出#xff1a;学习即联接#xff09;。 所以就跟背历史书也没多大区别。然而#xf…在不知其所以然的情况下算法只是一堆离散的机械步骤缺少背后的思想的支撑 这些步骤之间就没有一个本质层面上的关联先知亚里士多德早就指出学习即联接。 所以就跟背历史书也没多大区别。然而知道了算法是怎样一步步被推导出来的我们就一下拥有了大量的记忆提取线索 对算法发现过程中的任何一个关键步骤尤其是本质的回忆都可能使我们能够自己动手推导出剩余的内容。
譬如你知道堆(heap)是怎样由朴素的决策树演化而来的它又是为了解决什么问题的你即便忘 记了具体的细节也可以自己推导出来。
譬如你知道KMP算法的本质在于消除回溯至于如何消除回溯却并不是那么难以推导的所以即便 忘了也可以借助于大脑的逻辑演绎能力再现出来。
譬如你知道Tarjan算法其实只是从后序遍历经过两个优化调整而来的其中并査集的使用其实只 是优化手段——为了能够迅速判断祖先节点是谁——而非算法本质 ——
当然算法设计的主要任务本来就是通过问题条件中蕴含的知识来“消除冗余计算”和“避免不必要计算” 所以你也可以说并査集的使用是关乎本质的只不过知道了为什么需要引入并査集就会强烈地感觉 到一切是顺理成章的了那这个出了名的绕人的算法也就不那么难以理解和记忆了。
譬如你知道排序的本质就能够对什么是最优排序为什么它是最优排序有深刻的认识。
揣摩的重要性是怎么说都不为过的。揣摩的一些指导性的问题有为什么要这样为什么这是好的 为什么不是那样有其它做法吗有更好的做法吗这样做是最好的吗为什么能证明吗 这个做法跟其它的什么做法有本质联系吗这个跟这个的区别是什么问题的本质是什么 这个做法的本质又是什么到底本质上是什么东西导致了这个做法如此..与这个问题类似的还有其它问题吗 同样或类似的做法也适用吗等等。 猜数用二分法 本质为什么这种策略具有最优下界答案也很简单这个策略是平衡的。 这种策略的本质可以概括成“让未知世界无机可乘”。 二分搜索为什么好就是因为它每次都将可能性排除一半并且无论如何都能排除一 半它是最糟情况下表现最好的。
称球指导思想——你选择的称法必须使得当天平平衡的时候答案剩下的可能性和天平左倾右倾的 时候答案剩下的可能性一样多。实际上这等同于你得选择一种称法使得天平输出三种结果的概率 是均等的因为天平输出某个结果的概率就等同于所有支持这个结果左倾、右倾、平衡的答案可 能性的和并且答案的每个可能性都是等概率的。
排序的本质可以这样来表述一组未排序的N个数字它们一共有N!种重排其中只有一种排列是满足 题意的譬如从大到小排列。换句话说排序问题的可能性一共有N!种。
基排高效的本质原因假设前i张牌都已经放到了它们对应的位置上第i1张牌放出去的时候实际 上就相当于“一下子”就确立了它和前i张牌的大小关系用O(1)的操作就将这张牌正确地插入到了 前i张牌中的正确位置上这个效果就相当于插入排序的第i轮原本需要比较O (i)次的现在只需要O(1)了。
当i张牌放到位之后放置第i1张牌的时候有多少种可能性大约i1种因为前i张牌将13个位置分割成 了i1个区间——第i1张牌可以落在任意一个区间。所以放置第i1张牌就好比是询问这样一个问题 “这张牌落在哪个区间呢”而这个问题的答案有i1种可能性所以它就将剩下来的可能性均分成了 i1份换句话说砍掉了i/i1的可能性。再看看基于比较的排序吧由于每次比较只有两种结 果所以最多只能将剩下的可能性砍掉一半。
只需要一种看问题的本质视角将排序问题看成和猜数字一样是通过问问题来缩小/排除 narrow down结果的可能性区间这样一来就会发现“最好的问题”就是那些能够均分所有可能 性的问题因为那样的话不管问题的答案如何都能排除掉k- 1/kk为问题的答案有多少种输出——猜 数字里面是2称球里面是3种可能性而不均衡的问题总会有一个或一些答案分支排除掉的可能性 要小于k- 1/k。于是策略的下界就被拖累了。
思想与技术水平都是挂钩的到了哪一层技术才能有相应的思想。
