数据结构1

算法分析

比较：由小到大，“常对幂指阶”
加法规则：$O(f(n))+O(g(n)) = O(\max(f(n),g(n)))$
乘法规则：$O(f(n))\times O(g(n)) = O(f(n)\times g(n))$
扩展递归技术：用于求解递推关系式。扩展就是根据递推式替换等式右边项，依此下去，会得到一个求和表达式，求和得到问题的解。
对于一个分治/递归算法，列出关系式（比如f(n)=...f(n/2)...，或者f(n)=...f(n-1)...）。
确定最小规模（比如$n/2^k=1$或$n-k=1$），使得右边的项最小只能到f(1)，算出k等于多少
从第0层开始，一直替换到最小规模（即第k层）
累加：从第0层加到第k层，算时间复杂度，其中，T(1)=O(1)
主定理：若有$T(n)=aT(\frac{n}{b})+f(n)，其中a\ge1,b\gt1$
其中，假设每个子问题的规模都一样为$\frac{n}{b}$，f(n)为递归以外的计算，$\epsilon>0$，$c<0$
小于关系：若$f(n)=O(n^{\log_b a-\epsilon})$，则$T(n)=O(n^{lon_b{a}})$
等于关系：若$f(n)=\Theta(n^{\log_ba})$，则$T(n)=O(n^{lon_b{a}}\log n)$
大于关系：若$f(n)=\Omega(n^{\log_b a+\epsilon})$，若$af(n/b)\le cf(n)$，则$T(n)=O(f(n))$
- 注意，大于关系有两个条件