数据结构基础

1 数据结构基础

1.1 基本概念

1.数据（Data）
可被计算机识别并加工处理的对象。

2.数据元素（Element）
由数据组成的具有一定意义的基本单位。

3.数据项（Item）
是组成数据元素的、不可分割的最小单位。

注：
1.数据元素在计算机中通常作为一个整体来处理。
2.数据元素由若干数据项组成.

1.2 数据结构三要素

1.逻辑结构
逻辑结构 (Logical Structure)：数据元素间的逻辑关系。

根据数据结构中数据元素之间关系的不同特征，可划分为四种基本逻辑结构：
（1）集合结构：数据元素除了同属于一个集合外，没有其他的关系；
（2）线性结构：数据元素之间存在一对一的关系；
（3）树形结构：数据元素之间存在一对多的关系；
（4）图结构：数据元素之间存在多对多的关系；

2.存储结构

存储结构 (Storage Structure)：数据及数据之间的关系在计算机内的表示形式。

（1）顺序存储结构：将逻辑上相关的数据元素依次存储在地址连续的存储空间中；
（2）链式存储结构：数据元素可以存储在是连续的或不连续的存储空间；数据元素之间的逻辑关系通过指针域来体现；
（3）索引存储结构：建立附加的索引表来标识结点的地址；
（4）散列存储结构：将数据元素的关键字与存储位置之间建立散列表；

3.数据的运算
数据的运算 (Operations)：数据被使用的方式。
最常见的运算有：
（1）搜索运算—在数据结构中搜索满足一定条件的元素；
（2）插入运算—在数据结构中插入新元素；
（3）删除运算—将数据结构中指定元素删除；
（4）更新运算—将数据结构中指定元素更新为新的元素。

2 算法基本概念

2.1 基本概念

算法(algorithm)是对特定问题的求解步骤，它是指令的有限序列。

程序=数据结构+算法

算法的特征：
（1）输入：算法有零个或多个输入；
（2）输出：算法至少产生一个输出；
（3）可行性：算法的每一条指令都足够基本；
（4）确定性：算法的每一条指令都有确切的定义，没有二义性；
（5）有穷性：算法必须总能在执行有限步之后终止。

算法优劣的衡量标准：
（1）正确性：算法执行结果应当满足预先规定的功能和性能要求；
（2）高效性：执行效率高，占用存储空间少；
（3）可读性：一个算法应当思路清晰、层次分明、易读易懂；
（4）健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。

2.2 时间复杂度

1.定义

（1）时间频度
运行时间可以直观且准确地反映算法的效率，但是想准确地统计算法的运行时间既不合理也不现实（需要考虑硬件、语言、环境等多方面因素）。

一般来说，算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它执行花费的时间就多。所以，通常统计和比较的是算法中的语句执行次数，称为语句频度或时间频度，记为$T(n)$。其中，$n$称为问题的规模，当$n$不断变化时，时间频度$T(n)$也会不断变化。

想要知道$T(n)$随着$n$变化时呈现什么样的规律，为此我们引入时间复杂度的概念。

（2）时间复杂度

渐进上界：
若存在正实数$c$和实数$n_0$，使得对于所有$n>n_0$，均有$T(n) \leqslant c*f(n)$，则认为$f(n)$是$T(n)$的一个渐进上界（asymptotic upper bound），表示为$T(n)=O(f(n))$。

有$T(n)=O(f(n))$，表示随着数据规模$n$的增大，算法执行时间的增长率和函数$f(n)$的增长率相同。其中，$f(n)$称为渐进上界，$O(f(n))$即为渐进时间复杂度，简称时间复杂度（time complexity）。

时间复杂度符号上使用大写的$O$（Big O notation）来表示，也叫“大$O$表示法”。

注：时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

2.推算方法

推算算法的时间复杂度$O(f(n))$，其实就是找渐进上界函数$f(n)$，常规的方式是先列出算法执行次数$T(n)$的表达式，然后去掉所有系数，只保留最高阶的项，即为$f(n)$。

例如：某算法的执行次数$T(n)=2n^2+n+3$, 可推算得其时间复杂度为$O(n^2)$。

实际中，只需要找到算法中执行次数最多的语句，判断其执行次数的数量级，即可得到时间复杂度。例如，某算法中，循环部分代码执行次数最多，如下：

for(int i=1;i<=n;i++)
       for(int j=1;j<=i;j++)
            for(int k=1;k<=j;k++)
               x++;

算得x++执行次数为：

$$ \begin{align} \sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}1 &=\sum_{i=1}^{n}\sum_{j=1}^{i}j\\ &=\sum_{i=1}^{n}\frac{i(i+1)}{2} \\ &=\frac{1}{2}(\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}i)\\ &=\frac{1}{2}[\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}]\\ &=\frac{n(n+1)(n+2)}{6} \end{align} $$

所以该算法时间复杂度为$O(n^3)$。

3.常见类型

详细介绍见：Hello算法-时间复杂度-常见类型

常见的时间复杂度类型（顺序从低到高）：

（1）常数阶 - $O(1)$
（2）对数阶 - $O(\log_{}{n})$
（3）线性阶 - $O(n)$
（4）线性对数阶 - $O(n\log_{}{n})$
（5）平方阶 - $O(n^2)$
（6）指数阶 - $O(2^n)$
（7）阶乘阶 - $O(n!)$

4.最优、最坏和平均时间复杂度

算法的时间效率往往不是固定的，而是与输入数据的分布有关。

例如，在一个有$n$个元素的数组中查找一个指定元素，某个搜索算法从第一个元素开始，一次检查一个数组元素。
最优情况：待查元素恰好是第一个元素，只需查找1次，达到最优时间复杂度$\Omega(1)$。
最坏情况：待查元素是最后一个元素，需要查找n次，达到最坏时间复杂度$O(n)$。
平均情况：需要多次在数组中查找元素，并且假定以某种概率查找每个元素，最典型的是以相等概率查找每个元素。这种情况下，共有$n$个元素，而每个元素被找到的概率相等，因此每个元素被找到的概率都是$\frac{1}{n}$，任一元素被找到的需要进行的查找次数为：$\frac{(1+2+…+n)}{n} =\frac{(n+1)}{2} $，平均查找次数约为$n$的一半，平均时间复杂度（又称“加权平均时间复杂度”或“期望时间复杂度）为$\Theta\frac{(n+1)}{2} =\Theta(n)$。

关于复杂度符号表示的含义可以参考这篇博客。

2.3 空间复杂度

1.定义
空间复杂度（space complexity）用于衡量算法占用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”。

空间复杂度通常只分析最坏情况，同时间复杂度一样使用大$O$符号来表示，记为$S(n)=O(f(n))$。

算法在运行过程中使用的内存空间主要包括以下几种：

• 输入空间：用于存储算法的输入数据。
• 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
• 输出空间：用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。
而暂存空间可以进一步划分为三个部分：

• 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
• 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
• 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

分析一段程序的空间复杂度时，通常统计暂存数据、栈帧空间和输出数据三部分。

/* 函数 */
int func() {
    // 执行某些操作...
    return 0;
}

int algorithm(int n) { // 输入数据
    const int a = 0;   // 暂存数据（常量）
    int b = 0;         // 暂存数据（变量）
    int c = func();    // 栈帧空间（调用函数）
    return a + b + c;  // 输出数据
}

2.推算方法

一般来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为$O(1)$。若算法申请了额外空间，按和时间复杂度类似的推算规则进行推算，考虑空间释放，分析最坏情况。

注：

• 在循环中，初始化变量或调用函数而占用的内存在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为$O(1)$。
• 在递归中，若单次递归占用空间为$O(1)$，递归深度为$n$，则会递归时会同时存在多个未返回的函数，使用的栈帧空间为$O(n)$。递归算法的空间复杂度需要统计单次递归的空间*递归深度。

3.常见类型

详细介绍见：Hello算法-空间复杂度-常见类型

常见的空间复杂度类型（顺序从低到高）：

（1）常数阶 - $O(1)$
（2）对数阶 - $O(\log_{}{n})$
（3）线性阶 - $O(n)$
（4）平方阶 - $O(n^2)$
（5）指数阶 - $O(2^n)$

---

本文参考:

• https://www.hello-algo.com
• https://blog.csdn.net/qq_58710208/article/details/125182663
• https://blog.csdn.net/Matutinal/article/details/104485072