Algorithm thought

  • 算法在计算机的学习过程中是非常重要的,多对于一些常用的算法我们应该了解它的算法思想,所以,在此对一些常用算法思想做一个概念上的简单总结

递归的基本概念

一般来说,递归是一个过程或函数在它的定义或说明中又直接或间接调用它自己的一种方法。

递归本质是把一个复杂的大问题层层转化为一个与原问题相似的小问题,利用小问题的解来构筑大问题的解。学习用递归解决问题的关键就是找到问题的递归式,有了递归式就可以知道大问题与小问题之间的关系,从而解决问题了。

递归只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。它的能力在于用有限的语句来定义无限集合。正是如此,递归才能用很少的代码解决很复杂的问题。然而在使用递归解决问题时要特别注意,一定要有一个明确的递归结束条件,否则就会陷入无限循环中。例如在解决汉诺塔问题时,递归结束条件就是n=1。只要判断n=1,就停止继续调用Hanoi,开始返回值。

习惯递归的思想后,可以在很短的时间里写出正确的程序。写递归程序的诀窍就是:(1)怎么分,怎么合;(2)怎么终止。

(平面划分问题,汉诺塔问题)

分治法的基本思想

分治法是我们计算机科学解决问题的一种基本方法。从字面上来理解就是是“分而治之”。它的基本思想是把一个复杂的问题分成两个或更多的相同或相似的互相独立的子问题,再把子问题分成更小的子问题,直到最后的子问题可以简单的直接求解,然后将这些子问题的解合并从而构造出原问题的解。而用分治法求解问题的时候,通常会用到递归的思想来求解子问题。

(找假币的例子)

分治法与递归的联系与区别

其实在我们用分治法解题时,往往能会用到递归的思想。分治法产生的子问题往往是原问题的较小模式,反复应用分治法,可以使子问题与原问题的类型保持一致,而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解,这就为使用递归提供了方便。在分治法中用递归的思想求解问题是计算机科学解决问题时常有的一种手段,由此也产生了很多高效的算法。

贪心算法的基本概念

贪心算法,又被称为贪婪算法,也是用来求解最优化问题的一种方法。一般来说,求解最优化问题的过程就是做一系列决定从而实现最优值的过程。最优解就是实现最优值的这些决定。动态规划考虑全局最优,得到的解一定是最优解。贪心算法是一种在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。贪心算法考虑局部最优,每次都做当前看起来最优的决定,得到的解不一定是全局最优解。但是在有最优子结构的问题中,贪心算法能够得到最优解。最优子结构就是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。虽然对于很多问题贪心算法不一定能得到最优解,但是它的效率高,所求得的答案比较接近最优结果。因此,贪心算法可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

(找零钱问题)

动态规划的基本概念

动态规划是求解最优化问题的一种方法。通常这种问题有很多解,每个解都对应一个值,最优化问题是希望找到一个对应最优值(最大值或最小值)的解。动态规划与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的,即子问题之间具有重叠的部分。在这种情况下,如果用分治法求解就会重复的求解这些重叠的部分。而动态规划只会对这些重叠的部分求解一次并用表格保存这些解,如此一来就可以避免大量的重复计算。动态规划最特别的地方是自底向上的求解子问题并将这些子问题的解保存起来。这种用空间换取时间的方式大大提高了求解问题的效率。

(求最优解,最长增长子数列,背包问题)

动态规划求解问题的4个步骤

动态规划求解问题一般可以分为4个步骤:

  1. 定义最优解的结构。
  2. 递归的定义最优解的值。
  3. 以自底向上的方式计算最优解的值。
  4. 用第(3)步中计算过程的信息构造最优解。