另一种阅读体验


时间复杂度

时间复杂度用于描述算法的运算量随输入规模增长的增长情况,进而可以用于估计算法在某一输入下的运算次数,并据此评判出算法效率的优劣。

函数的增长规模

记 $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}$ 事实上可能是同样的空间复杂度只相差了两倍的常数),所以我们在实际解决问题时极少考虑空间复杂度,而是直接计算算法所需要的实际空间大小。

分类: 文章

Audrey_Hall

I am trying to bribe you with uncertainty, with danger, with defeat.

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。

*

code