时间复杂度用于描述算法的运算量随输入规模增长的增长情况，进而可以用于估计算法在某一输入下的运算次数，并据此评判出算法效率的优劣。
函数的增长规模
记 $f(n)=n^3,g(n)=n^3+10n^2+100n$，
可以得到 $f(10000)=1000000000000,g(10000)=1001001000000$，
于是我们发现，当 $n$ 充分大时，$f(n)≈g(n)$，此时函数的大小可以用其最高阶项（$n$ 充分大时最大的一项）来近似表示。
记 $f(n)=n^2,g(n)=100n^2$，
可以得到 $f(10)=100,f(100)=10000,\frac{f(100)}{f(10)}=100,g(10)=10000,g(100)=1000000,\frac{g(100)}{g(10)}=100$，
于是我们发现，最高次项的常数项不影响函数的增长规模。
更严谨的表述是：
$$\forall\epsilon>0,\exists N>0,s.t.\forall n\ge N,\frac{|f(n)-g(n)|}{f(n)}<\epsilon$$
可以用分析学的方法来证明。
一元函数的 $\mathbf\Theta$ 记号
我们可以用 $\Theta$ 记号来描述函数增长规模的确界：
对一元函数 $f(n)$，令 $f(n)=\Theta(g(n))$ 当且仅当 $g(n)$ 是仅保留 $f(n)$ 的最高阶项且去掉该项前的常系数后的一元一项代数式。
需要说明的是，因为 $\log_xy=k\log_zy$，其中 $x=z^{\frac{1}{k}}$。所以当底数为常数时，$\log_xy$ 与 $\log_zy$ 的增长规模相同，应省略底数。
因为 $\log n^a=a\log n$，所以应当省略真数的指数。
更严谨的表述是：
$$f(n)=\Theta(g(n))\Leftrightarrow\exists c_1,c_2,N,s.t.\forall n\ge N,0<c_1g(n)\le f(n)\le c_2g(n)$$
一元函数的大 $\mathbf{O}$ 记号
很多时候，我们只需要证明 $f(n)$ 小于某个上界，而不关心它是否能达到这个上界，于是我们引入大 $\text{O}$ 记号。
$f(n)=\text{O}(g(n))$ 当且仅当 $n$ 充分大时 $g(n)\ge h(n)$，其中 $f(n)=\Theta(h(n))$。同样对于 $g(n)$，我们要求它仅含一项且省略常系数。
(浅显地说，$\text{O}(f(n))$ 就是指问题的复杂度不超过 $f(n)$，即 $\text{O}$ 规定了问题的上界)
更严谨的表述是:
$$f(n)=\text{O}(g(n))\Leftrightarrow\exists c,N,s.t.\forall n\ge N,0<f(n)\le cg(n)$$
$\mathbf\Theta$ 记号与大 $\mathbf{O}$ 记号
显然 $\Theta$ 记号的信息量大于大 $\text{O}$ 记号，那么为什么要引入大 $\text{O}$ 记号而不直接使用 $\Theta$ 记号表示函数增长性？
因为对于非显性函数，有时其最高次项的精确界是不好确定的。
考虑下面对一棵树做 DFS 的算法：
Function dfs(u):
size_u = 0
for v is the son of u:
for i = 1 : size_u:
for j = 1 : size_v:
do sth. O(1)
end loop
end loop
size_u = size_u + size_v
end loop
end Function
看起来对于每个节点 $v$，都进行了一个 $i$ 从 $1$ 到 $\text{O}(n)$、$j$ 从 $1$ 到 $\text{O}(n)$ 的时间复杂度为 $\text{O}(n^2)$ 的二重循环，共有 $\text{O}(n)$ 个节点，所以调用一次 dfs(root) 的复杂度应该是 $\text{O}(n^3)$。
但事实上，枚举 $i$ 和 $j$ 的部分可以看作是在树上枚举点对。显然每个点对都仅在其 LCA 处被枚举了一次，树上共有 $\text{O}(n^2)$ 个点对，所以时间复杂度的上确界为 $Θ(n^2)$。
记 $T(n)$ 表示输入规模为 $n$ 时的运算量，我们表述 $T(n)=Θ(n^3)$ 显然是错误的，但表述 $T(n)=\text{O}(n^3)$ 却是正确的。
对于一个 $n≤100$ 的问题，我们只需要确定 $T(n)=\text{O}(n^3)$ 即可基本确定算法可以在几秒内完成。在这种情况下，使用大 $\text{O}$ 记号比 $\Theta$ 记号要方便得多。
多元函数的 $\mathbf\Theta$ 记号与大 $\mathbf{O}$ 记号
多元函数的 $\Theta$ 记号定义非常复杂，但基本思想还是保留能反映函数增长性的若干项。
我们只举例说明：
$$n\log m+5m\log n+nm+nm\log n+n+m=\Theta(nm\log n+n\log m)$$
$$q\log n+nq=\Theta(nq)$$
多元函数的大 $\text{O}$ 记号与 $\Theta$ 记号之间的关系和一元函数的情形完全类似。
$\mathbf\Omega$ 记号
同样是渐进符号的一种，但相较于 $\Theta$ 记号与大 $\text{O}$ 记号，$\Omega$ 记号并不常用。
浅显地说，$\Omega(f(n))$ 指问题的复杂度不小于 $f(n)$，即 $\Omega$ 规定了问题的下界。
渐进符号
这里需要强调两个点：
第一个是，渐进符号正如其名，其表示的意思是，随着问题规模 $n$ 不断增加，计算量 $h(n)$ 的增加速度不小于 $f(n)$，不大于 $f(n)$，或者几乎与 $f(n)$ 一样。
而并不是说计算量近似等于 $f(n)$，因为当 $n$ 比较小的时候，可能会出现计算量远超 $f(n)$ 的情况。
此外，在渐进符号里常数也是被忽略的，也就是说 $Θ(af(n)+b)$ 和 $Θ(f(n))$ 是一样的。
第二个是，由于在算法竞赛中，我们往往需要考虑最坏情况。
也就是说即使出题人绝顶聪明，也没有任何一种数据能把你卡掉。
这就导致在 OI 或 ACM 中，$\text O$ 和 $Θ$ 的意义往往是一样的，因为只要能跑过就行了，最快能跑多快我们是不关心的。
这也是 $\text O$ 和 $Θ$ 经常被误用的比较主要的原因。
回到时间复杂度
我们用 $T(n)$ 表示输入规模为 $n$ 时程序的运算量。显然 $T(n)$ 是一个关于 $n$ 的函数。于是我们就可以用大 $\text{O}$ 记号或 $\Theta$ 记号来表示 $T(n)$ 的规模，这就是算法的时间复杂度。它描述的是在输入充分大时算法运算量的增长性。
对于一般的算法，$T(n)$ 的非最高阶项前的常系数不会比最高阶项的常系数高太多，同时最高阶项的常系数相对于算法能处理的数据规模也比较小（也就是说，我们很少会遇到诸如 $T(n)=10^{10}n^2+10^{100}n$ 的算法），所以非最高阶项和最高阶项的常系数对实际运算量的影响非常小，因此我们可以直接通过 $\Theta$ 记号 (或大 $\text{O}$ 记号）来估计算法的运算量数量级。
例如，对于 $T(n)=\text{O}(n^2)$，当 $n=1000$ 时，我们认为其运算量大约是 $10^8$ 数量级。而其实际运算量可能是其数量级乘上一个比较小的常系数，比如 $0.5×10^8$，可能是 $2×10^8$，但基本不可能是 $10×10^8$。
一般来说，计算机一秒可以完成的运算次数在 $10^8$ 数量级。这就是说，对于一个需要在 $1s$ 内解决的问题，我们要求其运算量的数量级不能超过 $10^8$。
注意
例如「时间复杂度为 $\text{O}(n^3\log 10^{15})$」的表达方法是不正确的，因为大 $\text{O}$ 符号内不应有常系数 $\log 10^{15}$。在上例中 $10^{15}$ 其实是 $t$ 的范围，于是应该将复杂度表述为 $\text{O}(n^3\log t)$。
如果该常系数（或常真数）在描述中没有对应的变量，可以写作「时间复杂度为 $\text{O}(n^3\log w)$，其中 $w\le 10^{15}$」。
此外，诸如「时间复杂度是 $\text{O}(10^8)$」之类的表述完全错误。复杂度必须是一个关于输入规模的函数，而不是一个常数（除非是 $\text{O}(1)$）。这句话的正确说法为「运算量大约是 $10^8$」或「运算量为 $10^8$ 左右」。
空间复杂度
空间复杂度用于描述算法所使用的空间的增长性。
设 $S(n)$ 表示输入规模为 $n$ 时所占用的空间大小， 我们同样可以用大 $\text{O}$ 记号或 $\Theta$ 记号来表示 $S(n)$ 的规模，这就是算法的空间复杂度。
显而易见的，我们有下述的定理：我们总能对某个算法做适当的修改，使得在其正确性与时间复杂度不变的情况下，空间复杂度不大于时间复杂度（确界）。
完成这一修改的方法是把算法中实际用到的所有空间改为动态申请，那么申请完 $S(n)$ 的空间的运算量已经为 $S(n)$，于是算法的时间复杂度不可能低于其空间复杂度（确界）。
因为在空间上，常数极为重要（例如，$256\text{Mib}$ 和 $512\text{Mib}$ 事实上可能是同样的空间复杂度只相差了两倍的常数），所以我们在实际解决问题时极少考虑空间复杂度，而是直接计算算法所需要的实际空间大小。
0 条评论