4. 时空复杂度
在本章中, 我们将简述复杂度渐进分析的基本概念和方法.
我们首先需要明确几点:
- 本章节所分析的对象是 程序的复杂度, 也就是对程序运行时所占用的资源大小的估计. 在本章中, 我们主要关心的对象是程序的 运行时间.
- 在本章中, 我们缩关注的程序运行时间为 最坏状况下程序运行所需的最长时间.
- 本章仅介绍复杂度分析的基本概念, 不会涉及对复杂程序和算法的时间复杂度分析.
- 在本章中, 我们将不同操作和运算所消耗的时间进行归一化, 也就是假定赋值运算, 数值计算, 内存访问等操作所需要的时间基本一致, 从而简化复杂度分析的难度.
时间复杂度及渐进分析
我们考虑下面的这个简单的例子:
1
2
3
r := x; d := 0;
while y<= r do
d := d+1; r := r-y;
下面对这个程序的时间复杂度进行分析:
我们首先关注的是程序在运行过程中执行了多少次基础操作, 如赋值和数值运算. 可以看出, 程序的第一行中执行了两个赋值语句, 而第二行则执行了一次循环条件判断.
在循环体中, 每次循环程序均会执行两次赋值和两次数值运算. 由此看出, 执行一次循环所需要执行的基础操作为: 一次条件判断 + 两次赋值 + 两次数值运算 = $5$.
而不难看出, 该程序的功能是计算 $\text{int}(r / y)$, 因此可以得出循环总共会执行 $\lfloor \frac{r}{y} \rfloor$ 次.
因此, 可以得出, 该程序执行一次的时间消耗为
\[3 + 5 \cdot \lfloor \frac{r}{y} \rfloor.\]不难看出, 该程序的时间消耗介于 $O(1)$ 和 $O(n)$ 之间.
[这里应该补充 “eventually dominate” 的定义和一些例子, 但是鉴于该内容已经在COMP11120中详细介绍过, 因此不再赘述.]
[这里应该附上 $O(k), O(\log n), O(n), O(n\log n), O(n^2), O(k^n)$ 的对比图, 但由于同样的原因不再赘述]
$O(n)$ 符号的定义及基本性质
定义 ($O(n)$)
若对 $f \in O(g),~~ g: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0}$, 则存在 $k \in \mathbb{N}, C \geq 0$ 使得对所有 $n > k$: \(f(n) \leq C \cdot g(n).\)
引理 1
\[f \in O(f).\]
[证明]
取 $k = 0, ~~C= 1$. 则对 $\forall~ n \in \mathbb{N}$:
\[f(n) = Cf(n) \leq Cf(n).\]引理 2
\(O(1) \subsetneq O(n)\) 即: $O(1)$ 是 $O(n)$ 的真子集.
[证明]
不妨设 $f \in O(1)$. 则存在 $k$, 使得对于 $\forall~ n > k$: \(f(n) \leq C\cdot 1 = C\)
取 $k’ = \max(1, k), ~~ C’ = C$. 则对 $\forall n > k’$, 有:
\[f(n) \leq C \leq Cn.\]故有
\[f \in O(n).\]取 $g(n) = n$, 其显然在 $O(n)$ 而不在 $O(1)$ 中. 故真包含关系证毕.
引理 3
对多项式 \(g(n) = a_kn^k + a_{k-1}n^{k-1} + \cdots + a_1n + a_0\) 若 $a_k > 0$. 则有 $O(g) = O(n^k).$
[证明]
不妨设 $f \in O(g)$. 由定义知: $\exists ~K, C$ 使得 $n> K:$
\[f(n) < C \cdot g(n)\]由 $n\geq 1, i>j: n^i > n^j.$ 故取
\[K' = \max(1, K), C' = \sum_{i=0}^{k}C\vert a_i\vert\]则有
\[f(n) \leq C'n^k\]进一步得
\[f \in O(n^k).\]下面假设 $f \in O(n^k)$. 则存在 $K, C$ 使得对于任意 $n>k$:
\[f(n) \leq Cn^k\]此时取
\[K' = \max(1, K), ~~ C' = \frac{C}{a_k}\]则有
\[f(n)\leq C'g(n).\]故双包含证毕.
引理 4
\[O(n^m) \subsetneq O(n^{m+1}).\]
引理 5
\[O(1) \subsetneq O(\log n) \subsetneq O(n).\]
