复杂度分析

ToC

缘起

大O标记法分析程序的时间或者空间复杂度网络上相关的内容比较多,通常也是围绕着怎么去计算一个算法的复杂度方向上去的

于是我浅看了一下这方面的东西,了解了一些奇怪的知识

定性资源消耗

大O标记法是一种定性分析算法资源消耗变化的一种表示方法

表示复杂度

定义

复杂度用于描述一个函数的增长快慢,即增长率的大小

这就是大O标记法

定义中的 $c$ 用来忽略常数

例如:对于较小的 N 值使得 1000N 比 $N^2$ 要大,但这不代表 $1000N$ 的增长速度比 $N^2$ 大,这种情况下 N = 1000 是转折点($n _ 0$),当 $N > n _ 0$ 时,$N^2$ 总是 至少 与 $1000N$ 一样大 (c = 1);同样,也可以取 $n _ 0 = 10, c=100$. 因此可以说 $1000N = O(N^2)$

不过好像不太对?1000N 应该是 O(N) 才对,为什么是 O(N^2)???

其实都是对的,套用上面的公式,即 $f(N) = N$,让 c 取 1000, $n _ 0$ 取任意正常数,最后不等式依旧成立,你甚至可以取 O(N^k)... (k>=1)

但就不能是 O(1),因为无论 c 和 $n _ 0$ 取啥,上面的不等式都不满足

其实我们常常使用的大O计数法是满足条件下最"小"的 $O(f(N))$,因为这样更符合真实的复杂度,这种标记法其实就是接下来的 $\Theta$ 标记法

所以大O计数法是描述一个 worst 的情况,任何情况下的复杂度都不可能比 $f(N)$ 大

和大O标记法很像,描述的是一个 best 的情况,任何情况下的复杂度都不可能比 $g(N)$ 小

在上面的例子里,1000N 可以等于 $\Omega(N)$,甚至可以是 $\Omega(1)$

这就是我们常常使用到的大O标记法

在上面的例子里,$1000N = O(N)$ 且 $1000N = \Omega(N)$,所以 $1000N = \Theta(N)$

此时就不能让 $1000N = \Theta(N^2)$[$1000N = O(N^2), 1000N \not= \Omega(N^2)$] 或者 $1000N = \Theta(1)$[同理] 了

这也是在计算复杂度所用到的

有时候也可以说: 如果 $T(N) = O(p(N))$ 且 [$T(N) \not= \Theta(p(N))$ 或 $T(N) \not= \Omega(p(N))$],那么 $T(N) = o(p(N))$

它和大O标记法很像,但是它是不等式不取 = 的情况

一般叫它 小o标记法,或者有一个更亲切的名字 高阶无穷小,即 T(N) 是 p(N) 的高阶无穷小

为什么会蹦出一个高阶无穷小?

看下面就明白了

复杂度计算

常规的通过数程序 for 循环的层数,数执行的行数来算复杂度就过了,很简单,网上也有一堆教程

来点奇怪的:

用极限去计算复杂度

前提是知道要分析的复杂度的函数的表达式(既然都知道表达式了为什么不直接看,就能得出复杂度了呢...

其实算法程序里面,算法的执行流程函数是很简单的不定次多项式,最多出现个log, n!,不太可能出现 sin(x), sgn(x) 的奇怪流程,所以能得出算法最后执行流程的函数,基本上一眼就能看出复杂度

说不准哪一天有个人突发奇想,设计了一个 O(sgnN) 的算法呢 (bushi

求 $lim _ {N \to \infty} \frac{f(N)}{g(N)}$,具体怎么求?洛就完事了

会有以下情况

这不就是高级无穷小,连符号都一样

这其实就是等价无穷小.. 可以记为 $f(N) \sim g(N)$

这个时候,就可以得到 f(N) 的复杂度就是 O(g(N)) 了

例如:

$\lim _ {N \to \infty} \frac{1000N}{N} = 1000$ 这时 1000N = O(N)

同理

这种情况一般不会出现

注意

虽然复杂度相加公式是 $T _ 1(N) = O(f(N))$ $T _ 2(N) = O(g(N))$ $T _ 1(N) + T _ 2(N) = O(f(N) + g(N))$

这里的 $O(f(N) + g(N))$ 要理解成对 $f(N) + g(N)$ 再次计算大O标记法

或者不正式的理解成 $T _ 1(N) + T _ 2(N) = max(O(f(N)), O(g(N))$

O(2N) 需要写成 O(N),O(N^2 + N) 要写成 O(N^2)

不要写成 $f(N) \le O(g(N))$ 来凸显出 $f(N)$ 的复杂度比 $O(g(N))$ 小,因为在大O标记的定义中,就已经有不等式关系了,这无法体现

例如 令 10N = O(N^3),写出 1000N <= O(N^3) 来凸显 1000N 比 10N 复杂度低是错误的,因为它们都是 $\Theta(N)$

不要写出 $f(N) \ge O(g(N))$ 来凸显 $f(N)$ 的复杂度比 $O(g(N))$ 大,这恒成立的,它没有意义

结语

奇怪的知识又增加了

参考

  1. Data Structures and Algorithm Analysis in Java