RAM模型的引入
计算的基本概念
- 计算的关键特征：基于有限种类操作的灵活组合完成复杂的计算任务
- 算法的宏观定义：一组计算机操作的序列，遵循算法的指示，计算机对任意合法输入执行一系列操作，并给出正确结果。
计算模型的基本概念
- 算法掌握的一种抽象原则，与编程语言和机器无关，假设在抽象机器上完成算法设计和分析。
- 在不同具体机器上实例化算法时，虽然底层提供的基本操作不同，但是总是常数倍的关系，本质相同。
- 上述的抽象机器就是计算模型，是抽象算法设计与分析的基础。图灵机是描述能力很强的计算模型，对于算法设计分析的基础知识来说，RAM模型更简单易用。
RAM模型(Random Access Machine)
- 组成：输入纸带、输出纸带、存储寄存器、程序指令、位置计数器。
- 指令的分类：简单操作、复杂操作、存储访问
- 单位代价RAM和对数代价RAM：前者不管操作数多大都认为单位时间完成，后者认为操作代价和比特数成正比。未说明的情况都是单位代价RAM，特定问题（如背包问题）会显示指出对数代价RAM。
计算模型的选择：易用性与精确性
- RAM模型：具有易用性，不会给出原则错误，但细节不精确。
- 外部存储模型：对不同存储介质的不同访问代价精细建模，不像RAM模型认为存储空间是无穷的。
- PRAM（Parallel Random Access Machine）模型：刻画并行计算
有了RAM模型，我们清楚了需要完成的计算任务（算法问题），论证需要何种顺序执行哪些操作才能完成指定任务（算法设计），还可以统计完成任务需要的开销（算法分析）。
抽象算法设计
算法问题规约
- 输入：明确算法的所有合法输入
- 输出：明确规定对于每个合法输入，相应的输出是什么
算法正确性证明：数学归纳法
要证明算法正确性，就是证明对于每个合法输入，算法的输出都满足规约的要求。其中的难点往往是合法的输入是无穷的，无法测试穷举来证明正确性（测试只能证明算法是错的）。证明的手段是数学归纳法。
定义 (弱数学归纳法)
假设P是一个定义在正整数集合N上的命题。如果： +
定义 (强数学归纳法)
假设P是一个定义在正整数集合N上的命题。如果： +
定义(良序原理) 任意非空正整数集合必然有最小元素。
数学归纳法和良序原理本质是等价的。在各自的场景下更加便捷。
抽象算法分析
正确设计算法后，下一步就是分析算法的性能。
抽象算法的性能指标
- 时间复杂度：在RAM模型上执行简单操作的个数, 可以精炼为关键操作的个数
- 空间复杂度：在RAM模型中需要的寄存器的个数
最坏情况时间复杂度分析
对于不同的输入，时间代价不同。给定输入规模，最坏的输入对应最高的时间代价。假设规模为n,
则最坏情况时间复杂度定义为
平均情况时间复杂度分析
假设输入服从一个分布，时间复杂度看作一个随机变量，它的期望值就是平均情况时间复杂度。定义为：
期望情况时间复杂度分析
最坏输入情况下的期望时间复杂度，主要针对随机算法的随机数求期望。
平摊时间复杂度分析
详见第18章的笔记，大概理解就是用平摊分析法计算出的平均情况时间复杂度。
