数据结构的算法

(1)概念

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

重要特性：

①输入：有零个输入或者多个输

②输出：只有一个或者多个输出

③有穷性：算法在执行有限个步骤时，会自动结束而不会陷入无限循环里面

④确定性：算法的每一步都有确定的含义而不会出现二义性

⑤可行性：算法的每一步都可以通过有限次数完成。

3、算法的评价标准(“好”的算法应该考虑达到以下目标)

①正确性。算法能够正确地求解问题。

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

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

④效率与低存储量需求。效率指算法执行的时间，存储量需求是指算法执行过程中所需的最大存储空间。

时间复杂度：时间复杂度实际上是一个函数，代表基本操作重复执行的次数，进而分析函数虽变量的变化来确定数量级，数量级用O表示，所以算法的时间复杂度为： T（n）=O（f（n））

在一个算法存在最好、平均、最坏三种情况，我们一般关注的是最坏情况，原因是，最坏情况是任何输入实例在运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，从大体上来看，平均情况和最坏情况一样差。

(4)一般O（n）的计算方法：

①用 1代替所有运行时间中出现的加法常数；

②在修改后的运行函数中**保留最高阶的项；

③如果最高阶的项系数不是1，则去除这个项系数。

④ 递归算法的时间复杂度为：递归总次数每次递归中基本操作执行的次数。