算法分析
- 两个主要方面：
正确性：算法的功能与问题要求一致？
数学证明？可不那么简单...
成本：运行时间 + 所需存储空间
如何度量？如何比较？
考察：
（P）=算法A求解问题实例P的计算成本
意义不大，毕竟...可能出现的问题实列太多
如何归纳概括？
- 观察：问题实例的规模，往往是决定计算成本的主要因素
- 通常：规模接近，计算成本也接近
规模扩大，计算成本亦上升
特定算法 + 不同实列
- 令
- 然而，这一定义仍有问题...
- 观察：同一问题等规模的不同实列，计算成本不尽相同，甚至有实质差别
- 例如：在平面上的n个点中，找到所成三角形面积最小的三个点。
以蛮力算法为例，最坏情况下需枚举所有（n，3）种组合。
但运气好的话...可能只需一次就找到（三个点几乎在一条线上，面积无限接近于0）。
- 既然如此，又该如何定义T（n）呢？
- 稳妥起见，取T（n）= max { T（p） | |p| = n }，亦即，在规模相同为n的所有实例中，只关注最坏（成本最高）者
特定算法 + 不同算法
- 同一问题通常有多种的算法，如何评判其优劣？
- 实验统计是最直接的方法，但足以准确反映算法的真正效率吗？
- 不足够！！！
不同算法，可能更适应于不同规模的输入
不同的算法，可能更适应与不同类型的输入
同一算法，可能由不同的程序员，用不同程序语言，经不同编译器实现
同一算法，可能实现并运行于不同的体系结构，操作系统...
- 为给出客观的评判，需要抽象出一个理想的平台或模型
不再依赖于上述种种具体的因素
从而直接而准确地描述，测量并评价算法
TM：Turing Machine （图灵机）
- Tape 依次均匀地划分为单元格，各注有某一字符，默认为‘#’
- Alphabet 字符的种类有限
- Head 总是对准某一单元格，并可读取和改写其中的字符
每经过一个节拍，可转向左侧或右侧的邻格
- State TM总是处于有限种状态中的某一种
每经过一个节拍，可（按照规则）转向另一种状态
- Transition Function ：（ q，c；d，L/R，p）
若当前状态为q且当前字符为c,则当前字符改写为d；转向左侧/右侧的邻格；转入p状态，一旦转入待定的状态'h'，则停机
TM：Increase
- 功能：
将二进制非负整数加一
- 算法：
全'1'的后缀翻转为全'0'
原最低位的'0'或’#'翻转为'1'
京公网安备 11010502036488号