算法与复杂性相关笔记。 分治

Chapter 2. Divide-and-Conquer Algorithms

Recurrence relations

Master theorem:

$$T(n)=a T(\lceil n / b\rceil)+O\left(n^{d}\right)$$

for some constants (a>0) , (b>1) ,and (d ≥0) , then

$$T(n)= \begin{cases}O\left(n^{d}\right) & if d>log _{b} a \\ O\left(n^{d} log n\right) & if d=log _{b} a \\ O\left(n^{log _{b} a}\right) & if d<log _{b} a .\end{cases}$$

d代表非递归部分（即每次递归调用之外的操作）的时间复杂度的指数。

Example: 整数乘法的分治算法

$$T(n)=3 T(n / 2)+O\left(n\right)$$