数据结构 1.2 算法

算法的基本概念

算法的定义

算法是对特定问题求解步骤的一种描述，它是指定的有限序列，其中的每条指令表示一个或多个操作。

例、

算法的特性 （5个）

1.有穷性

一个算法总在执行有穷步之后结束，且每一步都可以在有穷时间内完成。

注：算法必须有穷，程序可以无穷。

2.确定性

算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

3.可行性

算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 

4.输入

一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

5.输出

一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

“好”算法的特质

1.正确性

算法应该能够正确地解决求解问题。

2.可读性

算法应具有良好的可读性，以帮助人们理解。

3.健壮性

输入非法数据时，算法能够适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。

4.高效率与低存储量需求

高效率：花的时间少，时间复杂度低。

低存储量需求：不菲内存，空间复杂度低。

回顾总结

算法的时间复杂度

时间复杂度——算法时间开销

事后统计法：

算法时间复杂度

 T（n）与n的关系

例

表白 爱你n遍

算法1 逐步递增型爱你

算法2 嵌套循环型爱你

算法3 指数递增型爱你

算法4 搜索数字型爱你

最好与最坏时间复杂度

思考：

问题1

问题2

去掉低阶部分 只保留最高阶部分 忽略常数项

a.加法规则：多项相加，只保留最高项

b.乘法规则：多项相乘，都保留

算法常见时间复杂度顺序：常对幂指阶

知识回顾

算法的空间复杂度

时间复杂度与空间复杂度对比

时间复杂度：时间开销与问题规模n之间的关系

空间复杂度：空间开销（内存开销）与问题规模n之间的关系

程序运行时的内存需求：

时间复杂度T(n) 空间复杂度S（n）

只需关注存储空间大小与问题规模相关的变量

例1

 例2

函数递归调用带来的内存开销

知识回顾