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

luikore · 发布于 2014年01月12日 · 最后由 mal5338 回复于 2014年03月05日 · 12063 次阅读
2880
本帖已被设为精华帖!

如果给你一个改进算法的任务, 你是盲头苍蝇的 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语法解析, 隐马尔可夫模型, 条件随机场, 和电子方面都有广泛应用)
共收到 59 条回复
3

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

2880

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

96

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

2466

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

2880

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

1289

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

681

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

157

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

4482

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

3930

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

29

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

1031

......

96

有用么,能通过面试么?

7263

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

96

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

1289

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

29

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

2880

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

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

96

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

2880

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

1232

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

96

补充一下:

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

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

3253

艾玛,巨坑啊。

96

划重点了 好high!

96

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

96

#27楼 @yaonie084

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

有这么简单?

1411

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

96

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

96

#27楼 @yaonie084 CS 的谁发 SCI 啊

7895

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

487

慢慢填坑

8893

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

6375

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

6375

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

2466

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

6375

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

2466

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

96

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

96

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

5083

望其项背

1289

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

96

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

4316

越看越糊涂

5485

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

96

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

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

96

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

96

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

11258

Great!

709

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

55楼 已删除
C4522b

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

11694

学习了。

9765

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

10432

学习

12224

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

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