CS408/Data-Structrue/0-summary.md

概述

基本概念

• 数据项：一个数据元素由若干个数据项组成。
• 数据元素：组成数据对象的基本单元。
• 数据对象：性质相同的数据元素的集合。

存储数据时要存储数据元素的值，也要存储数据元素之间的关系。

数据类型与抽象数据类型

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

• 原子类型：其值不可再分的数据类型。
• 结构类型：其值可以再分解为若干成分（分量）的数据类型。

抽象数据类型$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$，并列的循环不会叠加复杂度，只有嵌套的循环才会，嵌套的循环深度就是复杂度的幂数，具体的情况需要看循环内代码的逻辑分析。

void loop(int n){
    int i = 1;
    while(i<=n){
        i=i*1;
    }
}

这个代码的时间复杂度就是$O(\log_2n)$。

// 假定数组中乱序存储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$的二次方。

同时函数递归调用也会带来内存开销。当每一次递归调用的空间相等时，空间复杂度=递归调用的深度。

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)$。