为一个问题寻找算法的过程,有点像一个穷举过程:搜索已有知识,并进行重组的过程。所以把常用的算法记住,然后一个一个试用,看是否可行,不失为一个好方法。
如果这个方法不行呢?不妨写出最直观的解答(即用“蛮力法”),然后从中看出可以优化的地方在哪里,进而进行优化。
如何确定该问题可以用哪类方法来解答呢?首先,需要对这些常用的算法的基本思想非常熟悉。
常用的算法可以分为以下几类:
1. Divide & conquer
分治算法:将问题分为两个1/2规模大小的子问题,然后解决。如merge sort
2. Decrease & conquer
减治法 : 将问题规模从 n 变为 n - 1,然后在规模n-1的基础上解决此问题。 如insertion sort
这不是递归么?
3. Transform & conquer
变治法 :变换结构。如heap sort
4. Brute force
蛮力算法,可以说是必杀技吧,大部分问题都可以用此方法解决。 如selection sort
使用蛮力法的优点是简单不容易出错,缺点是复杂度有时很高,所以我们可以在穷举法的基础上进行改进,这样能达到一举双得的效果。
Backtracking(
回溯法) 是 Brute fore搜索算法的一种,它通常用最简单的递归方法来实现,在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。其比较经典的运用是:N皇后问题。
其次,数据结构有时候会决定算法,例 Transform & conquer。
另外在TopLanguage上看到的一些有用的观点:
1. 算法里面极大一部分内容是如何有效地进行搜索,这里的"有效"可以分为:避免不必要的计算(如A*寻路以及所有的启发式剪枝),缓存重复计算(如所有的动 态规划)。
2.本质上,练习并不产生新能力。然而练习最重要的一个作用就是将
外显记忆转化为
内隐记忆。用大白话来说就是将平时需要用脑子去想(参与)的东西转化为内在的习惯。譬如我们一开始学骑自行车的时候需要不断提醒自己注意平衡,但随着不断的联系,这种技能就内化成了所谓的
程序式记忆 这就是熟能生巧吧。
posted on 2011-08-24 21:39
hex108 阅读(567)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm