邓俊辉《数据结构》学习笔记

P8 01-C-2

Notation	Meaning
大 $O$ 记号	给出复杂度的上界（即最坏的情形）
$\Omega$ 记号（也可以小写）	给出复杂度的下界（即最好的情形）
$\Theta$ 记号（也可以小写）	给出复杂度的确界

如下图所示：

[图片上传失败...(image-ae045d-1584752613060)]

对数复杂度的算法是非常高效的，因为对数复杂度无限接近于常数复杂度：
$\forall c> 0, \log n = O(n^c) \tag 1$

P11 01-D-2

幂方级数的时间复杂度：比幂次高出一阶
$\begin{aligned} & T_1(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} = O(n^2) \\ & T_2(n) = 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} = O(n^3) \\ & T_3(n) = 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4} = O(n^4) \\ & T_4(n) = 1^4 + 2^4 + \cdots + n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} = O(n^5) \end{aligned} \tag 2$
收敛级数的时间复杂度：为常数时间复杂度
$\begin{aligned} & \frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \cdots + \frac{1}{(n-1) \times n} = 1 - \frac{1}{n} = O(1) \\ & 1 + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 1 + \frac{1}{2^2} + \cdots = \frac{\pi ^2}{6} = O(1) \\ & \frac{1}{3} + \frac{1}{7} + \frac{1}{8} + \frac{1}{15} + \frac{1}{24} + \frac{1}{26} + \frac{1}{31} + \frac{1}{35} + \cdots = 1 = O(1) \end{aligned} \tag 3$
两个特殊级数的时间复杂度：

调和级数： $h(n) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \Theta(\log n)$ ；
对数级数： $\log 1 + \log 2 + \cdots + \log n = \log(n!) = \Theta(n \log n)$ 。

（至 P12 01-D-3）