主定理.png
应用
二分搜索
- 每次问题规模减半，a=1，b=2，d=0
- 复杂度为n^0 log(n) = log(n)。
快速排序
- 随机选择待排序序列中的一个数字作为划分字问题的标准，划分是否平均影响算法复杂度
- 快速排序在每次平分的情况下，每次划分的代价都是O(n)
- 每次问题规模减半，a=2，b=2，d=1
- 复杂度为n log(n)
- 最差情况下，复杂度为O(n^2)
归并排序
- 数据列均分为两部分，分别排序，之后以O(n)的复杂度进行合并，空间复杂度O(n)
- 每次问题规模减半，a=2，b=2，d=1
- 复杂度为n log(n)
顺序统计量问题
T(n)=T(n/2)+O(n)
O(n)：和快速排序的划分过程一样
期望复杂度:O(n)
基数排序(Radix sort)
- 对于待排序的整数序列，从最低位到最高位每次按照相应的位排序一次
- 每次递归问题规模变为原来的1/10，但需要求解10个子问题，额外运算为O(n)的，a=10，b=10，d=1
- 复杂度为n^1 log(n) = n log(n)，近似为O(kN)，k为整数的位数
快速傅里叶变换：FFT
- 每次问题规模减半，a=2，b=2，d=1
- 复杂度为n log(n)
Karatsuba快速乘法
- 正常两个n位数乘法为n^2
- 算法把两个乘数各分为高低位两部分，如X*Y = (a+b) * (c+d) = ac+bd + (bc+ad) = ac+bd+(ac+bd - (a-b)(c-d)) 只需要ac,bd,(a-b)(c-d)三次乘法
- 每次问题规模减半，但需要解3个子问题，加法是O(n)的，a=3，b=2，d=1 复杂度为n^log2(3)
