01B 计算模型
性能测试
to measure is to know. 能度量才能提高。如何度量算法的性能?
问题规模
成本：运行时间 + 所需存储空间
TA(p): 算法A求解问题实例P的计算成本，跟规模有很大关系，如线段 3 等分和 n 等分，规模增加计算成本也增加。
最坏情况
TA(n): 用算法A求解某一规模为n的实例，规模相同实例不同，计算成本可能相差很大，如找平面上 n 个点中找到面积最小的三角形。
理想情况
抽象出理想的平台或模型，不依赖输入的类型，规模，实现的语言，编译器等。下面的两种模型即为抽象后的理想模型:
- 图灵机
- RAM模型
他们是一般计算工具的简化和抽象，可以使我们可以对立于具体平台，对算法效率做出可信的比较和评判。
图灵机
图灵机(turing machine)：
- tape 无限长纸带，均匀分为单元格，每个单元格可存储字符
- alphabet 字符的种类有限
- head 读写头
- state TM总是处于某种状态
- transition function: (1, c: d, L/R, p)
例子： 图灵机将二进制非负整数加一 演示： 见课件中下载的 excel
RAM模型(random access machine)
寄存器顺序编号，总算没有限制: R[0], R[1], R[2], R[3], ...
提供常数赋值，直接赋值，间接赋值等约10个级别操作，仅需常数时间。循环及子程序非基本操作。
上述两种模型，可以将模型中的算法运行时间转换为算法需要执行的基本操作次数。
例子：向下取证的除法