数据结构（算法）【7月6日】

一、算法的基本概念：

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

2、算法的特性：

（1）有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成；【算法是有穷的，程序是无穷的】

（2）确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出；

（3）可行性：算法中描述的操作都可以通过已经实现的基本运算执行次数有限次来实现；

（4）输入：一个算法有0个或多个输入，这些输入取决于某个特定的对象的集合；

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

3、“好”算法的特质：

（1）正确性：算法应能正确地解决求解问题；

（2）可读性：算法应有良好的可读性，以帮助人们理解；

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

（4）高效率与低存储量需求：花的时间少，不费内存【时间复杂度低，空间复杂度低】

二、时间复杂度

1、定义：事前预估算法时间开销  T(n)  与问题规模 n 的关系；

2、加法规则：多项相加，只保留最高阶的项，且系数变为1；

3、乘法规则：多项相乘，都保留；

4、常见的渐近时间复杂度：（常对幂指阶）

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

5、三种复杂度：最坏时间复杂度、平均时间复杂度和最好时间复杂度。

6、如何计算：

（1）找到一个基本操作（最深层循环）

（2）分析该基本操作的执行次数 x 与问题规模 n 的关系 x = f（n）；

（3）x 的数量级O（x）就是该算法的时间复杂度 T（n）；

三、空间复杂度

1、定义：预估算法内存开销 S(n)  与问题规模 n 的关系；

2、算法原地工作是指算法所需的辅助空间为常量，即O（1）；

3、普通程序：

（1）找到所占空间大小与问题规模相关的变量；

（2）分析所占空间 x 与问题规模 n 的关系 x = f（n）；

（3）x 的数量级O（x）就是算法空间复杂度 S（n）。

4、递归程序：

（1）找到递归调用的深度 x 与问题规模 n 的关系 x = f（n）；

（2）x 的数量级O（x）就是算法空间复杂度 S（n）

  注：有的算法各层函数所需存储空间不同，分析方法略有区别。