一些常用的算法思维

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

暴力解法(朴素解法)

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

二分查找

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

分治法

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

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

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

贪心算法

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

递归的视角看世界

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

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

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

完 :)


更多文章
  • 再读《软件随想录》/《黑客与画家》/《软技能》
  • HTTP 压力测试中的 Coordinated Omission
  • 2的补码
  • 编程语言中的 context 是什么?
  • flutter macOS 构建出错
  • Flatpak 使用小记
  • Golang CAS 操作是怎么实现的
  • PostgreSQL 当MQ来使用
  • Clash 结合 工作VPN 的网络设计
  • 使用 PostgreSQL 搭建 JuiceFS
  • PostgreSQL 配置优化和日志分析
  • 有GitHub Copilot?那就可以搭建你的ChatGPT4服务
  • 窗口函数的使用(以PG为例)
  • 读《为什么学生不喜欢上学》
  • OpenAI Prompt Engineering 摘录和总结