看了第二章之后，发现算法和数学关系挺大的，很多的都要公式推导。公式明天慢慢用语法进行修改。

一、渐近上界记号 O

如果存在正常数 c 和自然数 n0，使得当 n≥n0 时有 f(n) ≤ cg(n)，则称函数 f(n) 当 n 充分大时有上界，且 g(n) 是它的一个上界，记做 f(n)=O(g(n)) 。即 f(n) 的阶不高于 g(n) 的阶。

  • 定理2-1

  • 定理 2-2：如果 n>m ，则 n%m < n/2 。

二、渐近下界记号 Ω

如果存在正常数 c 和自然数 n0，使得当 n≥n0 时有 f(n) ≥cg(n) ，则称函数 f(n) 当 n 充分大时有下界，且 g(n) 是它的一个下界，记做 f(n)=Ω(g(n)) 。即 f(n) 的阶不低于 g(n) 的阶。

  • 定理2-3

三、紧渐近界记号 θ

如果存在正常数 c1,c2 和 n0，使得当 n≥ n0 时有 c1g(n)≤f(n)≤ c2g(n)，则称函数 f(n) 与函数 g(n) 同阶，记做 f(n)＝θ(g(n))。即 f(n) 与 g(n) 的增长阶数相同。

  • 定理2-4

四、非紧上界记号 o

如果对于任何正常数 c > 0 都存在正整数 n0 > 0，使得当 n ≥ n0 时有 f(n)＜cg(n) （等价于:n→∞时，f(n) / g(n) →0），则称函数 f(n) 当 n 充分大时的阶比 g(n) 低，记做 f(n) = o(g(n))。

五、非紧下界记号 w

如果对于任何正常数 c > 0 都存在正整数 n0 > 0，使得当 n ≥ n0 时有 f(n)＞cg(n) （等价于:n→∞时，f(n) / g(n) →∞），则称函数 f(n) 当 n 充分大时的阶比 g(n) 高，记做 f(n)＝w(g(n))。

渐近分析中函数比较

思考题：证明O(f(n))+O(g(n)) = O(max{f(n),g(n)})

算法按时间复杂度分类

附录：渐近分析记号的若干性质

（1）传递性：

（2）反身性：

（3）对称性：

（4）互对称性：

（5）算术运算：

附录：算法渐近复杂性分析中常用函数

取整函数

指数函数（ 对于正整数m,n和实数a>0）

对数函数

阶乘函数

版权声明：本文为博主原创文章，如有错误，恳请大家在评论区指出，在下不胜感激～如要转载注明出处即可～