数据结构和算法：如何设计自己的算法？
2017-10-22 本文已影响41人
ShannonChenCHN
当你遇到一个新问题时，并需要找一个算法解决它时，你该怎么做？
一、先看看是否已经存在过类似的问题
分析问题的本质，如果你发现你所面临的问题，本质上就是一个已知问题，那就不用造轮子了，直接借助现有的算法把它解决掉。
二、一开始采用粗暴的解决方式并没什么问题
一开始采用粗暴的解决方式，可能效果并不是最优，但是至少这是一个好的开始。因为在你使用简单方式解决问题的过程中，你也开始逐渐了解问题的本质是什么。
当你已经采用简单粗暴的方式实现了，你就可以在此基础上验证一些可以优化的想法。
有时候，在处理一些简单的数据时，简单粗暴的方式也许就够用了。过早优化是万恶之源。
三、学会运用算法思想
1. 经典的算法思想
- 分而治之：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处有很多——减低复杂度、算法复用以及便于进行并行计算。
- 动态规划：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
- 贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
- 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
- 线性规划
- 迭代法
- 穷举搜索法
- 递推法
- 回溯
2. 聊聊“分而治之”
“分而治之”是指在面临复杂问题时，将其拆分成各个小问题，把分解后的各个小问题解决之后，再把各个小问题的解决方案结合起来解决大问题。
这种解决问题的思想在软件工程领域很常见，在《剑指 Offer》一书中也提到过“分解让复杂问题简单化”就是解决算法题的一种思想。
我们不要把一个问题单纯看成是一个单一的、庞大的、复杂的任务，我们应该把一个大问题拆分成更小的、易于理解的、易于解决的小问题。
一个一个地去解决小问题然后把解决方案汇总起来，直到所有小问题都已经被解决。
随着一步一步地解决，手上的小问题变得越来越少，解决方案也越来越成熟，最后我们就会得到最终的正确答案。
将大问题拆分成小问题后，有些小问题其实是类似的，因此很多小问题的解决方案是可以复用的，这样我们就能节省更少的时间。
四、参考资料
如果你也喜欢交流技术、喜欢阅读、积极践行，欢迎关注我的公众号：祥龙Shannon写字的地方，一起成长。
qrcode_for_gh_cc686217be41_344.jpg
