我爱编程!编程爱我!

#(一)绪论

##(a)计算

计算是我们的研究对象和目标

对象:规律、技巧

目标:高效、低耗

算法

算法:有穷性

Hailstone:

int hailstone(int n){ // 计算序列 Hailstone(n) 的长度
  int length = 1;  //从 1 开始,以下定义逐步递推,直到n = 1
  while(1 < n){(n % 2) ? n = 3*n+1:n /= 2;length++}
  return length;
}
对于任意一个 n 是否总有 Hailstone(n) < ∞ ?

不确定,因此 Hailstone 并不一定是一个算法。

好算法

(b)计算模型

To measure is to know.

If you can not measure it, you can not imporove it.

——Lord Kelvin

算法分析

两个主要方面

考察:

$ T_A (P) $ = 算法 A 求解问题实例 P 的计算成本

意义不大,可能出现的问题实例太多

如何归纳概括?

观察:

问题实例的规模,往往是决定计算成本的主要因素

特定算法 + 不同实例

令 $ T_A (n) $ = 算法 A 求解某一问题规模为 n 的实例,所需的计算成本

讨论特定算法 A(及其对应的问题)时,简记作 T(n)

然而,这一定义仍有问题…

同一个问题等规模的不同实例,计算成本不尽相同,甚至有实质差别。

所以,在规模同为n的所有实例中,只关注最坏(成本最高)者

特定问题 + 不同算法

同一个问题常有多种算法,如何评判优劣?

实验统计是最直接的方法,但不足以准确反映算法的真正效率。(代码实际运行的环境、影响因素是复杂的)

为给出客观的评判,需要抽象出一个理想的平台或模型 。

例子:图灵机模型、RAM模型

在这些模型中:

算法运行时间 ==> 算法需要执行的基本操作次数

T(n) = 算法为求解规模为n的问题,所需执行的基本操作次数

(c)大 O 记号

Mathematics is more in need of good notations than of new therems.

—— Alan Turing

### 渐进分析:大 O 记号

关心足够大的问题,注重考察成本的增长趋势

渐进分析

在问题规模足够大,计算成本如何增长?

大 O记号(big-O notation)

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) $

这类算法效率最高

对数复杂度

$O(logn)$

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

$O(n^c)$

多项式找最高项

线性复杂度:所有$o(n)$类函数

指数复杂度

$ 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) $,是从有效算法到无效算法的分水岭

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

2-Subset

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

例子:美国选举人票制度

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

即:$O(2^n)$ —— 不甚理想

定理:2-subset is NP-complete

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

(d)算法分析