算法课笔记(持续更新)

这段时间学校采用线上课上课方式，由于没有课本，只能把笔记记在博客上了，大部分图片来自亲老师的课件，我猜老师不会无情到追究版权问题吧 ????

---

函数渐进的界

渐进上界O
算法在任何实例情况下，其时间复杂性的阶不超过g(n)的阶,f(n)=O(g(n))。
即对于f(n)这个实例复杂性的集合，所有的阶都小于等于g的阶，但是fmax(n)的阶必须等于g的阶。

非紧渐进上界o
算法在任何实例情况下，其算法时间复杂性的阶小于g(n)的阶，f(n)=o(g(n)).
即对于f(n)这个实例复杂性的集合，所有的阶都小于等于g的阶，而且fmax(n)的阶必须小于g的阶。

渐进下界Ω
算法在任何实例情况下，其时间复杂性的阶不低于g(n)的阶，f(n)=Ω(g(n))。
所有的阶都大于等于g的阶，但是fmin(n)的阶必须等于g的阶。

非紧渐进下界ω
算法在任何实例情况下，其时间复杂性的阶大于g(n)的阶， f(n)=ω(g(n)).

渐近紧确界Θ
若f(n)=O(g(n))，且f(n)=Ω(g(n))， 则称f(n)=Θ(g(n))

几个函数的渐进

log(n!) = Θ(nlogn)

n! = o(nⁿ) = ω(2ⁿ)

调和级数 = ln(n) + O(1)

主定理

对于递推方程T(n) = a T(n/b) + f(n)
a: 规约后子问题个数
n/b: 规约后子问题的规模
f(n): 规约过程及紫褐子问题的解的工作量

需要注意主定理并不是对于所有情况都适用