缘起
大O标记法分析程序的时间或者空间复杂度网络上相关的内容比较多，通常也是围绕着怎么去计算一个算法的复杂度方向上去的
于是我浅看了一下这方面的东西，了解了一些奇怪的知识
定性资源消耗
大O标记法是一种定性分析算法资源消耗变化的一种表示方法
- 为什么是定性：大0标记法省去了低阶项，省去了常数，所以无法定量计算算法的资源消耗，大多少情况下，我们只需要大致知道这个算法的资源消耗的变化情况
- 什么是资源：通常分为时间和空间，即算法的运行时间和消耗的内存
- 还有其他的标记法吗：还有有 $o, \Theta, \Omega$ 等标记法
表示复杂度
定义
复杂度用于描述一个函数的增长快慢，即增长率的大小
- 如果存在正常数 $c$ 和 $n _ 0$ 使得 $N \ge n _ 0$ 时， $T(N) \le cf(N)$ ,则记为 $T(N) = O(f(N))$
这就是大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)$ 大
- 如果存在正常数 $c$ 和 $n _ 0$ 使得 $N \ge n _ 0$ 时，$T(N) \ge cg(N)$ ,则记为 $T(N) = \Omega(g(N))$
和大O标记法很像，描述的是一个 best 的情况,任何情况下的复杂度都不可能比 $g(N)$ 小
在上面的例子里，1000N 可以等于 $\Omega(N)$，甚至可以是 $\Omega(1)$
- 如果 $T(N) = O(h(N))$ 且 $T(N) = \Omega(h(N))$ 时，可以记为 $T(N) = \Theta(h(N))$
这就是我们常常使用到的大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)$[同理] 了
这也是在计算复杂度所用到的
- 如果对任意正常数 $c$ 都存在一个常数 $n _ 0$ 使当 $N > n _ 0$ 时 $T(N) < cp(N)$ ，则 $T(N) = o(p(N))$
有时候也可以说: 如果 $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)}$，具体怎么求？洛就完事了
会有以下情况
- 极限是 0: 表示 $f(N) = o(g(N))$
这不就是高级无穷小，连符号都一样
- 极限是 c(c不等于0): 表示 $f(N) = \Theta(g(N))$
这其实就是等价无穷小.. 可以记为 $f(N) \sim g(N)$
这个时候，就可以得到 f(N) 的复杂度就是 O(g(N)) 了
例如:
$\lim _ {N \to \infty} \frac{1000N}{N} = 1000$ 这时 1000N = O(N)
- 极限是 $\infty$: 表示 $g(N) = o(f(N))$
同理
- 极限摆动: 表示 f(N) 和 g(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标记中不要出现常数和低阶项
O(2N) 需要写成 O(N)，O(N^2 + N) 要写成 O(N^2)
- 不要写成 $f(N) \le O(g(N))$ 或者 $f(N) \ge O(g(N))$
不要写成 $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))$ 大，这恒成立的，它没有意义
结语
奇怪的知识又增加了
参考
- Data Structures and Algorithm Analysis in Java