一些常用的算法思维
其实算法并不是空中楼阁的东西,相反,在实际工程、实际生活中,也可以看到它的影子。因为它是一种思维方式。我们来看看常用的 一些算法思维。
暴力解法(朴素解法)
这是最简单的一种思维,那就是强行上!比如我们想要在文件内容的每一行末尾都加上一个逗号,最简单的暴力解法就是,手动每一行 加一个逗号。这并不是最优解法,比较好的方法可能是,在编辑器里录制一个动作,然后批量执行,但是暴力解法仍然非常有用,比如 当行数很小的时候,暴力解法往往比录制动作要更快,例如当行数只有三五行的时候。
二分查找
怎么找出影响Vim启动速度最大的Vim插件呢?除了暴力解法,还可以尝试试用二分法。每次注释一半的插件,如果没有变快, 那么就在当前注释的这一半里,否则就在另一半里。接着我们重复上述动作,很快就可以找出最慢的那个插件。当然,Vim已经提供了 启动速度分析,我们也可以直接用。
分治法
当我们要转存一个文件的时候,通常的做法是,直接把文件从A处读出来,然后转发到B处,但是当文件变得非常大的时候,往往会被OOM 干掉,这个时候我们就要尝试对文件进行分块处理,每次读一小块上传。
这种方式在生活中还有一个例子,当我们通过网络传输一个超大文件时,我们可以先把文件切割然后压缩,传输过去之后,再解压缩后 合并文件。
这也是分治思维的一种现实体现,分而治之,再合并结果。
贪心算法
贪心算法的用处简直不用我说,例如在赌场的时候、打麻将的时候,很多人就会被贪心算法所迷惑,不知道适可而止,觉得自己还能赢, 但是由于贪心算法是局部最优,而并不是全局最优,所以最终的结果可能不一定很好。
递归的视角看世界
我们在教科书上老是被教育:不要用递归,因为递归很慢。其实递归是一种非常有用的思维方式,动态规划中,寻找最优子结构,其实 就是一种递归的思维,把当前的问题,划分成与当前问题相似,但是规模更小的问题,然后缓存子问题的结果,从而达到剪枝的效果。
此外,在数据结构中,我们可以以递归的方式来看数组、链表和树。例如数组 [1, 2, 3]
,我们可以看成元素 1
和 数组 [2, 3]
的组合,Haskell中对列表就是这样处理的。链表,则是链首元素和剩余元素,对于树,则是根节点和子树。
当我们尝试用递归的思维来看待问题时,我们往往能够发现一个简洁优美的面,当然是否用递归的方式来写代码,那是另外一回事(而且 递归的写法其实也没那么差)。
完 :)
更多文章
- socks5 协议详解
- zerotier简明教程
- 搞定面试中的系统设计题
- 用peewee代替SQLAlchemy
- frp 源码阅读与分析(一):流程和概念
- Golang(Go语言)中实现典型的fork调用
- DNSCrypt简明教程
- 一个Gunicorn worker数量引发的血案
- Golang validator使用教程
- Docker组件介绍(一):runc和containerd
- Docker组件介绍(二):shim, docker-init和docker-proxy
- 使用Go语言实现一个异步任务框架
- 协程(coroutine)简介 - 什么是协程?
- SQLAlchemy简明教程
- Go Module 简明教程