当前位置：首页 > news >正文

稳定性复杂度

news 2025/4/30 10:02:07

一稳定性

在一个待排序的序列中，如果存在多个具有相同关键字（值）的元素，那么在使用某种排序算法对该序列进行排序后，这些相同关键字元素的相对顺序与排序前保持一致，就称该排序算法是稳定的。反之，如果相同关键字元素的相对顺序发生了改变，则该排序算法是不稳定的。

二时间复杂度

时间复杂度通常用大 O 符号（O）来表示。它描述了算法的运行时间与输入规模之间的渐近关系，即当输入规模趋向于无穷大时，算法时间增长的速度。

时间复杂度越低，算法的效率越高。

2.1 常见时间复杂度

常数时间复杂度：O(1)，表示算法的执行时间与输入规模无关，无论输入规模如何变化，算法都在固定的时间内完成。

对数时间复杂度：O(\log n)，常见于一些分治算法，如二分查找。随着输入规模n的增大，算法的执行时间增长非常缓慢。例如，在一个长度为n的有序数组中进行二分查找，每次查找都能将搜索范围缩小一半，最多需要\(\log_2 n\)次比较就能找到目标元素。

线性时间复杂度：O(n），表示算法的执行时间与输入规模成正比。例如，遍历一个长度为n的数组，对每个元素进行一次操作，操作次数为n，时间复杂度就是\(O(n)\)。

线性对数时间复杂度：O(n\log n)，通常出现在一些高效的排序算法中，如归并排序、快速排序（平均情况）。这种时间复杂度结合了线性和对数的特点，当输入规模增大时，算法的执行时间增长速度比线性略快，但比平方级要慢得多。

多项式时间复杂度：(O(n^2)、O(n^3)。当时间复杂度为\(O(n^2)\)时，常见于一些简单的排序算法，如冒泡排序、插入排序。在这些算法中，对于长度为n的数组，通常需要进行两层嵌套的循环操作，导致基本操作的执行次数与\(n^2\)成正比。随着n的增大，算法的执行时间会急剧增加。

三空间复杂度

空间复杂度是衡量一个算法在运行过程中临时占用存储空间大小的指标，它用于描述算法所需的空间随输入规模增长的变化趋势。

空间复杂度是评估算法性能的一个重要方面，特别是在处理大规模数据或对内存空间有限制的情况下，选择空间复杂度较低的算法可以有效地减少内存的使用，提高程序的运行效率和稳定性。

3.1 常见空间复杂度

\(O(1)\) 空间复杂度表示算法在执行过程中占用的额外空间是一个常数。例如，一个简单的交换两个变量值的函数，只需要几个临时变量来存储中间结果，无论输入数据有多少，所占用的额外空间都是固定的，空间复杂度为\(O(1)\)。

\(O(n)\) 空间复杂度当算法需要创建一个与输入规模n成正比的额外空间时，空间复杂度为\(O(n)\)。例如，在归并排序算法中，通常需要创建一个大小与原始数组相同的辅助数组来进行数据的合并操作，因此归并排序的空间复杂度为\(O(n)\)。

\(O(n^2)\) 空间复杂度若算法中创建的额外空间与输入规模的平方成正比，则空间复杂度为O(n^2)。例如，对于一个二维数组的初始化操作，如果二维数组的大小为n*n，那么需要O(n^2)的空间来存储这个二维数组。

四八大排序

1. 冒泡排序（Bubble Sort）

稳定性：稳定。在冒泡排序中，只有当相邻元素顺序错误（即前一个元素大于后一个元素）时才会进行交换。相同元素不会因为排序过程中的交换操作而改变相对顺序。
时间复杂度：
- 最好情况：当数组已经有序时，只需遍历一次数组，比较 \(n - 1\) 次，时间复杂度为 \(O(n)\)。
- 最坏情况：数组完全逆序，需要进行 \(n - 1\) 趟排序，每趟排序需要比较 \(n - i\) 次（i 为当前趟数），总的比较次数为 \(\sum_{i = 1}^{n - 1} (n - i)=\frac{n(n - 1)}{2}\)，时间复杂度为 \(O(n^2)\)。
- 平均情况：平均时间复杂度也是 \(O(n^2)\)。
空间复杂度：只需要常数级的额外空间，用于交换元素，空间复杂度为 \(O(1)\)。

2. 选择排序（Selection Sort）

稳定性：不稳定。在选择排序中，每次会从未排序部分选择最小（或最大）的元素，与未排序部分的第一个元素交换位置。这个交换操作可能会改变相同元素的相对顺序。例如，数组 [5, 8, 5, 2]，第一次选择最小元素 2 与第一个 5 交换后，两个 5 的相对顺序就改变了。
时间复杂度：无论数组初始状态如何，都需要进行 \(n - 1\) 趟排序，每趟排序需要遍历未排序部分找到最小（或最大）元素，总的比较次数为 \(\sum_{i = 1}^{n - 1} (n - i)=\frac{n(n - 1)}{2}\)，时间复杂度为 \(O(n^2)\)。
空间复杂度：只需要常数级的额外空间，用于交换元素，空间复杂度为 \(O(1)\)。

3. 插入排序（Insertion Sort）

稳定性：稳定。插入排序是将未排序元素插入到已排序部分的合适位置。在插入过程中，如果遇到相同元素，会将新元素插入到相同元素的后面，不会改变相同元素的相对顺序。
时间复杂度：
- 最好情况：数组已经有序，每次插入操作只需要比较一次，时间复杂度为 \(O(n)\)。
- 最坏情况：数组完全逆序，每个元素都需要插入到已排序部分的最前面，总的比较次数为 \(\sum_{i = 1}^{n - 1} i=\frac{n(n - 1)}{2}\)，时间复杂度为 \(O(n^2)\)。
- 平均情况：平均时间复杂度为 \(O(n^2)\)。
空间复杂度：只需要常数级的额外空间，用于保存待插入元素，空间复杂度为 \(O(1)\)。

4. 希尔排序（Shell Sort）

稳定性：不稳定。希尔排序是对插入排序的改进，通过设置不同的间隔（增量）对数组进行分组排序。在分组插入排序过程中，相同元素可能会被分到不同的组中，从而导致相同元素的相对顺序发生改变。
时间复杂度：希尔排序的时间复杂度与增量序列的选择有关。常见的增量序列如 {n/2, n/4, ..., 1}，其时间复杂度约为 \(O(n^{1.3})\) 到 \(O(n^2)\) 之间。
空间复杂度：只需要常数级的额外空间，用于交换元素，空间复杂度为 \(O(1)\)。

5. 归并排序（Merge Sort）

稳定性：稳定。归并排序采用分治策略，将数组分成两个子数组分别排序，然后合并两个有序子数组。在合并过程中，如果遇到相同元素，会先将左边子数组的元素放入结果数组，从而保证相同元素的相对顺序不变。
时间复杂度：无论数组初始状态如何，归并排序都需要将数组不断二分，直到每个子数组只有一个元素，然后再合并这些子数组。每次二分的时间复杂度为 \(O(log n)\)，每次合并的时间复杂度为 \(O(n)\)，因此总的时间复杂度为 \(O(n log n)\)。
空间复杂度：需要额外的 \(O(n)\) 空间来存储合并过程中的临时数组。

6. 快速排序（Quick Sort）

稳定性：不稳定。快速排序通过选择一个基准元素，将数组分为两部分，小于基准的元素放在左边，大于基准的元素放在右边。在分区过程中，元素的交换操作可能会改变相同元素的相对顺序。
时间复杂度：
- 最好情况：每次选择的基准元素都能将数组均匀地分成两部分，此时时间复杂度为 \(O(n log n)\)。
- 最坏情况：数组已经有序，每次选择的基准元素都是最小或最大元素，导致分区不均衡，时间复杂度为 \(O(n^2)\)。
- 平均情况：平均时间复杂度为 \(O(n log n)\)。
空间复杂度：主要是递归调用栈的空间开销。
- 最好情况：递归深度为 \(O(log n)\)，空间复杂度为 \(O(log n)\)。
- 最坏情况：递归深度为 \(O(n)\)，空间复杂度为 \(O(n)\)。

7. 堆排序（Heap Sort）

稳定性：不稳定。堆排序是利用堆这种数据结构进行排序的算法。在堆调整过程中，元素的交换操作可能会改变相同元素的相对顺序。
时间复杂度：堆排序的主要步骤包括建堆和调整堆，建堆的时间复杂度为 \(O(n)\)，每次调整堆的时间复杂度为 \(O(log n)\)，需要进行 n 次调整，因此总的时间复杂度为 \(O(n log n)\)。
空间复杂度：只需要常数级的额外空间，用于交换元素，空间复杂度为 \(O(1)\)。