算法导论(二)

算法分析

一、 渐进符号

O符号 (大O符号)

定义: $f(n) = O(g(n)) f(n) 属于 g(n)的函数集, \exists$常数c, n₀ c> 0 , n₀ > 0

使得 $f(n) \leq O(g(n))$ 对于充分大的 n 成立, n >= n₀

Ex: $ 2n^2 = O(n^3) $ 等号是不对称的

$$O(g(n)) = \{ f(n) |\ \exists ,c > 0, n_0 > 0, 使得\ f(n) \ 以\ 0 和\ c *g(n)为界\ 0 \leq f(f(n)) \leq c *g(n) \ for \ all \ n \geq n_0 \}$$

不是等于 => 是一种 属于的关系

用法

$ f(n) = n^3 + O(n^2)$ 表示

$ f(n) = n^3 + O(n^2) \ \exists h(n) \in O(n^2) => f(n) = n^3 + h(n) , 存在 n > n_0$

有低阶项以某个常数 * $n^2$ 为 界

Ex $ n^ 2 +O(n) = O(n^2)$ 此处不对称, 表示 is

任何$n^2 +O(n)$ 都是 $O(n^2)$ 反之不然

$ means \ for \ any \ f(n) \in O(n) \ there \ is \ an \ h(n) \in O(n^2) \ such \ that \ n^2 + f(n) = h(n) $

Ω符号 (大Ω符号)

$\theta$ 符号 (大$\theta$符号)

二、 严格符号

o 符号 (小o符号)

ω 符号 (小ω符号)

解递归式