绪论

# 绪论

数据结构在学什么？

如何用程序代码把现实世界的问题信息化
如何用计算机高效地处理这些信息从而创造价值

# 数据结构的基本概念

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

# 早期计算机处理的数据

早期的计算机 —— 只用于处理纯数值型问题

# 现在计算机处理的数据

现代计算机 —— 经常处理非数值型问题

对于非数值型的问题：

我们关心每个个体的具体信息
我们还关心个体之间的关系

# 数据元素

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
数据项：一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

# 数据对象和数据结构

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

线性数据结构

网状数据结构

数据结构这门课着重关注的是数据元素之间的关系，和对这些数据元素的操作，而不关心具体的数据项内容。

# 数据结构的三要素

# 逻辑结构

# 集合结构

各个元素同属一个集合，别无其他关系

# 线性结构

数据元素之间是一对一的关系。
除了第一个元素，所有元素都有唯一前驱。
除了最后一个元素，所有元素都有唯一后继。

实际应用：

排行榜

队列

# 树形结构

数据元素之间是一对多的关系

为什么叫树形结构？

因为逻辑结构在关系图中类似树结构

实际应用

思维导图

文件结构

# 图状结构

数据元素之间是多对多的关系

实际应用

# 数据的运算

数据的运算 —— 针对于某种逻辑结构，结合实际需求，定义基本运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能：运算的实现是针对存储结构的，指出运算的具体操作步骤。

逻辑结构 —— 线性结构

基本运算：

查找第 i 个数据元素
在第 i 个位置插入新的数据元素
删除第 i 个位置的数据元素……

# 物理结构（存储结构）

如何用计算机表示数据元素的逻辑关系？

# 顺序存储

以下以线性结构作例子

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

# 链式存储

链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

# 索引存储

索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）

# 散列存储

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

在第六章散列表中介绍

# 数据类型、抽象数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

原子类型：其值不可再分的数据类型。如 bool 类型可以取 true 或 false 值，可以进行与、或、非等操作；int 类型可以取 -2147483648 ~ 2147483647 范围的值，可以进行加、减、乘、除、模运算...
结构类型：其值可以再分解为若干成分（分量）的数据类型。如结构体类型
抽象数据类型（ Abstract Data Type，ADT ）：是抽象数据组织及与之相关的操作 ADT 用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。

# 总结

数据的物理结构（存储结构） —— 如何用计算机表示数据元素的逻辑关系？

若采用顺序存储，则各个数据元素在物理上必须是连续的；

若采用非顺序存储，则各个数据元素在物理上可以是离散的。
数据的存储结构会影响存储空间分配的方便程度
数据的存储结构会影响对数据运算的速度

如何选择顺序存储还是非顺序存储？

运算的定义是针对逻辑结构的，指出运算的功能；
运算的实现是针对存储结构的，指出运算的具体操作步骤。

# 算法的基本概念

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

# 算法的五个特征

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。算法必须是有穷的，而程序可以是无穷的
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

类似于数学中的函数 $y = f (x)$ y 受 x 变量影响

# “好” 算法的特质

正确性：算法应能够正确地解决求解问题。
可读性：算法应具有良好的可读性，以帮助人们理解。
健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
高效率与低存储量需求。即时间复杂度和空间复杂度低。

# 总结

# 时间复杂度

# 如何计算时间复杂度

算法中所有语句的频度之和记为 $T (n)$

事前预估算法时间开销 $T (n)$ 与问题规模 $n$ 的关系（T 表示 “time”）

void loveYou(int n){ // n为问题规模
    int i=1;
    while(i<=n){
        i++;
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

int main(){
    loveYou(3000);
}

1
2
3
4
5
6
7
8
9
10
11
12

在上面代码块：

第 2 行代码执行了 1 次
第 3 行代码执行了 3001 次
第 4 行和第 5 行代码执行了 3000 次
第 5 行代码执行了一次

那么该代码具体的执行次数： $T (3000) = 1 + 3001 + 2 * 3000 + 1$

时间开销与问题规模 n 的关系： $T (n) = 3 n + 3$

这时统计代码的规模太过于繁琐

如果有好几千行代码，按这种方法需要一行一行数？
是否可以忽略表达式某些部分？

答案是可以，当问题规模 n 足够大时

可以只考虑阶数高的部分
问题规模足够大时，常数项系数也可以忽略

大 $O$ 表示 “同阶”，同等数量级。即：当 $n\rightarrow \infty $ 时，二者之比为常数。

即 $T (N) = O (f (n)) \Leftrightarrow lim_{n \to \infty} \frac{T (n)}{f (N)} = k$

# 常用技巧

时间复杂度有两个规则：

加法规则：多项相加，只保留最高阶的项，且系数变为 1 $T (n) = T_{1} (n) + T_{2} (n) = O (f (n)) + O (g (n)) = O (\max (f (n), g (n)))$
乘法规则：多项相乘，都保留 $T (n) = T_{1} (n) \times T_{2} (n) = O (f (n)) \times O (g (n)) = O (f (n) \times g (n))$

$E g : T_{3} (n) = n^{3} + n^{2} \log_{2} n = O (n^{3}) + O (n^{2} \log_{2} n) = O (n^{2} n) + O (n^{2} \log_{2} n)$

常用时间复杂度大小比较

$O (1) < O (\log_{2} n) < O (n) < O (n \log_{2} n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!) < O (n^{n})$

当两个算法的时间复杂度分别如下，哪个的阶数更高（时间复杂度更高）？

$T_{1} (n) = O (n)$ 与 $T_{2} (n) = O (\log_{2} n)$ 进行比较

证明：当 $n \to \infty$ 时， $n$ 比 $\log_{2} n$ 变大的速度快很多

lim_{n \to \infty} \frac{\log_{2} n}{n} \overset{洛必达}{⟹} lim_{n \to \infty} \frac{1}{n \ln 2} = 0

证明：当 $n \to \infty$ 时， $2^{n}$ 比 $n^{2}$ 变大的速度快很多

lim_{n \to \infty} \frac{n^{2}}{2^{n}} \overset{洛必达}{⟹} lim_{n \to \infty} \frac{2 n}{2^{n} \ln 2} \overset{洛必达}{⟹} lim_{n \to \infty} \frac{2}{2^{n} \ln^{2} 2} = 0

# 时间复杂度趋势图

口诀是：常对幂指阶

上面代码块中我们是每一行代码都算进时间开销中，如果有好几千行代码，按这种方法需要一行一行数，所以我们有三点结论：

顺序执行的代码只会影响常数项，可以忽略
只需挑循环中的一个基本操作分析它的执行次数与 $n$ 的关系即可

那么如果是嵌套循环又如何得出时间复杂度呢？

如果有多层嵌套循环，只需关注最深层循环循环了几次

时间开销与问题规模 n 的关系：

$T (n) = O (n) + O (n^{2}) = O (n^{2})$

# 三种复杂度

假设我们的算法是一个查找算法时间复杂度为 $O (n)$ ，从数组中找到目标值。

void find(int arr[],int n){
    for(int i=0; i<n; i++){
        if(arr[i]==n){
            printf("%d\n",arr[i]);
            break;
        }
    }
}

int main(){
    int arr[5]={2,7,4,1,16};
    find(arr,1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13

计算上述算法的时间复杂度 $T (n)$

最好情况：元素 n 在第一个位置 —— 最好时间复杂度 $T (n) = O (1)$
最坏情况：元素 n 在最后一个位置 —— 最坏时间复杂度 $T (n) = O (n)$
平均情况：假设元素 n 在任意一个位置的概率相同为 $\frac{1}{n}$ —— 平均时间复杂度 $T (n) = O (n)$ 循环次数 $x = (1 + 2 + 3 + \dots + n) \frac{1}{n} = (\frac{n (1 + n)}{2}) \frac{1}{n} = \frac{1 + n}{2} \Rightarrow T (n) = O (x) = O (n)$

通过上面例子我们得出三种复杂度

最坏时间复杂度：最坏情况下算法的时间复杂度
平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
最好时间复杂度：最好情况下算法的时间复杂度。很少用到。

# 总结

# 空间复杂度

# 如何计算空间复杂度

void loveYou(int n){ // n为问题规模
    int i=1;
    while(i<=n){
        i++;
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

int main(){
    loveYou(3000);
}

1
2
3
4
5
6
7
8
9
10
11
12

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为 $S (n) = O (1)$

注：S 表示 “Space”

算法原地工作 —— 算法所需内存空间为常量

空间复杂度与时间复杂度同样有加法规则、乘法规则和比较大小技巧常用技巧

void test(int n){
    int flag[n];
    int i;
}

1
2
3
4

假设一个 int 变量占 4B，则所需内存空间 $= 4 + 4 n + 4 = 4 n + 8$

空间复杂度只需关注存储空间大小与问题规模相关的变量

使用上面代码块的空间复杂度为 $S (n) = O (n)$

void test(int n){
    int flag[n][n];
	int i;
}

1
2
3
4

空间复杂度： $S (n) = O (n^{2})$

void test(int n){
    int flag[n][n];
    int other[n];
	int i;
}

1
2
3
4
5

空间复杂度： $S (n) = O (n^{2}) + O (n) + O (1) = O (n^{2})$

# 函数递归时空间复杂度计算

void loveYou(int n){
    int a,b,c;
    if(n > 1){
        loveYou(n-1);
    }
    printf("I Love You %d\n",n);
}

int main(){
    loveYou(5);
}

1
2
3
4
5
6
7
8
9
10
11

递归过程：

时间复杂度： $S (n) = O (n)$

该例子的空间复杂度 = 递归调用的深度

void loveYou(int n){
    int flag[n];
    if(n > 1){
        loveYou(n-1);
    }
    printf("I Love You %d\n",n);
}

int main(){
    loveYou(5);
}

1
2
3
4
5
6
7
8
9
10
11

存储规模： $1 + 2 + 3 + \dots + n = [n (1 + n)] / 2 = \frac{1}{2} n^{2} + \frac{1}{2} n$

时间复杂度： $S (n) = O (n^{2})$

# 总结

编辑

上次更新: 2023/12/06, 01:31:48

← 线段树线性表→