第2章 算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

2.5 算法的特性

2.6 算法的设计要求

正确性的四个层次：

1. 没有语法错误
2. 正确的输入有对应结果
3. 非法的输入能够得到满足规格说明的结果
4. 对应精心选择的，甚至刁难的测试数据有满足要求的输出结果

2.7.2 事前分析估算法

• 在计算机程序编制前，依据统计方法对算法进行估算

2.9 算法的时间复杂度

• 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而进行分析T(n)随n的变化情况并确定T(n)的数量级。

2.9.2推导大O阶法

1. 用常数1取代运行时间中的所以加法常数
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶存在，且不是1，则去除这个项相乘的常数，得到的结果就是大O阶。

2.10常见的时间复杂度

O(1)<O(logn)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

总结

1.如何记忆算法基本特性及设计要求：

• 首先要有0个或1个输入，满足确定性，保证语句不存在二义性，并且每一步都可行，可以在一定时间内（有穷）完成，最后输出；

2. 设计的要求

• 正确是基础，健壮、可读不能忘，效率存储需优化。

3. 函数的渐近增长

给定两个函数f,g,如果存在一个整数n,使得在大于n时，f总比g大，那么，我们说f的增长渐近快于g。