算法导论第三章函数的增长

小咪咪 2022-07-16 00:16 201阅读 0赞

**渐近记号**  
（1）**渐近上界记号O（大写O）**  
含义：渐近地给出了一个函数在常量因子内的上界：

*  O(g(n))=\{f(n):存在正常量c和n0，使得对所有n>=n0,有0<=f(n)<=cg(n)\}
 *  f(n)=Θ(g(n))蕴含着符f(n)=O(g(n))
 *  O可用于标记最坏的运行时间  
    **f(n)=O(g(n))的曲线图**  
    ![这里写图片描述][20160925190517586]  
    （注意n0和c的值）

（2）渐进下界记号Ω（大写Ω）  
含义：渐进的给出一个函数在常量因子的下界

*  Ω（g(n)）=\{f(n):存在正常量c和n0，使得对所有n>=n0,有0<=cg(n)<=f(n) for all n>=n0\}
 *  f(n)=Θ(g(n)蕴含了f(n)=Ω(g(n))  
    **f(n)=Ω(g(n))曲线**  
    ![这里写图片描述][20160925191602576]

**渐进紧确界记号Θ**  
含义：渐进的给出了一个函数的上界和下界，

*  Θ(g(n))=\{f(n):存在常量c1、c2和n0，使得对所有的n>=n0,有0<=c1g(n)<=f(n)<=c2g(n)\}  
    **f(n)=Θ(g(n))的曲线**  
    ![这里写图片描述][20160925192510182]
 *  f(n)=Θ(g(n))的确切含义是：f(n)∈Θ(g(n))
 *  Θ(g(n))的定义要求其每个元素渐进非负，也就要求g(n)本身渐进非负。
 *  Θ(g(n))中的所有函数有相同的最高阶项
 *  f(n)∈Θ(g(n))，当且仅当f(n)∈O(g(n))&&f(n)∈Ω(g(n))

**eg：形式证明(n\*n)/2-3\*n=Θ(n\*n)**

*  首先确定正常数c1，c2和n0，使得对所有n>=n0,有：
 *  c1\*n\*n<=(n\*n)/2-3\*n<=c2\*n\*n
 *  除去n\*n得：c1<=1/2-3/n<=c2
 *  右边不等式在n>=1,c2>=1/2时成立，左边不等式.n>=7,c1<=1/14时成立，选c1=1/14，c2=1/2，n0=7时。上式成立。

**非渐进紧确上界记号o(小写0)**

![这里写图片描述][20160925204209615]  
如果f(n)=o(g(n))，那么n当趋于无穷时，f(n)相对于g(n)变得微不足道。  
![这里写图片描述][20160925202859318]

**非渐进紧确下界记号：ω**

![这里写图片描述][20160925205010868]  
\- 如果f(n)=ω(g(n)),那么当n很大时候，f（n）相对于g（n）变得任意大了，  
![这里写图片描述][20160925204927830]  
\- 如果f(n)∈ω(g(n)),当且仅当g(n)∈o(f(n));  
**使用极限去定义渐进符号**  
![这里写图片描述][20160925205446133]

五种符号的关系：  
![这里写图片描述][20160925205937843]

其实上述的这些符号表示的都是一个集合，一般我们对算法复杂度的描述都是用O记号。

**性质**  
![这里写图片描述][20160925222241831]  
![这里写图片描述][20160925222254613]

[20160925190517586]: /images/20220716/42e1106d4f464011ad11c9729aaa4cbd.png
[20160925191602576]: /images/20220716/3161c56a5c4f419fbdd8341fa0ff4abe.png
[20160925192510182]: /images/20220716/154cebfd91574a51bfafa3b78d323168.png
[20160925204209615]: /images/20220716/02290cd5c2e1417c801c9ab2c5864e0b.png
[20160925202859318]: /images/20220716/aeab07a9d9b949c69ada46882a5d725b.png
[20160925205010868]: /images/20220716/f5ee96a64c144c0f8abb8af02f8a3762.png
[20160925204927830]: /images/20220716/7d22cc5c95d04e4a80e88f700652c85a.png
[20160925205446133]: /images/20220716/97e071e3f85b4c16bdd1ab7566af8527.png
[20160925205937843]: /images/20220716/3d67b03ba24b445dab916b6769ccc0c2.png
[20160925222241831]: /images/20220716/d38dde65d5f24a579d31851941325ace.png
[20160925222254613]: /images/20220716/e56a03e1c1c948c9aba89409d5e67174.png