O(1) 的小乐

Job Hunting

公告

记录我的生活和工作。。。
<2011年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

  • 随笔 - 182
  • 文章 - 1
  • 评论 - 41
  • 引用 - 0

留言簿(10)

随笔分类(70)

随笔档案(182)

文章档案(1)

如影随形

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜

算法的学习zz

首先写这点东西是为了和大家分享。很多加入群的新人都会问怎么怎么学习算法,我也
常常好为人师去参与解答 , 后来觉得应该有一个这样的东西 。 希望大家能够在群里面多多讨
论,前一阶段忙于各种各样的事情也是疏于管理,请大家见谅。
怎么学习算法是一个宽大的话题,人人都有自己的见解 。 我觉得如果想要学习算法,首
先要知道自己到底处在一个什么样的层次上 , 下一步的提高方式是怎么样的 。 网上有很多算
法的层次的讲解 , 程序员分九等之类的 。 。 。 我只想说说我的理解 。 其次 , 要知道自己将来要
用算法用到多深的程度。
算法分好多类 , 有传统意义上的计算机的算法 , 有各个学科自己的专属算法 , ( 像 CG 里
面的 Euler angle 四元数 转换之类 ) 。 。 。这里仅仅讨论传统意义上的计算机的算法。
首先算法入门的问题当然就是各种的排序算法了。这个在数据结构课程上已经被讲泛滥
了 。 当然仅仅是这么简单的问题也是能够看出差别来的 。 你可以尝试马上说出各个 排序 算法
的核心思想 , 准确说出他们的复杂度 。 如果都可以 , 那么你可以尝试证明一下 , 快排为什么
在概率意义下是 O(nlogn)... 如果这些你都不清楚 。 恐怕你就要从基础算法开始掌握了 。 虽然
排序简单,但是各种排序算法蕴含的算法思想不是都那么浅显易懂的。
掌握了上述,或许你可以准备了解一下 Greedy , Divide and Conquer , Dynamic
Programming 了 , 这些是算法设计的经典技巧 。 很多一些很难的问题 , 都能够通过上述技巧非
常优美的解决。举几个经典的例子来看一下具体掌握多少。

 

贪心:你能马上回忆起 Huffman 编码么? M inimum Spanning Tree 的两种经典构造呢?
如果可以,你的贪心算法就算合格了吧。
Divide and Conquer :马上想起分治排序 。 (这个在排序里面你已经掌握了) 最近点对问
题呢??有想法吗?主定理明白吗?如果不知道,可以去补一下相关的知识。
DP :曾经很多老师告诉我说, DP 是最不需要技巧的,很多 参加 ACM 的同学说 DP 是最
需要技巧的 。 在我看来 , DP 是一种经验类题目 , DP 题目的种类千变万化 , 每种 DP 的模型
都令人拍案叫绝 。 举 一个大家普遍都清楚的例子 , 比如说矩阵相乘的 DP 解法 , 最短路径问
题中 Bellford 算法 ( 这个是我在研究生的时候,才去仔细思考的一个模型,在实际使用中意
义重大 ) 等等。
如果上述都掌握了,说明你的算法水平已经不错了 。 其实很多人这些事情都不清楚 , 又
不愿意画时间去研究,他们讨论最多的是算法应该怎么学习,算法书籍那本好。 ( 也是我现
在干的 。 。 。 -_-!!) 他们不会花时间去研究算法到底是怎么回事 。 我觉得,学习这件事情,自
己不应该成为一个收藏者,手头什么都有,却什么都没看。
掌握了上述 , OK , 的确很不错 , 当然还有更多 , 单纯上述三种算法的话 , 还有很多东西 :
贪心算法背后的拟阵理论,动态规划的优化技巧 ( 四边形不等式等等 ) 。
接下来的一部,我们就要进入网络流和线性规划,这往往也是把很多人挡在算法门外的
一堵高墙 。 最大流 , 最小费用最大流 , 然后是各种算法 。 。 。 太多了 , 不一一列举 。 。 。 如果你
清楚 , 那么你更应该清楚的是网络流问题的转化 。 把各种各样的问题转化为网络流 , 转化为
线性规划 。 。

 

如果上述你也清楚 , 那么或许你应该看一下近似算法 随机算法和 NP 问题等等 。 这三类中

任何一类都可以写成好几本书,里面的东西也都是浩如烟海,各种 NPC 问题的相互规约如
果你能够搞清楚的话 , 或许你都可以到大学里面教书了 。 。 (->-) 。 。 。 这些都是没有止境的 。 。 。
如果上述的你还都清楚的话,你可以尝试一下 Local Search 或者写几本关于近似算法和
随机算法通俗易懂的中文书 。 。 。或者,把你学过的算法都变成高效可移植的代码和文档 , 开
源造福后人。
熟悉上述所有问题的,往往都是在某个领域经历比较久的 人 , 他们大 都转入了特别窄的
领域进行研究了 。 。 。
有关算法使用什么书 , 这还是被讨论了泛滥的问题 , 很多书都不错 , 我只推荐一本书 《 算
法设计 》 Jon Kleinberg Eva Tardos 等 , 至于说 《 算法导论 》 等好不好 , 其实都挺不错的 ,
我只是觉得《算法设计》比较适合我。
算法的练习场所就更多了 , 各大高校都非常重视的 ACM 竞赛 , 那 就是一个很好的锻炼 练
习 场所。 ACM 也训练出了无数的算法达人。推荐 T opcoder 的 Single Round Match 。此外 ,
一个更好的练习是世界各地的 ACM Regional 。当然大多数人都没有那么多时间和兴趣去做
了 。 。 。
以上就是自己对算法的一点小的简介,有什么错误和不足请大家指正。

posted on 2011-01-16 18:30 Sosi 阅读(1359) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


统计系统