什么是算法？
程序 = 数据结构 + 算法
- 数据结构：如何把现实世界的问题信息化，将信息存进计算机，同时还有实现对数据结构的基本操作。
- 如何处理这些信息，以解决实际问题
算法的特性
- 有穷性
一个算法必须总在执行的有穷步之后结束，且每一步都可在有穷时间内完成。
注意：算法必须是有穷的，程序可以是无穷的
- 确定性
算法中的每条指令必须有确切的含义，对于相同的输入只能得出相同的输出
- 可行性
算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
- 输入
一个算法有零个或多个输入，这些输入取自某个特定的对象的集合
- 输出
一个算法有一个或多个输出，这些输出是与输入有着某种特定的关系的量
“好”算法的特性
- 正确性：
算法应能够正确地解决求解问题
- 可读性
算法应该具有良好的可读性，以帮助人们理解。
注：算法可以使用伪代码来表示，甚至可以用文字来表示
- 健壮性
输入非法数据时，算法能适当的做出现反应或进行处理，而不会产生莫名其妙的输出结果。
- 高效率与低存储量需求
执行速度快，时间复杂度低。
不占用内存，空间复杂度低。
算法效率的度量
怎么来评估算法的时间开销？
让算法先运行，事后统计运行时间！
存在的问题？
- 和机器性能有关
- 和编程语言有关
- 和编程程序产生的机器指令质量有关
- 有些算法是不能够使用事后统计的，如：导弹控制算法
时间复杂度
$$T_1(n)=O(n)$$
$$T_2(n)=O(n^2)$$
$$T_3(n)=O(n^3)$$
- 加法规则
$$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$$
多项相加，只保留最高阶的项，且系数变为1
- 乘法规则
$$T(n)=T_1(n)+T_2(n)=O(f(n))×O(g(n))$$
多项相乘，都保留
$$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<o(2^n)<O(n!)<O(n^n)$$
常对幂指阶
- 结论1：
顺序执行的代码只会影响常数项，可以忽略
- 结论2：
只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
- 结论3：
如果多层嵌套循环，只需要关注最深层循环了多少次
在很多算法中执行时间与输入的数据有关
- 最坏时间复杂度 √
最坏情况算法的时间复杂度
- 平均时间复杂度 √
所有输入示例等概率出现的情况下，算法的期望运行时间
- 最好时间复杂度
最好情况下的算法的时间复杂度
空间复杂度
普通程序
- 找到所占空间大小与空间规模相关的变量
- 分析所占内存x与问题规模n的关系x=f(n)
- x的数量级O(x)就是算法空间复杂度S(n)
递归程序
- 找到递归调用的深度x与问题规模n的关系x=f(n)
- x的数量级O(x)就是算法空间复杂度S(n)
- 注意：有点算法各层函数所需存储空间不同，分析策略也有区别
版权声明：文章转载请注明来源，如有侵权请联系删除！
