算法分析与复杂性理论

2020-06-24  本文已影响0人  SunnyQjm

1. 函数渐进的界

1.1 大 O 符号

1.2 大 \Omega 符号

1.3 小 o 符号

1.4 小 \omega 符号

1.5 \Theta 符号

定义 说明
O fg 是定义域为自然数集N上的函数。若存在正数 cn_0 ,使得对于一切 n > n_00 \le f (n) \le cg(n) 成立,则称 f (n) 的渐进上界是 g(n),记作:f (n) = O(g(n)) f (n) = O(g(n))f (n) 的阶不高于 g(n) 的阶; 可能存在多个正数 c ,只要指出一个即可; 对前面有限多个值可以不满足不等式; 常数函数可以写作 O(1)
\Omega fg 是定义域为自然数集N上的函数。若存在正数 cn_0 ,使得对于一切 n > n_00 \le cg(n) \le f (n) 成立,则称 f (n) 的渐进下界是 g(n),记作:f (n) = \Omega(g(n)) f (n) = \Omega(g(n))f (n) 的阶不低于 g(n) 的阶; 可能存在多个正数 c ,只要指出一个即可; 对前面有限多个值可以不满足不等式;
o fg 是定义域为自然数集N上的函数。若对于任意正数 c 都存在 n_0使得对于一切 n > n_00 \le f (n) \le cg(n) 成立,则记作:f (n) = o(g(n)) f (n) = o(g(n))f (n) 的阶低于 g(n) 的阶; 对不同的正数 cn_0 不一样,c 越小 n_0 越大; 对前面有限多个值可以不满足不等式;
\omega fg 是定义域为自然数集N上的函数。若对于任意正数 c 都存在 n_0使得对于一切 n > n_00 \le cg(n) \le f (n) 成立,则记作:f (n) = \omega(g(n)) f (n) = o(g(n))f (n) 的阶高于 g(n) 的阶; 对不同的正数 cn_0 不一样,c 越小 n_0 越大; 对前面有限多个值可以不满足不等式;
\Theta f (n) = O(g(n))f (n) = \Omega(g(n)),则记作:f (n) = \Theta(g(n)) f (n) 的阶与 g(n) 的阶相同 对前面有限多个值可以不满足条件;

2. 函数渐进界的定理

2.1 定理1:Knowledge

2.2 定理2:

2.3 定理3:

4. 基本函数

4.1 对数函数

4.2 指数函数与阶乘

4.3 取整函数

4.4 按照阶排序 Knowledge

2^{2^n}, n!, n2^n, (\frac{3}{2})^n, (\log n)^{\log n} = n^{\log\log n}

n^3, \log{(n!)} = \Theta(n\log n), n = 2^{\log n}

\log^2n, \log n, \sqrt{\log n}, \log\log n

n^{\frac{1}{\log n}} = 1

5. 序列求和的方法

5.1 引例

\begin{aligned}(1). \sum_{k = 1}^{n - 1}\frac{1}{k(k + 1)}&=\sum_{k = 1}^{n - 1}(\frac{1}{k} - \frac{1}{k + 1})\\ &=\sum_{k = 1}^{n - 1}\frac{1}{k} - \sum_{k = 1}^{n - 1}\frac{1}{k + 1}\\ &=\sum_{k = 1}^{n - 1}\frac{1}{k} - \sum_{k = 2}^{n}\frac{1}{k} \\ &= 1 - \frac{1}{n} \\ \end{aligned}

\begin{aligned}(2). \sum_{t = 1}^{k}t2^{t - 1}&=\sum_{t = 1}^{k}t(2^t - 2^{t - 1}) \\ &=\sum_{t = 1}^{k}t2^t - \sum_{t = 1}^{k}t2^{t - 1} \\ &=\sum_{t = 1}^{k}t2^t - \sum_{t = 0}^{k - 1}(t + 1)2^t \\ &=\sum_{t = 1}^{k}t2^t - \sum_{t = 0}^{k - 1}t2^t - \sum_{t = 0}^{k - 1}2^t \\ &=k2^t - (2^k - 1) = (k - 1)2^k + 1\\ \end{aligned}

5.2 二分检索的平均时间复杂度 knowledge

image-20200624204630269.png

A(n) = \left \lfloor \log n \right \rfloor + \frac{1}{2}

5.3 估计和式上界的放大法 knowledge

5.4 估计和式渐进的界 Knowledge

估计\sum_{k = 1}^n \frac{1}{k} 的渐进的界

6. 递推方程与算法分析 Knowledge

上一篇 下一篇

猜你喜欢

热点阅读