软考中级软件设计师——数据结构与算法基础学习笔记

什么是数据

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

数据元素、数据项

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

以一个人的成绩单为例，整体成绩单为一个数据元素，而单科成绩是这个数据元素的数据项。

数据结构

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

逻辑结构

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

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

树形结构：数据元素之间是一对多的关系

图结构：数据元素之间是多对多的关系

物理结构（存储结构）

链式存储指逻辑上相邻的元素在物理位置上可以不相邻，也就是说是有相邻和不相邻两种情况的

算法

什么是算法

从字面意思上来说，就是用于计算的方法，通过这种方法可以达到预期的计算结果。从专业上来说，算法是一套模型分析的一组可行的，确定的，有穷的规则。简而言之，算法就是一系列的计算步骤，用来将输入数据转化为输出结果。

五个特性

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

算法效率的度量

时间复杂度和空间复杂度通常用大O表示法。

大O表示法：使用O(f(n))来表示时间复杂度，其中n是输入规模（例如数组的长度、图的节点数等），f(n)是一个关于n的函数。大O表示法关注的是随着n的增长，f(n)的增长趋势，即忽略掉常数项和低阶项。

时间复杂度

常见的时间复杂度类型及计算示例

①常数时间复杂度 O (1)

当算法的执行时间不依赖于输入规模时，时间复杂度为 O (1)。例如，访问数组中的一个特定元素：在大多数编程语言中，假设存在一个数组arr，访问arr[3]（这里 3 是一个固定的索引），无论数组arr的长度是多少，这个操作都只需要一次查找就能完成。

②线性时间复杂度 O (n)

如果算法的执行时间与输入规模 n 成线性关系，那么时间复杂度为 O (n)。例如，遍历一个数组

int arr[5] = {1,2,3,4,5};for(int i = 0;i < 5;i ++){cout << arr[i] << ' ';}

这里，数组arr的长度为 n（在这个例子中 n = 5），循环会执行 n 次，随着数组长度 n 的增加，操作次数也会线性增加。

③平方时间复杂度 O (n²)

当存在嵌套循环，且内外层循环都与输入规模 n 有关时，通常会得到 O (n²) 的时间复杂度。例如，一个简单的冒泡排序算法:

 vector<int> arr = {5, 4, 3, 2, 1};  int n = arr.size();  // 冒泡排序  for (int i = 0; i < n - 1; i++) {  for (int j = 0; j < n - i - 1; j++) {  if (arr[j] > arr[j + 1]) {  // 交换元素  int temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  }  }  }  

④对数时间复杂度 O (log n)

当算法每次迭代都将问题规模减半（或者按照某个比例缩小）时，时间复杂度通常为 O (log n)。例如，二分查找算法。在每次循环中，搜索范围都会减半，所以时间复杂度是 O (log n)，这里 n 是数组的长度。

⑤线性对数时间复杂度 O (n log n)

这是一种常见于分治算法（如快速排序和归并排序的平均情况）的时间复杂度。例如，归并排序算法：
归并排序将数组不断地分成两半，对每一半进行排序（这部分的时间复杂度是 O (log n)，因为每次划分都是将规模减半），然后合并这些子数组（合并操作的时间复杂度是 O (n)，因为需要遍历所有元素来合并）。总体时间复杂度就是 O (n log n)。

空间复杂度

常见的空间复杂度类型

①常数空间复杂度 O (1)

当算法运行过程中所占用的额外空间不随输入规模的变化而变化时，空间复杂度为 O (1)。例如，交换两个变量的值。

②线性空间复杂度 O (n)

如果算法运行时所需的额外空间与输入规模 n 成线性关系，那么空间复杂度为 O (n)。例如，创建一个长度为 n 的数组，创建的数组的大小取决于输入规模 n，随着 n 的增加，所需的额外空间也会线性增加。

③平方空间复杂度 O (n²)

当算法需要创建一个二维数组，且二维数组的行和列都与输入规模 n 有关时，通常会得到 O (n²) 的空间复杂度。例如，创建一个 n×n 的二维矩阵。创建的二维矩阵包含 n * n 个元素，随着 n 的增加，所需的额外空间会以 n² 的量级增加。

④对数空间复杂度 O (log n)

在一些递归算法中，如果递归的深度与输入规模 n 的对数成正比，那么空间复杂度为 O (log n)。例如，计算一个数 n 的二进制表示中的最高位 1 的位置（可以通过不断将 n 除以 2 来实现）

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