最近买了几本书，其中有一本是叫算法图解。买这本书是缘于阿里云开发者社区的大佬推荐的书籍，想到自己以前只是关注于问题的直接解决，而没有过多的思考计算是否合理、会不会绕弯路，效率是否低下。
这几天都在看算法图解，这本书很有意思，里面有很多图形来帮助解释，视觉感受非常好，理解起来也较为容易。现在将所学的知识点总结以及使用python程序来测试验证。
1、二分查找
二分查找每次猜测中间的数字，每次都可以排除一半的数字。使用二分查找最多需要log2n步（对数时间），如果使用简单查找则需要n步（线性时间）。但是二分查找时只对有序数据才管用。
下面的例子是先找到列表种的中间位置的数字索引，然后判断与给定值的大小，不断缩小范围，直至找到给定值的位置。
2、选择排序
选择排序的速度不快，第一次运行n次，第二次需要n-1次，依次递减，总的运行步骤为1/2*n*(n-1)。
下面二点例子是找到列表种的最小值，加入到新列表种，然后删除旧列表中的最小值，再次找旧列表中的最小值，一次找到后，新的列表就是按照从小到大顺序排列的列表。
3、递归算法
递归就是函数自己调用自己，让方法更加清晰，但是没有性能上的优势。
下面就是递归实现5的阶乘。
4、快速排序
快速排序采用分而治之的策略。找到一个基准值，然后将列表分为两个子列表，对两个子列表进行快速排序，再合并结果。其速度取决于选择的基准值，平均时间为n*logn 。
5、广度优先搜索
解决最短路径问题就是广度优先搜索。下面的案例是找到名字以m结尾的姓名，使用队列的先进先出的属性，算法的优先就是使用队列来体现的。这个案例十分经典，复杂的网络图可以使用字典（哈希表）来完成建模，在实际生产生活中，最短的路体现在方方面面，这个算法也经常使用。
6、狄克斯特拉算法
广度优先搜索找到最短的路径，但是没有考虑权重问题，狄克斯特拉算法就是找出权重最低的路径。下面的例子是找出权重最低的路径，fin是终点，costs是开销表这个算法运行时在不断的更新costs表和parents表，笔者花了一些时间才理清楚。
7、贪婪算法
贪婪算法是一种近似算法，每一步选择局部最优解，那么最终得到的就是接近全局最优解，是一种大致解决问题的算法。下面的是解决集合覆盖问题，可以得到一个非常接近的解，但是可以非常见到你解决问题，而不是把全部组合罗列出来。
网友评论