算法分析：
两个主要方面
正确性：算法功能与问题要求一致？
数学证明？可不那么简单…
成本： 运行时间 + 所需存储空间
如何度量？如何比较？
洒扫与事长
划分等价类
观察：问题实例的规模，往往是决定计算成本的主要因素
线段3等分，
n越大，耗时越长
通常：规模接近，计算成本也接近
Hailstone
既然如此，又该如何定义T(n)呢？
同一问题通常有多种算法，如何评判其优劣？
实验统计是最直接的方法，但足以准确反映算法的真正效率？
但足以准确反映算法的真正效率？
不同的算法，可能更适应于不同规模的输入
不同的算法，可能更适应于不同类型的输入
同一算法，可能由不同程序员，用不同程序语言、经不同编译器实现
同一算法，可能实现并运行于不同的体系结构、操作系统…
为给出客观的评判，需要抽象出一个理想的平台或模型
不再依赖于上述种种具体的因素
从而直接而准确地描述、测量并评价算法
图灵机模型
图灵机
将二进制非负整数加一
转换规则
(<,1,0,L,<)
(<,0,1,R,>)
(<,#,1,R,>)
(>,0,0,R,>)
(>,#,#,L, h) // 复位
RAM: Random Access Machine
寄存器顺序编号，总数没有限制 // 但愿如此
R[0], R[1], R[2], R[3], …
每一基本操作仅需常数时间 // 循环及子程序本身非基本操作
R[i] <- c R[i] <- R[R[j]] R[i] <- R[j] + R[k]
R[i] <- R[j] R[R[i]] <- R[j] R[i] <- R[j[ - R[k]
IF R[i] = 0 GOTO 1 IF R[I] > 0 GOTO 1
GOTO 1 STOP
与TM模型一样，RAM模型也是一般计算工具的简化与抽象
使我们可以独立于具体的平台，对算法的效率做出可信的比较与评判
在这些模型中，算法的运行时间 转化为 算法需要执行的基本操作次数
T(n) = 算法为求解规模为n的问题，所需执行的基本操作次数
RAM模型实例：Floor
功能：向下取整的除法, 0 <= c, 0 < d
[c/d] = max{x | d·x <= c }
所有与d相乘之后不大于c的最大的整数
= max{x | d·x | 1 + c }
等价于与d相乘之后小于1+c的最大的整数
算法：反复地从R[0] = 1 + c 中减去R[1] = d
统计在下溢之前，所做减法的次数x
图灵机、RAM等模型，为度量算法性能提供了准确的尺度
如何使用这些尺度，有何规则，有何技巧？
渐近分析： 大O记号
回到原先的问题：随着问题规模的增长，计算成本如何增长？注意：这里更关心足够大的问题，注重考查成本的增长趋势
渐近分析：在问题规模足够大后，计算成本如何增长？
Asymptotic analysis : 当 n 足够大后，对于规模为n输入，算法需执行的基本操作次数：T(n) = ?
需占用的存储单元数：S(n) = ?
需占用的存储单元数，通常可不考虑，为什么？
渐近分析：大O记号
渐近分析：其它记号T(n) = Ω(f(n))下界
这类算法的效率通常认为已可令人满意，然而…
这个标准是否太低了？
2-Subset
[问题描述]
S包含n个正整数，ΣS = 2m
S是否有子集T，满足ΣT = m ?
2-Subset
【问题描述】
S包含n个正整数，ΣS = 2m
S是否有子集T，满足ΣT = m？
2-Subset
直觉算法：逐一枚举S的每一子集，并统计其中元素的总和
定理： ∣ 2 s ∣ = 2 ∣ S ∣ = 2 n | 2^s | = 2^{|S|}=2^n ∣2s∣=2∣S∣=2n
亦即：直觉算法需要迭代2^n轮，并（在最坏情况下）至少需要花费这么多的时间
不甚理想！
还是直觉：应该有更好的办法吧？
定理：2-subset is NP-Comlete
----什么意思？
意即：就目前的计算模型而言，不存在可在多项式时间内回答此问题的算法
就此意义而言，上述的直觉算法已属最优
