随笔-19  评论-21  文章-0  trackbacks-0
为一个问题寻找算法的过程,有点像一个穷举过程:搜索已有知识,并进行重组的过程。所以把常用的算法记住,然后一个一个试用,看是否可行,不失为一个好方法。
如果这个方法不行呢?不妨写出最直观的解答(即用“蛮力法”),然后从中看出可以优化的地方在哪里,进而进行优化。


如何确定该问题可以用哪类方法来解答呢?首先,需要对这些常用的算法的基本思想非常熟悉。
常用的算法可以分为以下几类:
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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理