算法复杂度

1. 什么是算法复杂度

算法复杂度是衡量一个算法在执行过程中的资源消耗量的指标。通常分为 时间复杂度 和 空间复杂度 两种：

• 时间复杂度：表示算法执行所需的时间。
• 空间复杂度：表示算法执行过程中所需的存储空间。

2. 大O表示法

大O表示法用于描述算法复杂度的上界，主要关注的是算法在输入规模很大时，性能的增长情况。

• O(1)：常数时间复杂度，无论输入大小如何，算法总是执行相同数量的步骤。
• O(log n)：对数时间复杂度，随着输入规模的增加，算法执行的步骤按对数关系增加。
• O(n)：线性时间复杂度，算法执行的步骤与输入规模成正比。
• O(n log n)：线性对数时间复杂度，比线性时间复杂度稍差一些，常见于一些高级排序算法。
• O(n^2)：平方时间复杂度，步骤数量随着输入规模的平方增加，常见于一些简单的嵌套循环。
• O(2^n)：指数时间复杂度，步骤数量随着输入规模的指数增长。
• O(n!)：阶乘时间复杂度，极其低效的算法。

3. 时间复杂度的计算方法

计算时间复杂度时，主要关注的是算法中执行次数最多的基本操作。常见的步骤如下：

1. 找到算法的最基本操作：通常是算法中的一个循环或递归调用的步骤。
2. 分析算法的控制结构：例如顺序结构、循环结构和分支结构等。
3. 计算每部分的操作次数：分别计算每个控制结构中的基本操作执行次数，并结合输入规模 $n$ 进行计算。
4. 得出整体复杂度：去除低阶项和常数系数，取最高阶项，得到算法的时间复杂度。

3.1 顺序结构

顺序执行的代码段的时间复杂度是它们每部分复杂度的加和。常数项被忽略，只保留最高阶的复杂度。

示例：

int a = 1;   // O(1)
int b = 2;   // O(1)
int sum = a + b;  // O(1)

该算法是常数时间复杂度 $O(1)$。

3.2 循环结构

循环的复杂度取决于循环次数与循环体内的操作复杂度。一般来说，循环执行的次数乘以内层的操作复杂度就是整体的时间复杂度。

示例：

for (int i = 0; i < n; i++) {
    // 执行 O(1) 的操作
}

该循环执行 $n$ 次，每次执行 $O(1)$ 的操作，因此该算法的时间复杂度是 $O(n)$。

3.3 嵌套循环

嵌套循环的时间复杂度是各层循环次数的乘积。

示例：

for (int i = 0; i < n; i++) {  // O(n)
    for (int j = 0; j < n; j++) {  // O(n)
        // 执行 O(1) 的操作
    }
}

该嵌套循环执行 $n \times n$ 次，每次执行 $O(1)$ 的操作，因此算法的时间复杂度是 $O(n^2)$。

3.4 分治法与递归

递归算法的时间复杂度通常使用递推式进行分析。对于经典的分治算法，比如归并排序，递推式可以表示为：

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

使用递推法或主定理，可以得出该算法的时间复杂度为 $O(n \log n)$。

3.5 例子：求解递归的复杂度

考虑以下递归算法：

void recursion(int n) {
    if (n <= 1) return;
    recursion(n - 1);
}

该递归的深度为 $n$，每次递归中只有一个简单操作，因此复杂度为 $O(n)$。

4. 空间复杂度的计算方法

空间复杂度衡量的是算法在执行过程中所需的额外存储空间。和时间复杂度类似，主要分析算法在执行过程中动态分配的存储空间。

4.1 常数空间

如果算法所需的空间不随输入规模的变化而变化，空间复杂度就是常数级别。

示例：

int a = 0;  // O(1)
int b = 1;  // O(1)

这个算法的空间复杂度是 $O(1)$。

4.2 线性空间

当算法使用了与输入规模成正比的空间时，空间复杂度是线性级别。

示例：

int arr[n];

这个算法需要 $n$ 个整数的存储空间，因此空间复杂度是 $O(n)$。

4.3 递归调用的空间复杂度

递归算法的空间复杂度还需要考虑递归调用栈的深度。如果递归的深度为 $n$，并且每次递归调用只使用常数空间，那么其空间复杂度为 $O(n)$。

5. 常见算法的时间和空间复杂度

6. 如何分析实际算法的复杂度

在面对实际问题时，可以遵循以下步骤分析算法的复杂度：

1. 明确输入规模：确定算法的输入是什么，以及输入的规模 $n$ 是如何定义的。
2. 识别基本操作：找出算法中影响复杂度的关键操作（如循环次数、递归调用次数等）。
3. 分析最坏情况：通常我们分析的是最坏情况下算法的复杂度，这样可以保证算法在任何情况下的表现。
4. 去除常数项与低阶项：只保留影响最大的项，用大O符号表示复杂度。

7. 补档 常见排序算法的复杂度练习

练习 1：冒泡排序 (Bubble Sort)

题目：
请根据以下 C++ 代码分析冒泡排序的时间复杂度。

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

分析：

• 外层循环运行 $n-1$ 次。
• 内层循环运行次数为 $n-1$、$n-2$、$n-3$ 等，因此总的比较次数是：

  $$(n-1) + (n-2) + (n-3) + \dots + 1 = \frac{(n-1)n}{2}$$

  这是一个二次方程，因此时间复杂度为 $O(n^2)$。
• 在最优情况下（即数组已经有序），虽然可以进行优化，减少不必要的交换操作，但嵌套循环仍然执行比较，导致时间复杂度仍为 $O(n^2)$。
• 如果我们添加一个标志位，在没有交换时直接退出循环，则在最优情况下时间复杂度可以降低到 $O(n)$。

答案：

• 最优时间复杂度：$O(n)$（如果做了优化）
• 最坏时间复杂度：$O(n^2)$
• 平均时间复杂度：$O(n^2)$

练习 2：选择排序 (Selection Sort)

题目：
请根据以下 C++ 代码分析选择排序的时间复杂度。

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[min_idx], arr[i]);
    }
}

分析：

• 外层循环运行 $n-1$ 次。
• 内层循环在第 $i$ 次迭代中运行 $n-i-1$ 次。总的比较次数为：

  $$(n-1) + (n-2) + \dots + 1 = \frac{(n-1)n}{2}$$

  因此时间复杂度为 $O(n^2)$。
• 无论输入是否有序，选择排序每次都需要找到未排序部分的最小元素。因此最优、最坏和平均情况下的时间复杂度都是 $O(n^2)$。

答案：

• 最优时间复杂度：$O(n^2)$
• 最坏时间复杂度：$O(n^2)$
• 平均时间复杂度：$O(n^2)$

练习 3：插入排序 (Insertion Sort)

题目：
请根据以下 C++ 代码分析插入排序的时间复杂度。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

分析：

• 外层循环运行 $n-1$ 次。
• 内层循环在最坏情况下（即数组是逆序的）运行 $O(i)$ 次。总的比较和移动操作次数为：

  $$1 + 2 + 3 + \dots + (n-1) = \frac{(n-1)n}{2}$$

  因此最坏情况下的时间复杂度为 $O(n^2)$。
• 在最优情况下（即数组已经有序），内层循环不执行任何移动操作，因此时间复杂度为 $O(n)$。

答案：

• 最优时间复杂度：$O(n)$
• 最坏时间复杂度：$O(n^2)$
• 平均时间复杂度：$O(n^2)$

练习 4：快速排序 (Quick Sort)

题目：
请根据以下 C++ 代码分析快速排序的时间复杂度。

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

分析：

• 最优情况： 每次划分都将数组分成大小相等的两部分，递归深度为 $\log n$。每层的比较操作次数为 $O(n)$，因此总时间复杂度为 $O(n \log n)$。
• 最坏情况： 每次划分时，选择的基准点总是数组的最大或最小值，导致划分非常不平衡。此时，递归深度为 $O(n)$，每层的比较操作仍然是 $O(n)$，因此总时间复杂度为 $O(n^2)$。
• 平均情况： 快速排序的平均时间复杂度为 $O(n \log n)$，这是因为划分通常是相对平衡的。

答案：

• 最优时间复杂度：$O(n \log n)$
• 最坏时间复杂度：$O(n^2)$
• 平均时间复杂度：$O(n \log n)$

练习 5：归并排序 (Merge Sort)

题目：
请根据以下 C++ 代码分析归并排序的时间复杂度。

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

分析：

• 最优情况、最坏情况和平均情况： 归并排序的每次划分将数组分为大小相等的两部分，递归深度为 $\log n$。每层的合并操作需要 $O(n)$ 的时间。因此总的时间复杂度为 $O(n \log n)$。
• 归并排序的操作与输入数据是否有序无关，因此无论输入是最优还是最坏情况，时间复杂度都是 $O(n \log n)$。

答案：

• 最优时间复杂度：$O(n \log n)$
• 最坏时间复杂度：$O(n \log n)$
• 平均时间复杂度：$O(n \log n)$

练习 6：堆排序 (Heap Sort)

题目：
请根据以下 C++ 代码分析堆排序的时间复杂度。

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 

2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

分析：

• 构建堆： 构建最大堆的操作需要 $O(n)$ 的时间。
• 堆排序过程： 每次将堆顶元素与最后一个元素交换，并对剩下的 $n-1$ 个元素重新堆化，每次堆化的时间复杂度为 $O(\log n)$。这个过程重复 $n$ 次，因此时间复杂度为 $O(n \log n)$。
• 最优、最坏和平均情况： 堆排序的时间复杂度与输入数组无关，因此所有情况下时间复杂度均为 $O(n \log n)$。

答案：

• 最优时间复杂度：$O(n \log n)$
• 最坏时间复杂度：$O(n \log n)$
• 平均时间复杂度：$O(n \log n)$