学习数据结构（2）空间复杂度+顺序表

1.空间复杂度

（1）概念

空间复杂度也是一个数学表达式，表示一个算法在运行过程中根据算法的需要额外临时开辟的空间。 空间复杂度不是指程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。 空间复杂度的计算规则基本和时间复杂度类似，也使用大O渐进表示法

函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

（2）示例

例1：计算BubbleSort的空间复杂度

函数栈帧在编译时已经确定了，只需要关注函数在运行时额外申请的空间，有size_t end、size_t i、int exchange 三个额外创建的变量，F(N)=3，故空间复杂度为O(1）

例2：计算Fac的空间复杂度

递归算法的空间复杂度=单次递归的空间复杂度*递归次数，每调用一次递归函数开辟一个函数栈帧，这里调用了N次，空间复杂度为O(N)

2.常见复杂度对比

（这是作者在百度上找的图）

3.关于复杂度的算法题

提交代码1（循环k次，每一次先保存数组最后一位元素，循环将数组前numsSize-1个元素向后移动一位，将最后一位元素值赋给数组第一个元素）：

分析可知，这段代码的时间复杂度为O(N^2)，空间复杂度为O(N)，代码效率不高

提交代码2（创建一个新数组，将原数组中后k个元素移到新数组的前k位，将元素组中的前numSize-k个元素移到新数组的后numSize-k位，再将新数组的每一位对应赋给原数组的每一位）：

分析可知，这段代码的时间复杂度为O(N)，空间复杂度为O(N)，相对代码1效率提高了

提交代码3（编写一个逆置函数，将数组前numSize-k个元素逆置，再将数组后k个元素逆置，最后将数组整体逆置）：

分析可知，这段代码的时间复杂度为O(N)，空间复杂度为O(1)

4.线性表

线性表是n个具有相同特性的数据元素的有限序列，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，在物理上通常以数组和链式结构的形式存储

5.顺序表

（1）概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

（2）静态顺序表和动态顺序表

静态顺序表：使用定长数组储存元素

typedef int SLDataType;
#define N 7;
typedef struct Seqlist
{SLDataType a[N];//定长数组int size;//有效数据个数
}SL；

或另写一行代码重命名：

typedef int SLDataType;
#define N 7;
struct Seqlist
{SLDataType a[N];//定长数组int size;//有效数据个数
}；
typedef struct SeqList SL;

动态顺序表：创建指针变量，按需申请内存

typedef int SLDataType;
typedef struct Seqlist
{SLDataType* a;int size;//有效数据个数int capacity;//空间容量
}SL；