202604301621分治法复习

分治法并不仅只能二分，解决子问题，合并。根据《算法导论》，它有三种形式，

1. 替换模型。猜一个bound，然后用数学归纳法证明其正确。
2. 递归树模型。
3. 主方法（master method）。形如 $T(n)=aT(n/b)+f(n)$,where $a\ge 1,b>1,f(n)$ is a given function.

怪不得 maximum-subarray 这么爱考，原来是出自算法导论。