四种算法思想
学习算法，有两个比较重要的基础要学习。
- 首先是复杂度的计算。复杂度包括时间复杂度和空间复杂度，通过对一个问题的不同算法，通过比较时间复杂度和空间复杂度，我们选择针对这个问题最合适的算法。就像架构师选择架构所做的事情一样。
- 其次是算法思想。目前的算法书籍总结了四种基本的算法思想，用以指导算法的开发，分别是分治、回溯、贪婪和动态规划。
对于四种算法思想，我们学习后当然需要能讲得清并且反复练习直至掌握，这四种算法思想的掌握还是非常有难度的，特别是动态规划。
理解四种算法思想
四种算法要理解并学习实在不易，学习就是为了用，那么怎么学比较好呢，学习原理，记忆模版。学习原理是为了真正理解，记忆模版是为了如何用，因为真的抽象度高，通过模版能够降低使用的门槛难度。光学不用就会出现学了忘忘了学的死循环，光用不学就发现不会用，只会学过的问题。
分治
分治最典型就是mergySort了，这个排序算法是在学习排序的时候必学的，用到就是分治思想。
什么样的问题适合用分治思想解决？那么就是如下几点：
- 一个大问题可以拆解程若干小问题。
- 每个小问题可以再拆解或者到达终止条件。例如说mergy算法，最终拆解到只剩一个元素，到达了终止条件。
- 每个小问题各不相同，如果小问题都相同。
- 小问题处理完后能合并回原来的整体。
为什么要强调如上几个点，就是为了和动态规划、回溯、贪婪算法区分开来。这几种算法的特点等会在下面说。一个明显的不同就是后者存在相同的子问题，可以将相同的子问题缓存下来，避免多次计算。
最后咱们用的时候，就需要记忆一个模版，使用Python表达：
def divide_and_conquer(datas, paras):
if exit_condition(datas): #终止条件
return
subData = split_data(datas) #问题可被分解为不同的子问题
result1 = divide_and_conquer(subdata[0], paras)
result2 = divide_and_conquer(subdata[1], paras)
result3 = divide_and_conquer(subdata[2], paras)
...
result = mergy_data(result1, result2. result3...) #问题的结果可被还原为整体
return result
回溯
回溯是一种暴力算法，如果需要用到遍历，那么就使用回溯。例如说alphago围棋，最简单容易想到的就是回溯暴力计算了，为了推测下一步走那个子胜率高，我们对于可能下的位置的点用回溯遍历计算出一个概率，然后选择胜率最高的位置放下一个子。但是对于围棋，需要超出人类想象的计算能力和存储能力才能用暴力计算完成，所以说需要用不同的算法优化等。
上述对于alphago的回溯计算也就说明了回溯算法的优缺点：
- 优点是容易想到
- 缺点是只能面对小数据集，使用面有限。
进而下一步的，如果想用回溯算法，需要进行优化。例如说在树和图的深度优先的回溯中，有个比较专门的优化名词，剪枝，也就是将一些不需要的路径给剪掉，从而减少计算量。
上模版：
def backtracking(level, paras):
if exist_condition(level):
return
state = keepsate(level) #保存当前状态
backtracking(level+1, paras):
reverseState(level, state) #恢复当前状态
小结
分治和回溯相对来说，是两种比较好掌握的算法思想，需要做的就是搞明白后，牢记模版，多多练习一下。
题外话：递归和迭代
如上模版中使用了递归的技巧，而在计算设计中SICP中讲解了为了提升效率迭代的技巧。一般的问题能用递归解决也就同时能用迭代解决，这是两个必须要掌握的基本技巧。
- 递归是计算机的思考方式，其数学基础就是数学归纳法，基于某个子问题已成立的基础上，去思考下一层的问题。计算机的递归思维思考起来是比较自然的，但是实际上它是基于栈的，如果你把它展开，就会发现栈不停再随规模增长而增长，直到超出人的思考界限和计算机栈的容量。因此对于一些可能的递归，有尾递归的优化避免栈爆炸。
- 迭代是另外一种技巧，讲中间结果作为状态保存起来传递，而避免使用栈。递归因为符合计算机思维，编码的时候简单，要想出并写出迭代却没有那么容易。
网友评论