分治法算法复杂度

分治法是一种常用的算法设计技巧,二分法就是其最常见的特例。所谓分治,分而治之也:

  • 分(divide):递归解决较小的问题
  • 治(conquer):从子问题的解构建原问题的解

一般来说,至少含有两个递归的程序才叫做分治法,只有一个递归的程序是不算的。下面来总结下分治法的算法复杂度问题,摘自《数据结构与算法分析——C语言描述》一书。