DataStructure


绪论

基本概念和术语

数据:所有能输入到计算机中并被计算机程序处理的符号总称
数据元素:数据的基本单位,一个数据元素可由若干个数据项组成
数据项:是数据的不可分割的最小单位
数据对象:是性质相同的数据元素的集合,是数据的一个子集
数据结构:是相互之间存在的一种或多种特定关系的数据元素的集合(简单解释)

根据数据元素之间关系的不同特性,通常有下列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
5
ADT抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}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
2
1x1/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
2
1x1/(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))

留坑待填

-------------Thanks for Reading-------------

本文标题:DataStructure

文章作者:asKylin

发布时间:2018年09月26日 - 22:09

最后更新:2019年02月13日 - 15:02

原始链接:http://askylin.top/2018/09/26/DataStructure/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。