C++ 数据结构(一)绪论(3)复杂度
     发布在:C/C++      浏览:48      评论:0 条评论

上一篇:《C++ 数据结构(一)绪论(2)计算模型》

大 O 记号

当 n >> 2 后,对于规模为 n 输入,算法:

1、需要执行的基本操作次数:T(n) = ?

2、需占用的存储单元数:S(n) = ?(通常不考虑)

T(n) = O( f(n) )
$ if \; \exists \ c > 0,当 \ n \gg 2 \ 后,有 \ T ( n ) < c * f ( n ) $

与 T(n) 相比,f(n)更为简介,但依然反映前者的增长趋势

常系数可忽略:O( f(n) ) = O( c * f(n) )

低次项可忽略:O( n^a + n^b ) = O( n^a ), a > b > 0

其他记号

Omega

$ T(n) = \Omega ( f ( n ) ) $

$ if \ \exists \ c > 0,当 \ n \gg 2 \ 后,有 \ T ( n ) > c * f ( n ) $

Theta

$ T(n) = \Theta ( f ( n ) ) $

$ if \ \exists \ c_1 > c_2 > 0,当 \ n \gg 2 后,有 \ c_1 * f( n ) > T( n ) > c_2 * f(n) $

大 O 复杂度

常数复杂度

$ O(2) \ = \ O(2013) \ = \ O(2013 * 2013) \ = \ O(2013^{2013}) \ = \ O(1) $

  • 这类算法的效率最高

对数复杂度

$ \ln (n) $ | $ \lg (n) $ | $ \log_100 (n) $ | $ \log_2013 (n) $

  1. 常底数无所谓

$ \forall \ a, \ b > 0, \ \log_a n = \log_a b * \log_b n = \Theta (\log_b n) $

  1. 常数次幂无所谓

$ \forall \ c > 0, \ \log n^c = c * \log n = \Theta (\log n) $

  1. 对数多项式

$ 123 * \log^{321} n + \log^{105} (n^2 - n + 1) = \Theta (\log^{321} n) $

  1. 小总结

这类算法非常有效,复杂度无限接近于常数

$ \forall c > 0, \ \log n = O(n^c) $

多项式复杂度

$ 100n + 200 = O(n) $

$ (100n - 500)(20n^2 - 300n + 2013) = O(n * n^2) = O(n^3) $

$ \frac{2013n^2 - 20}{1999n - 1} = O( \frac{n^2}{n} ) = O(n) $

一般的:$ a_k n^k + a_{k-1} n^{k-1} + \cdots + a_1 n + a_0 = O(n^k), \ a_k > 0 $

指数复杂度

$ T(n) = a^n $

$ \forall c > 1, \ n^c = O(2^n) $

$ \forall c > 1, \ 1.0000001^n = \Omega (n^1000), \ n^1000 = O(1.0000001^n) = O(2^n) $

这类算法的计算成本增长极快,通常被认为不可忍受。

从 $ O(n^c) $ 到 $ O(2^n) $,是从有效算法到无效算法的分水岭

C++ 数据结构(一)绪论(3)复杂度

很多问题的 $ O(2^n) $ 算法往往显而易见。然而,设计出 $ O(n^c) $ 算法却极其不易,甚至有时注定只能徒劳无功

问题描述

S 包含 n 个正整数,$ \sum S = 2m $
S 是否有子集 T,满足 $ \sum T = m $ ?

直觉算法:逐一枚举 S 的每一子集,并统计其中元素的总和

定理:$ | 2^s | = 2^{| s |} = 2^n $

亦即:直觉算法需要迭代 2^n 轮,并(在最坏情况下)至少需要花费这么多的时间

定理:subset is NP-complete

意即:就目前的计算模型而言,不存在可在多项式复杂度内回答此问题的算法。就此意义而言,上述的直觉算法已属最优

下一篇:《C++ 数据结构(一)绪论(4)算法分析》

Responses