第二章只有一个知识点

计算时间的渐进表示

定义

记住这几个定义，以后的整明全靠这些定义了。



这几个分别表示，g(x)是f(x)的：渐进上界、渐进下界、渐进确信界。（考试说这几个词知道是啥就行）

这个定理说是定理，不如说就是个例子而已…

O的时间比较

从计算时间上把算法分为两类：

多项式时间算法：

指数时间算法：

这里有一道考试题我得去问一下再更新。

证明

考试真题里有一道很像的，不过是把O换成Ω，max换成min而已，思路应该一样的。

幸好我已经有心理预期，这里f’(n)是另一个函数而已，你可以把它看成F(n)，不是导数。

总体证明过程就是：
1.p(n)=max{f(n),g(n)}（看题里是要求什么）
2.设两个函数F(n)=O(f(n))和G(n)=O(g(n))
3.F(n)+G(n)分别通过定义展开得到与(c1+c2) ∗ * ∗p(n)的关系
4.c3=c1+c2，n3=max{n1,n2}（这个也是根据题来的），得到F(n)+G(n)与c3 ∗ * ∗p(n)的关系