1

一些常用的算法思维

 1 year ago
source link: https://jiajunhuang.com/articles/2021_02_24-use_algorithms_in_life.md.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

一些常用的算法思维

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

暴力解法(朴素解法)

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

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

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

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

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

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

递归的视角看世界

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

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

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


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

我的技术栈选型

为什么我要用Linux作为桌面?

disqus获取评论时忽略query string

MySQL性能优化指南

网络编程所需要熟悉的那些函数

DNSCrypt简明教程

SQLAlchemy简明教程

这些年,我们错过的n个亿

给Linux用户的FreeBSD快速指南

旧电脑也不能闲着:家用备份方案

将SQLite的数据迁移到MySQL

Linux托管Windows虚拟机最佳实践

为什么gRPC难以推广

关于ORM的思考

MySQL指定使用索引(使用索引提示)




About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK