本文最后更新于 362 天前，其中的信息可能已经有所发展或是发生改变。
1.1 基本名词
- 数据（data)：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。
- 数据元素（data element）：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项（data item）组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
- 数据对象（data object）:数据对象是具有相同性值的数据元素的集合，是数据的一个子集。
- 数据类型（data type) :数据类型是一个值的集合和定义再此集合上的一组操作的总称。
- 原子类型：其值不可再分的数据类型。如
bool和int类型。 - 结构类型：其值可以再分解为若干成分（分量）的数据类型。
- 抽象数据类型：抽象数据组织及与之相关的操作。
- 原子类型：其值不可再分的数据类型。如
- 数据结构（data structure）：
- 数据结构是在计算机中存储、组织数据的方式。小到变量、数组，大到线段树、平衡树，都是数据结构。
- 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
- 数据结构往往同高效的检索算法和索引技术有关。
1.2 数据结构的三要素
1.2.1 数据的逻辑结构
概念：
- 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。
分类：
- 集合结构：结构中的数据元素之间除“同属一个集合”外，别无其它关系。
- 线性结构：结构中的数据元素之间只存在一对一的关系，除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
- 树形结构：结构中数据元素之间存在一对多的关系。
- 图状结构：数据元素之间是多对多的关系。
1.2.2 数据的存储结构
概念：
- 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。
分类：
- 顺序存储：逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
- 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
- 索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
总结：
1.2.3 数据的运算
概念：
- 施加在数据上的运算包括运算的定义和实现。
分类：
- 运算的定义：针对逻辑结构，指出运算的功能。
- 运算的实现：针对存储结构，指出运算的具体操作步骤。
1.3 抽象数据类型
1.3.1 基本概念和术语
- 抽象数据类型(Abstract Data Type, ADT)：指由用户定义的、表示应用问题的一个数学模型，及定义在此数学模型上的一组操作。
- 抽象数据类型是与表示无关的数据类型，使用抽象数据类型描述数据结构，可以不必首先考虑数据对象及操作的实现细节，可以在更高的层次上进行软件的分析和设计，从而提高软件的整体性能和利用率。
- ADT包括三部分：
- 数据对象。
- 数据对象上关系的集合。
- 对数据对象的基本操作的集合。
定义一个ADT：
代码语言：javascript复制ADT 抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT 抽象数据类型名注意：
- 我们所定义的ADT仅仅只有设计部分，具体操作并未实现，故不可以直接使用。
1.3.2 抽象数据类型的表示与实现
实现方式
- 抽象数据类型需要通过固有数据类型（高级编程语言中已经实现的数据类型）来实现。如：C语言中的结构体或C 语言中的类来实现。
1.4 算法和算法分析
1.4.1 算法的概念
程序 = 数据结构 算法
定义：
- 算法是为解决一个或一类问题而规定的一个确定的、有限长的操作序列，其中的每条指令表示一个或多个操作。
算法的特性：
- 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
- 确定性：算法中每条指令必须有确定的含义，不产生二义性，对于相同的输入只能得到相同的输出。
- 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
- 输出：一个算法有一个多个输出，这些输出是与输入有着某种特定关系的量。
算法的设计原则：
- 正确性：算法应能够正确的求解问题。
- 可读性：算法应具有良好的可读性，以帮助人们理解。
- 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名奇妙地输出结果。
- 效率与低存储量：
- 效率是指算法执行的时间。
- 存储量需求是指算法执行过程中所需要的最大存储空间。
1.4.2 算法的时间复杂度
概念：
- 算法执行时间的这一变化趋势可表示为输入规模的一个函数，称作该算法的时间复杂度（time complexity）。
- 具体地，特定算法处理规模为 n 的问题所需的时间可记作 T(n)。
估计方法：
- 大mathcal{O}记号（big-O notation）：我们关注 T(n) 的上界，则时间复杂度的公式可以表示为 T(n) = mathcal{O}(f(n))。
常见量级：
- 常数阶 mathcal{O}(1)
- 线性阶 mathcal{O}(n)
- 对数阶 mathcal{O}(log_2^n)
- 线性对数阶 mathcal{O}(n log_2^n)
- 平方阶 mathcal{O}(n^2)
- 立方阶 mathcal{O}(n^3)
- K 次方阶 mathcal{O}(n^k)
- 指数阶 mathcal{O}(2^n)
- 阶乘阶 mathcal{O}(n!)
常数阶 mathcal{O}(1)：
- 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 mathcal{O}(1)。如：哈希算法，用 hash 函数在常数时间内计算出存储位置。
long long sum = 0;
for(int i = 1; i <= 1000; i ){
sum = i;
}线性阶 mathcal{O}(n)：
- 计算规模随 n 线性增长。如：查找无序数列中的某个数。
int n;
scanf("%d", &n);
long long sum = 0;
for(int i = 1; i <= n; i ){
sum = i;
}对数阶 mathcal{O}(log_2^n) ：
- 计算时间为对数，通常是以 2 为底的对数，每次计算后，问题的规模减少一倍。如：分治算法和二分算法。
int i = 1;
while(i < n){
i *= 2;
}线性对数阶 mathcal{O}(n log_2^n)：
- 这常常是大部分算法能达到的最优复杂度。如分治思想实现的快速排序算法和归并排序算法。
int n;
scanf("%d", &n);
long long sum = 0;
for(int i = 1; i <= n; i ){
for(int j = 1; j <= n; j *= 2){
sum ;
}
}平方阶 mathcal{O}(n^2)：
- 常见于一个两重循环的算法，时间复杂度为 mathcal{O}(n^2)。如：冒泡排序等。类似的复杂度有 mathcal{O}(n^3)，如： Floyd算法求最短路。
int n;
scanf("%d", &n);
long long sum = 0;
for(int i = 1; i <= n; i ){
for(int j = 1; j <= n; j ){
sum ;
}
}阶乘阶 mathcal{O}(n!)：
- 常见于排列问题，若输出所有的全排列，则复杂度为 mathcal{O}(n!)。
总结：
- 对于矩阵，问题的规模与矩阵的阶数有关。
- 对于排序，问题的规模与待排序的元素数量有关。
- 对于多项式计算，问题的规模与多项式的项数有关。
- 对于树结构，问题的规模与树中结点的个数有关。
- 对于图结构，问题的规模与图的边数和顶点有关。
1.4.3 算法的空间复杂度
概念：
- 算法执行所占存储空间的大小可通过计算算法所需的存储空间实现，叫做算法的空间复杂度（space complexity）。
- 具体地，特定算法处理规模为 n 的问题所占的存储空间可记作 S(n)。
估计方法：
- 大mathcal{O}记号（big-O notation）：我们关注 S(n) 的上界，则时间复杂度的公式可以表示为 S(n) = mathcal{O}(g(n))。
常见量级：
- 常量空间 mathcal{O}(1)
- 线性空间 mathcal{O}(n)
- 二维空间 mathcal{O}(n^2)
- 三维空间 mathcal{O}(n^3)
- 递归空间：与递归函数的空间和递归深度有关。
常量空间 mathcal{O}(1)：
- 类似于时间复杂度 mathcal{O}(1)，当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作 mathcal{O}(1)。
int a = 1;线性空间 mathcal{O}(n)：
- 当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模 n 成正比时，空间复杂度记作 mathcal{O}(n)。
int num[] = new int[n];二维空间 mathcal{O}(n^2)：
- 当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模 n 成正比时，空间复杂度记作 mathcal{O}(n^2)。类似的复杂度有 mathcal{O}(n^3)。
int[][] num = new int[n][n];
int[][][] nums = new int[n][n][n];1.5 作业与练习
描述：
- 设计算法，查找一维数组
A[N]中最小的两个数。
要求：
- 简述基本思想。
- 根据思想实现该算法。
- 说明该算法的时间复杂度和空间复杂度。
1.5.1 设计思想
- 对该数组进行快速排序：
- 取数组
A[N]中间的一个任意值x， 将需要排序的数组以此为分界线划分为两个区间。 - 分别从左端点和右端点进行检查，判断是否左区间的数都满足
A[i] <= x，右区间的数都满足A[j] >= x。 - 利用循环在两个区间里分别找到一个不满足对应区间条件的数，然后交换
A[i]和A[j]。 - 递归处理左右两个子区间，直到所有的区间都满足对应的条件。
- 取数组
- 排序后，最小的两个数即为
A[0]和A[1]。
1.5.2 算法实现
算法模板
代码语言：javascript复制int A[N]; //A[N]为需要排序的序列
void quick_sort(int A[], int l, int r){ //调用方法quick_sort(A, 0, n - 1) 其中n - 1为末尾下标，即末边界
if(l >= r) return ; //若满足条件直接返回
int x = A[l r >> 1], i = l - 1, j = r 1; //i,j为移动的两个指针
while(i < j){
do i ; while(A[i] < x); //i先移动，若A[i] < x则停止
do j -- ; while(A[j] > x); //j再移动，若A[j] > x则停止
if(i < j) swap(A[i], A[j]);
}
quick_sort(A, l, j);
quick_sort(A, j 1, r); //递归处理区间
}完整代码
代码语言：javascript复制#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 3;
int A[N];
void quick_sort(int A[], int l, int r){
if(l >= r) return ;
int x = A[l r >> 1], i = l - 1, j = r 1;
while(i < j){
do i ; while(A[i] < x);
do j -- ; while(A[j] > x);
if(i < j) swap(A[i], A[j]);
}
quick_sort(A, l, j);
quick_sort(A, j 1, r);
}
void solve(){
//读入数组长度
int n;
cin >> n;
//读入数组
for(int i = 0; i < n; i ) cin >> A[i];
//排序
quick_sort(A, 0, n - 1);
//输出最小的两个数即为 A[0] 和 A[1]
cout << A[0] << " " << A[1] << endl;
}
int main(){
solve();
return 0;
}1.5.3 算法分析
时间复杂度：
- 最好的情况：当该数组是递增状态时，则只进行了递归遍历，时间复杂度为 mathcal{O}(nlog_2^n)。
- 最坏的情况：当该数组每次都需要遍历找到左右区间不满足条件的值时，时间复杂度为 mathcal{O}(n^2)。
空间复杂度：
- 递归的深度达到最大时，即递归到所有的子区间，空间复杂度为 mathcal{O}(nlog_2^n)。
1.6 补充扩展
- 关于指针和结构体的知识复习：C/C 基础入门
- 关于C/C 语言官方文档：cppreference.com
- 关于算法复杂度详细参考：复杂度-OI WIKI
