一些常用的算法思维

其实算法并不是空中楼阁的东西,相反,在实际工程、实际生活中,也可以看到它的影子。因为它是一种思维方式。我们来看看常用的 一些算法思维。

暴力解法(朴素解法)

这是最简单的一种思维,那就是强行上!比如我们想要在文件内容的每一行末尾都加上一个逗号,最简单的暴力解法就是,手动每一行 加一个逗号。这并不是最优解法,比较好的方法可能是,在编辑器里录制一个动作,然后批量执行,但是暴力解法仍然非常有用,比如 当行数很小的时候,暴力解法往往比录制动作要更快,例如当行数只有三五行的时候。

二分查找

怎么找出影响Vim启动速度最大的Vim插件呢?除了暴力解法,还可以尝试试用二分法。每次注释一半的插件,如果没有变快, 那么就在当前注释的这一半里,否则就在另一半里。接着我们重复上述动作,很快就可以找出最慢的那个插件。当然,Vim已经提供了 启动速度分析,我们也可以直接用。

分治法

当我们要转存一个文件的时候,通常的做法是,直接把文件从A处读出来,然后转发到B处,但是当文件变得非常大的时候,往往会被OOM 干掉,这个时候我们就要尝试对文件进行分块处理,每次读一小块上传。

这种方式在生活中还有一个例子,当我们通过网络传输一个超大文件时,我们可以先把文件切割然后压缩,传输过去之后,再解压缩后 合并文件。

这也是分治思维的一种现实体现,分而治之,再合并结果。

贪心算法

贪心算法的用处简直不用我说,例如在赌场的时候、打麻将的时候,很多人就会被贪心算法所迷惑,不知道适可而止,觉得自己还能赢, 但是由于贪心算法是局部最优,而并不是全局最优,所以最终的结果可能不一定很好。

递归的视角看世界

我们在教科书上老是被教育:不要用递归,因为递归很慢。其实递归是一种非常有用的思维方式,动态规划中,寻找最优子结构,其实 就是一种递归的思维,把当前的问题,划分成与当前问题相似,但是规模更小的问题,然后缓存子问题的结果,从而达到剪枝的效果。

此外,在数据结构中,我们可以以递归的方式来看数组、链表和树。例如数组 [1, 2, 3],我们可以看成元素 1 和 数组 [2, 3] 的组合,Haskell中对列表就是这样处理的。链表,则是链首元素和剩余元素,对于树,则是根节点和子树。

当我们尝试用递归的思维来看待问题时,我们往往能够发现一个简洁优美的面,当然是否用递归的方式来写代码,那是另外一回事(而且 递归的写法其实也没那么差)。

完 :)


微信公众号
关注公众号,获得及时更新

更多文章
  • 2016年就要结束了,2017年就要开始啦!
  • unittest 源代码阅读
  • APUEv3 - 重读笔记
  • Mock源码阅读与分析
  • Thinking in Python
  • 我的代码进CPython标准库啦
  • Python零碎小知识
  • Python和单元测试
  • 工作一年的总结
  • Python 的继承
  • MongoDB 的一些坑
  • Python的yield关键字有什么作用?
  • 借助coroutine用同步的语法写异步
  • Python3函数参数中的星号
  • 使用Git Hooks