数据结构：第六节-复杂度分析（下）

Cpp入门到精通 2024-05-04

128

点击蓝字

山月

关注我们

第六节复杂度分析（下）

上节我们主要介绍了常见的时间复杂度与最好最坏时间复杂度，这节我们介绍有关时间复杂度分析的其他内容。

我们要介绍的最后一个时间复杂度分析是平均时间复杂度分析：

平均时间复杂度是算法在所有可能输入实例上的期望运行时间的度量。它考虑了算法在不同输入情况下的执行效率，并对每种情况的概率进行加权平均，以得出算法的平均性能。

我们以简单的冒泡排序算法为例：

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped; // 用于标记本次遍历是否发生了交换
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        // 在每次遍历中，比较相邻元素并进行交换
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻元素
                swap(arr[j], arr[j + 1]);
                swapped = true; // 标记本次遍历发生了交换
            }
        }
        // 如果本次遍历没有发生交换，则数组已排序完成
        if (!swapped) {
            break;
        }
    }
}

在冒泡排序中，每次遍历都会比较相邻的元素，并根据需要进行交换，直到数组完全排序。对于随机排列的数组，相邻元素需要进行交换的期望次数是一个重要指标。在冒泡排序中，相邻元素需要交换的概率取决于它们的相对顺序。

在冒泡排序中，最坏情况时间复杂度为 O(n^2)，即当数组完全逆序时。一般而言，冒泡排序的平均时间复杂度约为 O(n^2)。这是因为即使在平均情况下，仍然需要执行大量的比较和交换操作，使得算法的时间复杂度保持在二次方级别。

第二个例子来看快速排序算法：

快排算法是通过选择一个基准元素，将数组分割成两个子数组，左边的子数组元素都小于基准元素，右边的子数组元素都大于等于基准元素，然后递归地对子数组进行排序。

void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        // 选取基准元素（这里选择最右边的元素作为基准）
        int pivot = arr[right];
        int i = left - 1;
        // 将小于基准的元素放到左侧，大于等于基准的元素放到右侧
        for (int j = left; j < right; ++j) {
            if (arr[j] < pivot) {
                ++i;
                swap(arr[i], arr[j]);
            }
        }
        // 将基准元素放到正确的位置
        swap(arr[i + 1], arr[right]);
        // 递归调用对基准左右两侧的子数组进行排序
        quickSort(arr, left, i);       // 对左侧子数组进行排序
        quickSort(arr, i + 2, right);  // 对右侧子数组进行排序
    }
}

最坏情况：假设每次选择的基准元素总是数组中的最小或最大值。在这种情况下，分割后的子数组大小极不均衡，导致每次递归的规模仅减少一个元素，使得时间复杂度达到 O(n^2)。

平均情况：通常情况下，基准元素的选择能够使得数组分割较为均匀，每次递归的规模约为原数组的一半，因此平均情况下的时间复杂度为 O(n log n)。

介绍完时间复杂度后，我们再来看空间复杂度：

空间复杂度是指算法在运行过程中所需的额外空间大小，通常是指在计算机内存中用于存储临时数据和辅助空间的量度。

空间复杂度可以通过以下几种方式进行计算和估算：

原地算法：一些算法可以在输入数据所占用的空间上进行操作，而不需要额外的辅助空间。这种情况下，空间复杂度为 O(1)，即常数空间复杂度。

额外空间的分配：一些算法可能需要额外的空间来存储中间结果或辅助数据结构，这种情况下，空间复杂度会根据额外空间的大小而变化。

我们利用逆序算法来介绍空间复杂度：

额外空间存储：

在逆序算法中，通常需要创建一个新的数据结构（如新的数组、链表等）来存储逆序后的结果。空间复杂度取决于存储逆序后数据所需的额外空间大小。

void reverseArray(int arr[], int n) {
    // 创建一个新的数组用于存储逆序后的元素
    int reversed[n];
    // 将原数组元素逆序存储到新数组中
    for (int i = 0; i < n; ++i) {
        reversed[n - 1 - i] = arr[i];
    }
    // 将逆序后的数组复制回原数组
    for (int i = 0; i < n; ++i) {
        arr[i] = reversed[i];
    }
}

这种方法需要额外的辅助空间来存储逆序后的结果，因此空间复杂度为 O(n)，其中 n 是数组的长度。

原地逆序算法：

void reverseArray(int arr[], int n) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        // 交换左右指针对应位置的元素
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        // 移动指针
        ++left;
        --right;
    }
}