数据结构学习心得(转)
查看(715) 回复(0) |
|
sszqm1314
|
发表于 2014-05-31 11:43
楼主
考试和算法设计精髓一样:
时间消耗越少,一般空间消耗越大,存储越冗余 空间消耗越少,一般时间消耗越大,计算越冗余 空间和时间的消耗如果都降低的话,人的智力和脑力消耗越大,包括人思考所用的时间和记忆力。 总之,三者无法 同时降低,可能有人要问这三句话有什么意义?其实,这三句话的意思就是:其他一个或两个因素的冗余在可以接受的幅度内,降低另两个或一个因素的代价。本质是折中取舍,如何取舍取决于你的目的。人设计高效的算法是需要很大代价的,但是,高效算法一旦被发明,低廉且容易的大批量技术复制让它的整个成本降低,而且,复制的数量越庞大,整体成本越低,当你在今天使用一个看似简单而且高效的算法时,你可曾想过此前有很多人为此付出了巨大的代价和花费? 这三句话的现实意义就是,在考试中,你想提高解题速度,你只能在复习中记忆更多的常识,知识和结论。你想巧妙的解决问题,那么意味着你在考试时需要付出更多时间和脑力用于的思考。所以唯一可取的方法是:复习中记忆掌握,考试中快速计算。 这三句话的现实意义还有,在记忆时,必如记忆中间结论和单词,冗余永远不是好的记忆方法,因为如果你为了记住A,必须记住相关的B,那么B怎么记忆呢? 由B该如何联想到A呢 ? 你记忆的冗余信息越多,说明你遗忘的几率越大,因为,联系中的任意一环都是你记忆的薄弱部分。此外冗余必然引起信息的不一致性,你还得解决不一致性带来的问题,总之,冗余作为存储本质及其精髓而言,对人和计算机都非常关键!请注意,这里的冗余只是不必要的冗余,如俞敏洪的联想记忆,就是这种非常愚蠢做法的明证。那么,该如何记忆呢?最好的方法莫过于降低冗余,改善存储结构。抽象与具体,归纳与演绎,分析与综合,对比与类推,分类细化与拓沿一般,这是人的思维独到之处,从自个思维模式着手,发现你最擅长的一面是什么?(比如本文作者相对比较擅长分析,抽象,类推三种),从你自身出发,选择适合你的方法。比如:词根+词缀记忆这个方法就是好的方法,首先,它降低了记忆的冗余;其次它采用二维存储结构比一维更便于记忆。 我还想谈一点我对考试的看法:知识是冗余的常识,复习应该是一个超集合,考试只是这个超集合的子集的幂集。 对于数据结构和算法,我认为: 数据结构其实就是人的头脑中的三种逻辑模式(先后关系[线],层次关系[树],交互关系[图])如何用计算机存储模式(顺序存储[冯诺依曼机的特点]和链接存储[间接寻址])来实现,在此过程中需要考虑两个问题:一,这种存储如何和人头脑的思维达到融合,方便人解决问题。二,数据存储的目的和意义在于数据访问,数据访问决定数据存储,因此访问效率和存储效率必须折中取舍。 至于,算法,其实是计算机解题模式,无非是存取,运算,顺序执行,跳转,迭代和递归的有限步骤。 我推荐17个算法,请注意,如果你熟悉这17算法的话,在考试中,就可以写出相对较好的算法。考试中的算法的最优解的复杂度是O(logn)级,这些算法可以帮助你写出O(n)或者O(nlogn)的解法。考试时间很关键,一般,你没有过多的时间思考最优解,你给出线性的算法就已经足够了 ,失之东隅,收之桑榆。 算法如下: 线形2个: 1.将两个有序表合并为一个表,这个算法的变种很多,可以是链表,顺序表。涉及集合运算, 归并排序,字符串处理。 2.将一个顺序表的元素重新划分,左边的较小,右边较大。涉及快速排序,求字符串的逆串。 树形9个: (注意:有些可以实现,有些实现不了,可以拿来思考) 3-5.前序线索化,递归实现,栈模拟递归,非栈式迭代实现。 6-8.中序线索化,递归实现,栈模拟递归,非栈式迭代实现。 8-11.后序线索化,递归实现,栈模拟递归,非栈式迭代实现。 图形6个: (注意:至少会画表格,写出算法执行的逐个步骤) 12:DFS 13:BFS 我强烈推荐大家做一些走迷宫的编程(Maze),DFS和BFS都可以实现,好好比对一下。 14.MST:prim,kruskal 15.short pathijkstra ,Floyd 16.AOV:拓扑排序的DFS,BFS实现 17.AOE:关键路径 |
回复话题 |
||
上传/修改头像 |
|
|