本章内容

• 复杂性函数的阶
• 和的估计与界限
• 递归方程

1.一些记号

​ a. $\lfloor x \rfloor$ 表示小于等于$x$的最大整数;

​ b. $\lceil x \rceil$ 表示大于等于$x$的最小整数;

​ 即： $x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \le x+1$

​ c. $\lfloor x \rfloor$ $log(n) = lg(n) = log_2(n)$ ​ 为何此处不显示$log(n) = lg(n) = log_2(n)$

​ d. $In(n) = log_e(n)$

2.复杂性函数的阶

2.1. 渐近复杂性

​ 定义：当输入规模趋于极限情形时的复杂性

​ 表示复杂性阶的三个记号：

​ a. $T(n) = O(f(n))$

​ 若存在$c>0$，和正整数$n_0 \ge1$，使得当$n \ge n_0$时， 有$T(n) \le c*f(n)$成立,

​ 给出算法复杂度的上界，不可能比$c*f(n)$更大;

​ b. $T(n) = \Omega(f(n))$

​ 若存在$c>0$，和正整数$n_0 \ge1$，使得当$n \ge n_0$时， 有$T(n) \ge c*f(n)$成立,

​ 给出算法复杂度的下界，不可能比$c*f(n)$更小;

​ c. $T(n) = \Theta(f(n))$

​ 若存在$c_1,c_2>0$，和正整数$n_0 \ge1$，使得当$n \ge n_0$时， 有$c_1*f(n)\le T(n) \le c_2*f(n)$成立,

​ 给出算法复杂度的上界和下界

2.2多项式时间与指数时间

​ 设每秒可做某基本运算$10^9$次，$n=60$:

	算法1	算法2	算法3	算法4	算法5	算法6
复杂度	$n$	$n^2$	$n^3$	$n^5$	$2^n$	$3^n$
时间	$6*10^{-8}$s	$3.6*10^{-6}$s	$2.16*10^{-4}$s	0.013min	3.66世纪	$1.3*10^{13}$世纪

​ 根据上表可以得出结论：

• 多项式时间的算法互相之间虽有差距，一般可接受
• 指数量级时间的算法对于较大的 $n$ 无实用价值

​