分类与分治思想

By | 2016-09-08

写在前面

类是揭示概念外延(概念所反映事物的范围)的逻辑方法,也是求解问题的一种基本思想方法。

分治是特殊分类,通常与递归联系在一起。

分类和分治的解题步骤

  1. 确定对象
  2. 合理分类
  3. 逐步讨论
  4. 归纳结论

作用

能够是繁复的问题条理化简单化,通过对各类情况“分而治之”,达到解决整体的复杂问题的目的。

二分法

二分法是一种最常用的分类或分治方法。二分法的要点如下:

  1. 选取一个标准,按照是否符合这个标准将所需讨论的问题分成两类。
  2. 在前次分类的基础上,选取另一个标准将已分出的类再分成两类。
  3. 不断重复前一个过程,直至不能够再分为止。

尽管二分思想本身很简单,但它的扩展性之强、应用面之广,或许仍是我们所未预见的。

1. 应用于一般有序序列的二分法

  • 在给定的序列中“二分查找”
    • 注:不要想当然地认为二分查找的时间效率一定是log2n
  • 将“二分插入”应用于交互式问题

2. 应用于退化了的有序序列的“二分枚举”

二分枚举与二分查找相比,最大的区别在于,在判断选择哪一部分递归调用时没有了比较运算。

  • 用二分枚举求可行方案
    • 用二分枚举将最优性问题转化为可行性问题(退一步海阔天空)
  • 用二分枚举求最优性问题
    • 欲进先退

3. 应用于无序序列的“二分搜索”

  1. 在“二分搜索”的基础上构造可行解
  2. 在“二分搜索”的基础上构造最优解

注意点

  • 难点在于构造查找对象(多接触、多思考、多积累)
  • 具体问题具体分析

4. 应用于多维情况的“多重二分”

二分”思想和“降维”思想结合的产物

二维线段树属于这一类

结语

  • 不要让二分思想仅停留在对有序数组进行二分查找的层次上,而应该扩展到更广泛的应用上
  • 扎实的基本功、丰富的解题经验、大胆合理的猜测以及活跃的创造思维是根本(以不变应万变

发表评论

电子邮件地址不会被公开。