第1章 绪论

有关介绍算法正确性算法复杂性时间复杂性时间复杂性记号1、上有界$O$2、下有界$\Omega$多项式复杂度指数复杂度 3、同阶$\theta$ 运算规则 空间复杂性

有关介绍

(算法 + 数据结构) = 程序

图灵——计算机科学之父、人工智能之父 图灵奖——计算机界的诺贝尔奖 图灵测试

算法相关性质：输入、输出、确定性、有限性

算法：解决问题的方法或过程

算法正确性

一个算法是正确的，如果它对于每一个输入都最终停止，而且产生正确的输出。

程序调试只能证明程序有错，不能证明程序无错误！

算法复杂性

时间复杂性

一个算法在一台抽象的计算机上运行所需要的时间 （对特定输入产生结果需要的原子操作或“步”数） $$T=T(N,I)$$

N：问题的规模 I：输入

1、最坏情况下的时间复杂性 2、最好情况下的时间复杂性 3、平均情况下的时间复杂性

时间复杂性记号

f(N)和g(N)是定义在正数集上的正函数 若存在正常数$C$和自然数$N_0$

1、上有界$O$

$f(N)$当N充分大时上有界：当$N\ge N_0$时，有$f(N)\le Cg(N)$，$g(N)$是$f(N)$的一个上界

f(N)=O(g(N))

$$O(1)<O({log}_{2}n)<O(n)<O(nlo{g}_{2}n<O(n^2)<\cdot \cdot \cdot <O(2^n)<O(n!)<O(n^n)$$

2、下有界$\Omega$

$f(N)$当N充分大时下有界：当$N\ge N_0$时，有$f(N)\ge Cg(N)$，$g(N)$是$f(N)$的一个下界

f(N)=Ω(g(N))

多项式复杂度

高效算法，堆叠硬件

指数复杂度

低效算法，堆叠硬件无用

3、同阶$\theta$

$f(N)$当与$g(N)$同阶：当且仅当$f(N)=O(g(N))$且$f(N)=\Omega (g(N))$

f(N)=θ(g(N))

运算规则

O(f) + O(g) = O(max(f,g)) O(f) + O(g) = O(f + g) O(f)O(g) = O(fg) 若g(N) = O(f(N))，则O(f) + O(g) = O(f) O(Cf(N)) = O(f(N))，其中C是一个正的常数 f = O(f)

空间复杂性

一个算法对特定输入产生结果所需要的存储空间大小 $$S=S(N,I)$$