考研考点整理：数据结构 时间复杂度和空间复杂度

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

一般一个算法具有以下特性：

有穷性：一个算法必须在执行有穷步之后结束，且每一步在有穷时间内完成。

确定性：算法中的每条指令都有确切的含义，对于相同的输入只能得到相同的输出。

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

输入：一个算法有零个或多个输入，所谓零个输入是指算法本身定出了初始条件。

输出：一个算法有一个或多个输出，没有输出的算法是毫无意义的。

评价一个好算法，应考虑以下方面：

正确性

可读性

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

效率和存储量的需求：效率是算法执行的时间，存储量是算法执行是所需要的最大存储空间。此两者都与问题的规模有关。

算法的效率：时间复杂度

算法中，基本操作重复执行的次数是问题规模n的某个函数f(n)，其时间量度记作T(n)=O(f(n))，称为算法的渐进时间复杂度，简称时间复杂度。

一般的，常用最深层循环的语句中原操作的执行频度来表示。

O的定义：若f(n)是正整数n的一个函数，则O(f(n))表示∃M≥0，使得当n≥n0时，|O(f(n))|≤M|f(n)|。

表示时间复杂度的阶有以下几种：

O(1)：常量时间阶

O(n)：线性时间阶

O(log2n)：对数时间阶

O(nlog2n)：线性对数时间阶

以下六种计算算法时间复杂度的多项式是最常见的，其关系为(n趋于正无穷大求极限)O(1)

指数时间的关系为O(2n)

在考研中，时间复杂度的计算主要包括循环、递归等形式，具体类型有常量阶、对数阶、线性阶、线性对数阶等计算。

结合真题，本小节在单选题中主要是给定一个程序，分析程序的时间复杂度;在算法题中，分析我们所设计的算法时间复杂度。

算法的效率：空间复杂度

空间复杂度是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作S(n)=O(f(n))，其中n为问题的规模。

空间复杂度的度量

指令常数变量所占用的存储空间

输入数据所占用的存储空间

辅助(存储)空间

一般的，空间复杂度指的是辅助空间的大小。

比如空间复杂度是常量时，空间复杂度是O(1)，表示就地空间。

比如一维数组a[n]：空间复杂度为O(n)。

比如二维数组a[n][m]：空间复杂度为O(n×m)。

结合真题，本小节在单选题中目前没有考察，主要考察方式是在算法设计题中，分析我们所设计的算法的空间复杂度。