那就默认是对的吧qwq
主定理
定义
如果我们要解决规模为$n$的问题,通过分治,得到$a$个规模为$\frac{n}{b}$的问题,每次的额外复杂度为$O(n^d)$
$T(n) <= aT(\frac...实际应用
肯定就是分析算法复杂度啦。。...二分搜索
$a = 1, b = 2, d = 0$
复杂度:$O(logn)$
归并排序
$a = 2, b = 2, d = 1$
复杂度:$O(nlogn)$
基数排序
$a= 10, b = 10..., d = 1$
复杂度:$O(nlogn)$ ?...FFT
$a = 2, b = 2, d = 1$
复杂度:$O(nlogn)$
Karatsuba快速乘法
$a = 3, b = 2, d =1$
复杂度:$O(n^{log_2^3})$
参考资料