目录
思考问题
1、算法的特性是什么
2、如何评估一个算法的性能
3、什么是大O记号，使用其应注意什么？是否还有其他评估方式？
概述
**计算 **
主要研究对象，寻规律 技巧，达到有效高效计算 computer sicenice
绳索计算机
输入：人给直线及其一点
输出：垂线
算法：采用12段线方式 埃及人
尺规计算机
任给一条线段 如果找出两个切分点均匀切分
算法：弄三个相等的射线段 完事之后做平行线
算法：
正确性
确定性
可行性
有穷性 参考递归例子
程序 不等于 算法 （例如死循环 栈溢出）
如何设计好的算法？
正确，健壮，可读，最重要的是效率（速度快、空间少） 算法+数据结构 = 程序
计算模型
性能测试： 度量 To measure is to know
算法分析:
1、正确性
2、成本 运行时间+所需存储空间 如何度量？如何比较？
划分等价类：问题实例的规模，往往决定计算成本
特定算法，同一问题 ：规模不同可能不同，规模相同也有可能成本不同，所以也要关注最坏情况；特定问题，不同算法：算法不同可能不同。
那么如何计算呢？实验室统计？但是不足够 不同规模 类型 语言 体系结构 操作系统等
客观的评判
1、需要抽象出一个理想平台或模型
2、不再依赖上述种种具体的因素 直接准确描述 测量并评论算法
如何客观评判呢？
- 图灵机模型TM:
Tape 依次均匀的划分为单元格，各注一个有某一字符，默认为#
Alphabet 字符的种类有限
Head 总是对准某一单元格，并可读取和改写其中的字符没经过一个节拍，可转向左侧或右侧的邻格
State TM总是处于悠闲中状态的某一种 没经过一个节拍，可（按照规则）转向另一种状态
Transition Function (q,c;d,L/R,p)若当前状态为q且当前字符为c，则当前字符改写为d；
转向左侧/右侧邻格；转入p状态一旦转入特定的状态’h’，则停机
图灵机实例:二进制非负整数加1
- RAM模型
无限的空间 寄存器顺序编号，总数没有限制，每一个基本操作仅需要常数时间
RAM实例：Floor
图灵机模型与RAM模型对比：
均是一般计算工具的简化与抽象，使我们可以独立于具体平台，对算法效率做出可信的比较与评判
总结：
在这些模型中，算法的运行时间 ~~~ 算法需要执行的而基本操作次数 抛开了硬件环境
复杂度标注
大O记号（big-O notation）上界（针对性能的悲观预测）
关心足够大的问题，注重考查成本的趋势，常系数可以忽略，低次项可以忽略
其他标示
* Ω 下界 针对性能的乐观预测
* seita 针对性能的平均预测
高效解
* 常数O（1） 算法效率最高 不含转向（循环调用递归等）必顺序执行既是O1
* 对数O（logn）算法非常有效 复杂度无限接近与常数
* 常底数无所谓
* 常数次幂无所谓
* 对数多项式
* O（n的c次方）线性：所有O（n）类函数
*
较低效解
* O（2的n次方）指数 成本增长极高
例子：2-subset
算法分析
- 正确性（不变性 单调性）+复杂度
- 去粗存精
- C++等高级语言的基本指令，均等效于常数条RAM的基本指令
- 分支转向：goto
- 迭代循环：for while 本质上是if goto
- 调用+递归：本质上也是goto
复杂度分析的主要方法
* 迭代：级数求和
* 递归：递归跟踪+递推方程
* 猜测+验证
级数（最好再看一遍，就知道复杂度）
* 算数级数：与末项平方同阶
* 幂方级数：比幂次高出一截
* 几何级数：与末项同阶
* 收敛级数：O（1）
循环，使用面积的方式来看复杂度
for(i...n)
for(j...n){
operate()
}
n+n+...+n = n * n = O(n2)
对应坐标看的话正好是矩形的面积 约On平方
for(i...n)
for(j...i){
operate()
}
0+1+....(n-1) = n(n-1)/2 = O(n2)
对应坐标看的话正好是三角形的面积 约On平方
非极端元素+冒泡排序
正确性的证明
* 问题：算法是否必然结束？至多迭代多少趟
* 不变性：经k纶扫描交换后，最大的k歌元素必然就位
* 单调性：经k纶扫描交换后，问题规模缩减至n-k
* 正确性：经过至多n趟，算法必然终止，能给出正确解答
封底估算 Back Of the envelopse calculation