算法复杂度分析

时间复杂度分析

渐进分析 Asymptotic analysis

如果存在 $c > 0, n_{0} > 0$ ，对于所有的 $n \geq n_{0}$ 都有 $0 \leq f (n) \leq c g (n)$ ，则 $f (n) = O (g (n))$

比如说 $2 n^{2} = O (n^{3})$ ，我们取 $c = 1, n_{0} = 2$

如果存在 $c > 0, n_{0} > 0$ ，对于所有的 $n \geq n_{0}$ 都有 $0 \leq c g (n) \leq f (n)$ ，则 $f (n) = Ω (g (n))$

比如说 $n = Ω (l g n)$ ，我们取 $c = 1, n_{0} = 16$

如果存在 $c_{1} > 0, c_{2} > 0, n_{0} > 0$ ，对于所有的 $n \geq n_{0}$ 都有 $0 \leq c_{1} g (n) \leq f (n) \leq c_{2} g (n)$

比如说 $n^{2} + 2 n = Θ (n^{2})$

正确性分析与证明、时间复杂度分析、空间复杂度分析、最坏情况分析、平均情况分析、聚合分析

tags	基础知识, 算法
aliases	Algorithm Complexity Analysis