算法分析与设计概论
目录：
引论及算法分析
算法设计模式
算法分析的数学基础
一、引论及算法分析
70年代Kunth出版了《The Art of Computer Programing》以算法为主线，确立了算法为计算机科学基础的重要主题。1974年获得图领奖
70年代后，算法作为计算机科学的核心，推动了计算机科学的飞速发展。
可计算理论
——计算模型
——可计算问题/不可计算问题
——计算模型的等价性---图灵/Church命题
计算复杂想理论：在给定的计算模型下研究问题的复杂想
- 固有复杂性
- 上界
- 下界
- 平均
- 复杂性问题的分类
- 抽象复杂性研究
算法正确性证明：
——证明算法对所有输入都停止
——证明对每个输入都产生正确的结果
——程序调通不等于证明算法正确
算法复杂性分析：
目的：预测计算所需资源量
复杂性测度：时间、空间、I/O是输入大小的函数
用途：为求解一个问题选择最佳策略、最佳设备
数学基础：离散数学、概率论、代数等。建立算法复杂性的数学模型，然后对模型化简。
算法复杂性分析的度量
1.时间复杂性：算法输入产生结果需要的原子操作或“步”数
时间复杂性是输入大小的函数
假设每一步执行需要常数时间
2.空间复杂性：输入产生结果所需要存储空间的大小
3.最坏复杂性：max
4.最小复杂性：min
5.平均复杂性：数学期望
算法分析的模型：单处理机、串执行、无并发
基本数据操作、基本数据类型
二、算法的设计模式
算法设计模式：暴力搜索、分治、图说与枚举、（分支界限、回溯）、随机化方法
算法实现方法：
递归与迭代
顺序、并行、分布式
确定性与非确定性
近似求解与精确求解
最优化设计方法：线性规划、动态规划、贪心算法、启发式算法
三、算法分析的数学基础
3.1计算复杂性函数的阶
用增长率描述算法的效率，忽略低阶项，保留最高项，忽略常系数
渐进效率：
——输入规模非常大
——忽略低阶项和常系数
——只考虑最高阶
典型的增长阶、记号等
同阶函数集合：
低阶函数集合：
高阶函数集合：
3.2和式的估计与界限
线性和：
级数
和的界限：
证明：
3.3递归方程
递归方程：是用小的输入值来描述一个函数的方程或不等式
求解递归方程的三个主要方法：
替换方法：
猜想加数学归纳法证明。
——联想已知的T(n)
迭代方法：循环的展开递归方程，要知道通项公式。把递归方程转化为和式，再用求和解决。
Master定理：
对于红色部分，Master定理无能为力。
使用方法：