mirror of
https://github.com/Didnelpsun/CS408.git
synced 2026-02-09 21:55:46 +08:00
122 lines
3.8 KiB
Markdown
122 lines
3.8 KiB
Markdown
# 概述
|
||
|
||
## 基本概念
|
||
|
||
+ 数据项：一个数据元素由若干个数据项组成。
|
||
+ 数据元素：组成数据对象的基本单元。
|
||
+ 数据对象：性质相同的数据元素的集合。
|
||
|
||
存储数据时要存储数据元素的值，也要存储数据元素之间的关系。
|
||
|
||
### 数据类型与抽象数据类型
|
||
|
||
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
|
||
|
||
+ 原子类型：其值不可再分的数据类型。
|
||
+ 结构类型：其值可以再分解为若干成分（分量）的数据类型。
|
||
|
||
抽象数据类型$ADT$用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。
|
||
|
||
## 数据结构三要素
|
||
|
||
+ 逻辑结构：元素之间的逻辑关系：线性结构、非线性结构（集合）、树结构、网状结构。
|
||
+ 存储结构：数据在计算机中的表示（映像），也称物理结构：顺序存储结构（顺序表）、链式存储结构（链表）、索引存储（索引表）、散列存储（散列表、哈希表）。
|
||
+ 数据运算：运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
|
||
|
||
逻辑结构独立于存储结构，存储结构依托于逻辑结构。
|
||
|
||
## 算法
|
||
|
||
程序=数据结构+算法。算法为了处理信息。
|
||
|
||
是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
|
||
|
||
### 算法的特性
|
||
|
||
+ 有穷性。
|
||
+ 确定性。
|
||
+ 可行性。
|
||
+ 输入。零个或多个输入。
|
||
+ 输出。一个或多个输出。
|
||
|
||
### 好算法的特点
|
||
|
||
+ 正确性。
|
||
+ 可读性。
|
||
+ 健壮性。
|
||
+ 高效率与低储量需求。
|
||
|
||
### 效率度量
|
||
|
||
#### 时间复杂度
|
||
|
||
时间开销$T(n)$与问题规模$n$的关系。
|
||
|
||
当n规模够大时可以只考虑阶数高的部分。即$T(n)=O(T(n))$。
|
||
|
||
+ $T(n)=f(n)+g(n)=O(f(n))+O(g(n))=O(\max(f(n),g(n)))$。多项相加只保留最高阶的项，系数为$1$。
|
||
+ $T(n)=f(n)×g(n)=O(f(n))×O(g(n))=O(\max(f(n)×g(n)))$。多项相乘就都保留。
|
||
+ $O(1)<O(\log_2n)<O(n)<O(n\log_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$。
|
||
|
||
如$T(n)=n^3+n^2\log_2n=O(n^3)+O(n^2\log_2n)=O(n^3)$。
|
||
|
||
+ 顺序执行的代码只会影响常数项，可以忽略。
|
||
+ 循环就代表一个$n$，并列的循环不会叠加复杂度，只有嵌套的循环才会，嵌套的循环深度就是复杂度的幂数，具体的情况需要看循环内代码的逻辑分析。
|
||
|
||
```c
|
||
void loop(int n){
|
||
int i = 1;
|
||
while(i<=n){
|
||
i=i*1;
|
||
}
|
||
}
|
||
```
|
||
|
||
这个代码的时间复杂度就是$O(\log_2n)$。
|
||
|
||
```c
|
||
// 假定数组中乱序存储1到n的整数
|
||
int array[n]={...};
|
||
void check(int array[], int n){
|
||
for(int i=0; i<n; i++){
|
||
if(array[i]==n){
|
||
printf("%d", i);
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
check(array, n);
|
||
```
|
||
|
||
这个代码的执行时间依托于输入数据：
|
||
|
||
+ 最好情况：元素$n$在第一个位置，$T(n)=O(1)$。
|
||
+ 最坏情况：元素$n$在最后一个位置，$T(n)=O(n)$。
|
||
+ 平均情况：$n$在任意一个位置概率相同，$T(n)=T((1+n)/2)=O(n)$。
|
||
|
||
在实际考虑时只会考虑最坏情况和平均情况。
|
||
|
||
#### 空间复杂度
|
||
|
||
存储空间$S(n)$与问题规模$n$的关系。
|
||
|
||
算法原地工作是指算法所需的内存空间为常数级，即$O(1)$。
|
||
|
||
当$n$规模够大时可以只考虑阶数高的部分。即$S(n)=O(S(n))$。
|
||
|
||
空间复杂度主要看程序所需要的变量所要的空间，一阶数组就是$n$，二阶就是$n$的二次方。
|
||
|
||
同时函数递归调用也会带来内存开销。当每一次递归调用的空间相等时，空间复杂度=递归调用的深度。
|
||
|
||
```c
|
||
void check(int n){
|
||
int array[n];
|
||
if(n > 1) {
|
||
check(n-1)
|
||
}
|
||
}
|
||
check(n);
|
||
```
|
||
|
||
此时每一次的递归会使变量空间减去$1$，所以$S(n)=S((1+n)n/2)=O(n^2)$。
|