本章主要讲了渐近符号，初看晦涩难懂，其实主要是数学公式太多，“不求甚解”的态度就很好...
渐近记号
主要讲了三个渐近记号，对应三种情况， 分别是
的：
-
渐近上界：，对应最坏复杂度，
-
渐近下界：，对应最好时的复杂度，
-
渐近确界：，最强的，同时包含了
渐近上界和渐近下界，
书中的定义看起来很复杂，其实可以简单理解为无穷大的阶的问题。当时，
分别是
的：
-
非渐近紧确的上界：，高阶无穷大，
-
非渐近紧确的下界：，低阶无穷大，
-
渐近确界：
所谓非渐近紧确的，就是上面的不等式里面不能取等号的。
各种比较关系
书中写的传递性、自反性、对称性、转置对称性等，其实就是不等式的传递
最坏复杂度分析
通常算法分析使用渐近上界，即最坏情况的复杂度，按照马克思的说法就是找到事物的主要矛盾，一般是找到
等阶无穷大，取式子里最高阶的那项。
常见复杂度
一般记住下面的强弱关系就行了：
还有一个常用结论：
标准记号和常用函数
这里也没啥好讲的，复习复习数学知识就好了。
不如顺便来学一下 Latex公式编辑器的语法吧...
Latex 公式语法
Latex是一种强大的排版语法。行内公式写法为$内容$，块级公式写法为两个$：$$内容$$
不等式$\lt f(n) \le cg(n)$：
分式\frac{分子}{分母}：
极限lim_{n\to \infin}f(n)：
向下取整\lfloor 和 \rfloor：
向上取整\lceil 和 \rceil：
模等价 9\equiv 3 \pmod{6}:
多项式求和：
p(n) = \sum_{i=0}^n a_in^i
指数（上标）a^b:
下标 `a_1·：
对数log_a^b:
插播几个对数公式
a = b\log_b^a \\
\log_c^{(ab)} = \log_c^a + \log_c^b \\
\log_b^{a^n} = n\log_b^a \\
\log_b^a = \frac{\log_c^a}{\log_c^b} \\
a^{\log_b^n} = n{\log_b^a} \\
网友评论