算法分析

时间代价分析 f(n) 与空间代价分析 s(n)

Growth rate（增长率）

算法性能分析关注代价函数 f(n) 的增长率

一般的代价函数增长率：小 => 大

$c$，$log_{2}n$，$n$，$nlog_{2}n$，$n^{2}$，$n^{3}$，…，$n^{k}$，$2^{n}$，n!

估计代价函数 f(n) 的增长度作为算法时间复杂度的测度

Big-$O$ Notation（最大描述）

$$f(n) \le O(g(n))$$

当 $n$ > $n_{0}$ 时，$f(n) \le cg(n)$ ，即 $cg(n)$ 是 $f(n)$ 的上限，代价函数的 $O$ 描述不唯一，但应该取更加紧凑的上限

Big-$\Omega$ Notation（最小描述）

$$f(n) \ge \Omega(g(n))$$

$\Omega$ 描述是代价函数的最小描述，与 $O$ 描述类似，取紧凑的下限

Big-$\Theta$ Notation（最大 = 最小时描述）

当 $O$ 描述与 $\Omega$ 描述相等时，可以写成 $\Theta$ 描述

每一个 f(n) 都有其对应的 $f_{best}(n)$ | $f_{worse}(n)$ | $f_{ave}(n)$

其中都有各自对应的 O/$\Omega$ 描述，但一般只对 $f_{ave}(n)$ 进行描述