绪论
基本概念和术语
数据：所有能输入到计算机中并被计算机程序处理的符号总称
数据元素：数据的基本单位，一个数据元素可由若干个数据项组成
数据项：是数据的不可分割的最小单位
数据对象：是性质相同的数据元素的集合，是数据的一个子集
数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合（简单解释）
根据数据元素之间关系的不同特性，通常有下列4种基本结构：
1）集合
2）线性结构
3）树形结构
4）图状结构或网状结构
数据结构的形式定义为：数据结构是一个二元组
1
Data_Structure = (D,S)
其中：D是数据元素的有限集，S是D上关系的有限集。
数据的储存结构
顺序、链接、索引、散列
抽象数据类型（ADT）
和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示
1
(D、S、P)
其中，D是数据对象，S是D上的关系集，P是对D的基本操作机集。
以如下格式定义抽象数据类型：
1
2
3
4
5ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT抽象数据类型名
其中，数据对象和数据关系的定义用伪代码描述，基本操作的定义格式为
1
2
3基本操作名(参数表)
初始条件：<初始条件描述>
操作结果：<操作结果描述>
基本操作有两种参数：
赋值参数只为操作提供输入值
引用参数以&打头，出可提供输入值外，还将返回操作结果
复杂度分析
时间复杂度
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作
1
T(n) = O(f(n))
时间复杂度分析
1）只关注循环执行次数最多的一段代码
2）加法法则：总复杂度等于量级最大的那一段代码的复杂度。例如：
若 T1(n) = O(f(n)), T2(n) = O(g(n))
则 T(n) = T1(n) + T2(n) = max{O(f(n)), O(g(n))} = O(max{f(n),g(n)})
3）乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。例如：
若 T1(n) = O(f(n)), T2(n) = O(g(n))
则 T(n) = T1(n) x T2(n) = O(f(n)) x O(g(n)) = O(f(n) xg(n))
复杂度量级（按数量级递增）
| 多项式量级 | 非多项式量级 |
|---|---|
| 常量阶O(1) | 指数阶O(2^n) |
| 对数阶O(logn) | 阶乘阶O(n!) |
| 线性阶O(n) | |
| 线性对数阶O(nlogn) | |
| 平方阶O(n^2)…k次方阶O(n^k) |
当O(m+n)、O(mxn)时
加法法则：T1(m) + T2(n) = T(n) = O(f(n) + g(n))
乘法法则不变
进阶：四个复杂度分析
最坏情况时间复杂度：代码在最坏的情况下执行的时间复杂度
最好情况时间复杂度：代码在最理想的情况下执行的时间复杂度
平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示
均摊时间复杂度：在代码执行的所有复杂度情况中绝大多数是低级别的复杂度，个别情况是高级别复杂度，且低级别的复杂度与高级别的复杂度发生具有规律性时，可以将个别高级别的复杂度均摊到低级别的复杂度上。基本上均摊结果等于低级别的时间复杂度。
平均时间复杂度举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14//n表示数组array长度
int find(int[] array,int n,int x)
{
int i = 0;
int pos = -1;
for (;i<n;++i)
{
if(array[i]==x){
pos = i;
break;
}
}
return pos;
}
假设要查找的x在数组中与不在数组中的概率都为1/2，另外，要查找的数据出现在0-n-1这n个位置的概率都一样，即1/n，则该例的平均时间复杂度计算方式为
1
21x1/2n + 2x1/2n + 3x1/2n + ... + nx1/2n +nx1/2
= (3n+1)/4
由此可见该代码的加权平均时间复杂度为O(n)
均摊时间复杂度举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//array表示一个长度为n的数组
//代码中的array.length就等于n
int[] array = new int[n];
int count 0;
void insert(int val){
if(count == array.length){
int sum = 0;
for (int i = 0;i<array.length;i++){
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
在最理想的情况下，数组内有空闲空间，所以最好情况时间复杂度为O(1)，数组长度为n，那么更具数组插入的位置的不同，我们可以分为n种情况；最坏的情况下，数组中没有空闲空间，需要先做一次数组的遍历求和，然后将数组插入，所以最坏情况时间复杂度为O(n)。所以总共有n+1种情况，且发生概率一样，都是1/(n+1)。那么平均时间复杂度的计算方法为
1
21x1/(n+1) + 1X1/(n+1) + ... + 1x1/(n+1) + nx1/(n+1)
= O(1)
我们可以发现find()函数和insert()函数有很大的差别，find()函数在极端情况下复杂度才为O(1),但insert()函数在大部分情况下复杂度都是O(1)，而且O(1)的插入和O(n)的插入，出现频率是非常有规律的，而且有一定的时序关系，一般都是一个O(n)插入之后，紧跟着n-1个O(1)的插入操作，循环往复。针对如此场景，上述分析的方法被称为：摊还分析法；通过摊还分析法得到的时间复杂度就是均摊时间复杂度。我么可以发现每一次O(n)的插入都会伴随n-1次的O(1)的插入，所以把耗时多的操作均摊到接下来n-1次耗时少的操作上，这就是均摊分析的大致思路
空间复杂度
类似于时间复杂度，空间复杂度作为算法所需存储空间的度量，记作
1
S(n) = O(f(n))