分享 关于算法, 我们该学什么?

luikore · 2014年01月12日 · 最后由 mal5338 回复于 2014年03月05日 · 19341 次阅读
本帖已被管理员设置为精华贴

如果给你一个改进算法的任务,你是盲头苍蝇的 google 又 google 试了又试,还是利用算法知识一下找到问题所在?以我浅薄的经验,觉得应该学的是这些:

  • 寄存器,内存,硬盘,IO 操作速度的不同之处
  • 时间/空间复杂度,大 O 记法,多项式复杂度的基本概念
  • 单/多递归函数的时间/空间复杂度
  • 工作语言中的常用操作的复杂度 (例如 array.index? 的最佳和最差情况)
  • 二分和排序等常见的 log(n) 或者 n log(n) 的算法 (进阶:大 L 记法, 其他复杂度类别).
  • 给一个简单问题知道该用/搜什么算法或者 API 去解决 (这是经验), 不知道算法名称但能直接写代码搞定其实更好 (这是能力)...

如果要求底层算法:

  • 文件 IO 和 mmap
  • 几种基本内存管理的实现 (malloc, memory pool, arena, reference counting, trace GC 等)
  • CPU 架构:高级缓存,page fault, cache miss, cache line, cache oblivion 等概念和应用
  • CPU 架构:流水线,分支预测,超向量指令等概念和应用

如果关心计算并行化:

  • task parallel 和 data parallel 的基本概念
  • 差分方程和母函数法的应用
  • 把简单的算术运算转换成矩阵运算
  • 认出可以优化成 c 倍快或者 log(c) 倍快的代码模式 (其中 c 是核的数目)

如果是数据分析,暂时只想到这些:

  • PAC learning 评价选择适合业务的算法 (关于这个数学框架 Tom Mitchell 的 Machine Learning 有详述)
  • 反向传播算法 (在神经网络,SGD, 各种数值系统都有广泛应用) 和 viterbi 算法 (在 RCG 语法解析,隐马尔可夫模型,条件随机场,和电子方面都有广泛应用)

大赞,新年伊始,吕哥给我们挖了这么大一个坑,加精,沙发坐等吕哥填坑。

#1 楼 @lgn21st 已经写完了... 等楼下补充和删除...

感觉算法这个话题能深入挖掘的太多了,坐等补充~~

确实太多了,基本分类的大概有,程序语言方面的,体系结构方面的,图形图像方面的,网络方面的,近期比较热门的是关于数据处理的内容。

#4 楼 @rasefon 加起来说不定有有几千种算法,有些是谁都写得出的根本不用记,有些记了也没用,需要的时候就搜好了... 但只要有了基础,不管要掌握和应用哪种都很快,所以才列了那些...

啊,矩阵,永远的痛,CSS 里的矩阵直接绕着走。。。必须学了

整体结构设计也很重要。数据库 IO 和网络 IO 算不算?

收藏先,等以后要用到的时候再来看。。用不到的时候学了也很难记住。。

我觉得大部分算法不用了解细节,但是必须知道什么问题需要用什么算法。楼主部分解决了这个问题

一说算法头晕犯迷糊,一问三不知。。。咋办好

#2 楼 @luikore 赞"给一个简单问题知道该用/搜什么算法或者 API 去解决 (这是经验), 不知道算法名称但能直接写代码搞定其实更好 (这是能力)...",我怎么感觉你不去做云计算方面的工作真是可惜了。。。

有用么,能通过面试么?

大神,文件 IO 和 mmap 这些是系统编程层面的,不是算法吧?

个人感觉算法是个很神奇的东西

#14 楼 @assassinpig 算法就是用来针对性弥补硬件性能缺憾的啊

#14 楼 @assassinpig 用算法解决问题有三个角度,1, CPU 组织,2, IO 组织,3, CPU 和 IO 互换。

#13 楼 @bhuztez 大概不能...

#14 楼 @assassinpig 其实有根据磁盘的 buffer 大小来做优化的,还有针对 raid 磁盘和 mmap 写的数据结构... 帮助理解数据库源代码应该挺有用

#18 楼 @luikore 不能学个屁啊 ...

#19 楼 @bhuztez 那是面经和面试官心理学要解决的问题...

话说,ruby 的 matrix 运算有做优化么?

补充一下:

  • 数据库索引的概念和索引设计技巧
  • 状态机的概念和正则表达式

#19 楼 @bhuztez 人生最重要的事情,不就是找到你真正喜欢的东西嘛。你喜欢算法么?

艾玛,巨坑啊。

划重点了 好 high!

我觉得数据挖掘的话。。。。知道原理和应用就好,基本上都有相关的算法包。比如 libsvm 什么的。。要是把里面的公式推导都搞通了,读个博士问题不大,顺便还能发几篇 SCI。

#27 楼 @yaonie084

要是把里面的公式推导都搞通了

有这么简单?

牛啊,都搞明白了没。。。

学好计算机本科大一到大三该学的。。

计算机是应用科学,学习算法其实没太大用,大部分人也无需去学算法。学习算法是应用数学系和 CS 的某些博士干的事情. 学会应用算法就行了,应用算法上面再加一点点稍微的要求——高效优美的实现算法。拿最简单的倒置数字来说,13 倒置成 31,不考虑 10,100 的处理,不考虑溢出。如何算优美写出,而不是反正实现了. 如何学会应用算法?手熟多练。

慢慢填坑

我先把微积分,线性代数,概率论恶补一遍,深深觉得这是我的瓶颈了

不同领域需要的基础不一样。例如数据挖掘、机器学习、DSP(数字信号处理)、模式识别领域,当然这些领域每一个都很大,有非常多的算法。 在很多 AI 相关的领域,概率和数理统计的知识是最为重要的。

#36 楼 @yanguango 数学好,什么都可以玩;数学不好,什么都玩不起

#37 楼 @wushexu 概率和数理统计在 AI 里重要,是因为 AI 只能靠这些,没有真正意义上的那种理想化具有思考能力的‘AI’。不要说 AI,连真正的随机数,都没法生成。

#39 楼 @rasefon AI 太复杂,没法建立精确的模型,只能采用概率和统计的办法去解决。而且,计算、推理所依据的信息是有限的,甚至是不准确的,就算有一个精确的模型,也不可能得到精确的结果。实际上人的大脑的运算过程也不太可能是精确的。 真正的随机数是可以生成的,有多种办法。例如电子噪声、宇宙微波辐射,都认为是随机源。

#40 楼 @wushexu 你说的随机数生成,我不懂。对随机这个概念我就从来没想清楚过,我潜意识里面觉得跟不上就不存在随机。。。

#39 楼 @rasefon AI 和随机数怎么关联上的?

#32 楼 @chrishine 也不能说没用,这是某种智力标记吧

#42 楼 @xranthoar 人的多数灵感,就是随机数碰撞到特定知识结构产生的。其实蛮重要。

#45 楼 @pepsin 如果你真的对随机数感兴趣的话,这儿有个量子随机数生成器,至于这是不是真随机我就不分辨了~

越看越糊涂

唉唉。。。暂不提算法。。。

具体业务逻辑的抽象,最后可以归结到纯数学问题. 而针对数学问题的具体处理与分析,一些好的方法是通过抽象算法进行描述与处理。

从计算机系统的全技术栈,就可以找到很多算法技术。http://www.infoq.com/cn/news/2013/11/Core-algorithms-deployed

算法还是应该和具体的问题相结合,算法主要还是为了解决问题,分析问题,解决问题。

#36 楼 @yanguango 别忘了分享过程

数据结构很重要,很多算法依赖于数据结构的设计. 推荐看<算法导论>.看完了,差不多"不惑"了. 算法的标准只有两条,有效性以及效率。如果对算法效率的要求深究到 CPU 底层实现的地步,那 ruby 就不合适了,用 C 吧。

55 楼 已删除

游戏要的是伪随机,真随机不能用的,不然调试不会重现问题。

学习了。

大神帖子要顶!!!! 这每一项拆开了都好多内容··

匿名 #60 2014年06月24日

赞 :plus1: 你是盲头苍蝇的 google 又 google 试了又试, 还是利用算法知识一下找到问题所在? 可否举例? 只会 Google 的求解。怎样可以减少 Google 之“鱼”,而能“渔”?

需要 登录 后方可回复, 如果你还没有账号请 注册新账号