Lesson 13. 时间复杂度，排序和贪心算法

1. 时间复杂度简介

时间复杂度 是衡量算法执行效率的重要指标，它描述了随着输入数据量的增大，算法执行时间的增长速度。时间复杂度通常表示为 O(某个函数)，其中 "O" 表示增长的上限。以下介绍四种常见的时间复杂度：O(1)、O(n)、O(n^2) 和 O(n log n)。

常见的时间复杂度

O(1)：常数时间复杂度
- 操作的执行时间不随输入数据的大小而变化。
- 例子：从数组中获取第 k 个元素。

C++
#include <iostream>
using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int k = 2;  // 获取第三个元素（索引从0开始）
   int element = arr[k];  // O(1)
   cout << "Element at index " << k << ": " << element << endl;
   return 0;
}

时间复杂度：无论数组大小是多少，获取第 k 个元素所需时间是固定的，属于 O(1)。

O(n)：线性时间复杂度
- 操作的执行时间随着输入数据量线性增长。
- 例子：遍历一个数组。

C++
#include <iostream>
using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   for (int i = 0; i < n; i++) {  // O(n)
       cout << "Element at index " << i << ": " << arr[i] << endl;
   }
   return 0;
}

时间复杂度：遍历整个数组需要的时间与数组的长度 n 成正比，属于 O(n)。

O(n^2)：平方时间复杂度
- 操作的执行时间与输入数据量的平方成正比，常见于双重循环。
- 例子：打印二维数组中每个元素。

C++
#include <iostream>
using namespace std;

int main() {
   int arr[3][3] = {
       {1, 2, 3},
       {4, 5, 6},
       {7, 8, 9}
   };
   for (int i = 0; i < 3; i++) {  // O(n)
       for (int j = 0; j < 3; j++) {  // O(n)
           cout << "Element at [" << i << "][" << j << "]: " << arr[i][j] << endl;
       }
   }
   return 0;
}

时间复杂度：双重循环嵌套遍历每个元素，总的执行时间是 n 的平方，属于 O(n^2)。

O(n log n)：常见于排序算法（此章节后半部分会详细讲解）
- 例子：归并排序、快速排序。

C++
#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
   int n1 = m - l + 1;
   int n2 = r - m;

   vector<int> L(n1), R(n2);

   for (int i = 0; i < n1; i++)
       L[i] = arr[l + i];
   for (int i = 0; i < n2; i++)
       R[i] = arr[m + 1 + i];

   int i = 0, j = 0, k = l;
   while (i < n1 && j < n2) {
       if (L[i] <= R[j]) {
           arr[k] = L[i];
           i++;
       } else {
           arr[k] = R[j];
           j++;
       }
       k++;
   }

   while (i < n1) {
       arr[k] = L[i];
       i++;
       k++;
   }

   while (j < n2) {
       arr[k] = R[j];
       j++;
       k++;
   }
}

void mergeSort(vector<int>& arr, int l, int r) {
   if (l >= r) return;
   int m = l + (r - l) / 2;
   mergeSort(arr, l, m);
   mergeSort(arr, m + 1, r);
   merge(arr, l, m, r);
}

int main() {
   vector<int> arr = {12, 11, 13, 5, 6, 7};
   int arr_size = arr.size();

   mergeSort(arr, 0, arr_size - 1);

   cout << "Sorted array is: ";
   for (int i = 0; i < arr_size; i++)
       cout << arr[i] << " ";
   return 0;
}

时间复杂度：归并排序通过递归将数组分成更小的部分进行排序，时间复杂度为 O(n log n)。

为什么是 O(n log n)? 归并排序是一种 分治算法，我们可以把归并排序的步骤分为两部分：拆分和合并。

Text Only
**1. 拆分过程：递归分解数组**

归并排序首先将数组递归地对半拆分，直到每个子数组只剩下一个元素。这个过程类似于构建一棵二叉树，每次将问题的规模减半。

- 对一个长度为 `n` 的数组：
    - 第一层：1 个长度为 `n` 的数组
    - 第二层：2 个长度为 `n/2` 的数组
    - 第三层：4 个长度为 `n/4` 的数组
    - ...
    - 第 `log n` 层：每个数组的长度是 1，共有 `n` 个数组

因为每次都对数组进行二分，所以整个递归树的深度是 `log n`。

**2. 合并过程：线性合并**

当子数组拆分到最小（每个数组只有一个元素）时，归并排序开始合并这些子数组。合并两个有序数组的时间与它们的长度成正比，也就是说合并两个数组的时间是 `O(n)`。

在递归树的每一层，所有数组的总长度始终是 `n`，因此：

- 第一层：合并一个长度为 `n` 的数组，时间是 `O(n)`
- 第二层：合并两个长度为 `n/2` 的数组，总时间仍然是 `O(n)`
- 第三层：合并四个长度为 `n/4` 的数组，总时间也是 `O(n)`

无论有多少个小数组，合并每一层的总时间都是 `O(n)`。

**3. 递归树的层数**

拆分的过程最多进行 `log n` 次（每次将数组对半分）。因此，递归树的深度是 `log n`，即最多有 `log n` 层。

**总时间复杂度的计算**

因为每一层的合并时间都是 `O(n)`，而整个递归树有 `log n` 层，所以总的时间复杂度是 `O(n) * O(log n) = O(n log n)`

**为什么不会超过 `O(n log n)`**

有人可能会疑惑：既然我们在递归中反复分裂数组，为什么时间复杂度不会超过 `O(n log n)` 呢？

- **每层的合并操作是线性的**：虽然递归分裂会产生多个小数组，但每一层中所有数组的总长度仍然是 `n`。也就是说，每一层合并的时间复杂度始终是 `O(n)`，不会累积更多复杂度。
- **递归的深度是 `log n`**：由于每次递归都将数组对半分裂，整个递归过程只会进行 `log n` 次分裂。因此，递归树的深度是 `log n`。

最终的时间复杂度是每层的时间 `O(n)` 乘以递归树的层数 `log n`，所以总时间复杂度是 `O(n log n)`。

时间复杂度总结

O(1)：执行时间不受输入规模影响。
O(n)：执行时间随输入规模线性增长。
O(n^2)：执行时间与输入规模的平方成正比，通常发生在嵌套循环中。
O(n log n)：常见于高效的排序算法。

具体实例

考虑一个简单的算法：计算数组中所有元素的和。

C++
#include <iostream>
using namespace std;

int sumArray(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];  // 基本操作
    }
    return total;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of array: " << sumArray(arr, n) << endl;
    return 0;
}

步骤分析

确定基本操作：
- 基本操作是 total += arr[i]。
计算基本操作的次数：
- 在最坏情况下，for 循环会执行 n 次（其中 n 是数组 arr 的长度）。
- 因此，基本操作的次数为 n 。
使用大 O 表示法：
- 所以时间复杂度是 O(n)。
考虑最坏情况：
- 无论输入的具体内容如何，只要数组长度为 n ，基本操作都会执行 n 次，因此最坏情况为 O(n)。
特殊情况：
- 如果数组为空，循环不会执行，但我们仍然认为时间复杂度为 O(n)，因为我们关注的是输入的规模。

随堂练习

判断以下代码的时间复杂度

C++
#include <iostream>
using namespace std;

int findMax(int arr[], int n) {
    int maxNum = arr[0];
    for (int i = 0; i < n; i++) {  // 基本操作
        if (arr[i] > maxNum) {
            maxNum = arr[i];
        }
    }
    return maxNum;
}

int main() {
    int arr[] = {1, 5, 3, 9, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max number: " << findMax(arr, n) << endl;
    return 0;
}

解答

第一段代码（findMax）：

基本操作是 if (arr[i] > maxNum)。
在最坏情况下，循环执行 n 次。
所以时间复杂度是 O(n)。

2. 排序算法与应用

排序是程序设计中一个非常基础但重要的操作。它不仅可以让数据按特定顺序排列，还能帮助我们解决许多与数据处理相关的问题。通过排序，我们可以更快地解决找第 K 大元素、合并重叠区间等问题。

适用场景

排序的应用场景非常广泛，尤其是在数据处理中，你会经常遇到需要对数据进行排序的情况：

找出第 K 大元素：通过排序数据，可以很快找出第 K 大（或第 K 小）的元素。
合并区间：当处理多个区间或段时，常常需要先将这些区间按某个维度排序，然后合并它们。
例子：合并日程、任务时间段等数据，解决区间重叠问题。
优化操作：不同的排序算法在面对不同规模的数据时表现各异，因此选择合适的排序算法对于提高程序性能非常重要。

常用技巧

1. 内置排序函数

大多数编程语言都提供了内置的排序函数，它们经过优化，能以高效的方式进行排序。C++ 提供了 std::sort() 函数。

示例代码：

C++
#include <iostream>
#include <vector>
#include <algorithm>  // 包含 std::sort 函数

using namespace std;

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9};  // 定义一个整数数组

    // 使用内置的排序函数对数组进行升序排序
    sort(nums.begin(), nums.end());

    // 输出排序后的数组
    cout << "Sorted array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

说明：

这里我们使用了 std::sort() 函数，它会对 nums 数组进行升序排序。
使用内置函数 sort() 是一种非常快捷的方法，对于大多数简单排序任务，它的效率非常高。

2. 自定义排序

有时我们需要按照自定义的规则对数据进行排序。比如，我们可能希望按数组的某个特定元素进行排序，而不是按默认的顺序。在 C++ 中，我们可以通过 std::sort() 函数的第三个参数来自定义排序规则。

示例代码：

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 自定义比较函数，按数组中第二个元素升序排序
bool compareBySecondElement(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

int main() {
    vector<vector<int>> data = {{1, 3}, {2, 2}, {3, 1}};

    // 使用自定义的排序规则按第二个元素排序
    sort(data.begin(), data.end(), compareBySecondElement);

    // 输出排序后的二维数组
    for (const auto& row : data) {
        cout << row[0] << ", " << row[1] << endl;
    }

    return 0;
}

说明：

在这个例子中，我们使用了自定义比较函数 compareBySecondElement 来按照二维数组中每一行的第二个元素进行排序。
std::sort() 的第三个参数就是这个比较函数，用于告诉 sort() 应该如何比较每对元素。

3. 排序优化

排序算法在处理不同规模数据时表现各异。以下是一些常见的排序算法及其适用场景，供大家初步了解：

选择排序：适用于小规模数据集，时间复杂度为 (O(n^2))。
它的特点是每次选择未排序部分中的最小值，然后将其与当前元素交换。虽然简单易懂，但性能较差，不适合大数据集。
插入排序：适合于几乎已排序的数据集，时间复杂度也是 (O(n^2))。
插入排序的优势是当数据几乎有序时，它的效率会比选择排序好得多。
快速排序：性能较好的通用排序算法，时间复杂度为 (O(n log n))。
它通过选择一个基准元素（pivot），将数组划分为两部分，并递归地对这两部分进行排序。适合大规模数据集。
归并排序：与快速排序一样，时间复杂度为 (O(n log n))，但它是稳定的排序算法。
归并排序将数组不断拆分，然后合并排序好的子数组。虽然它的性能稳定，但需要额外的内存来存储拆分的数组。
冒泡排序：是一种简单但性能较差的排序算法，时间复杂度为 (O(n^2))。
它的基本思想是通过不断比较相邻的元素并交换它们，将较大的元素“冒泡”到数组的末尾。适用于非常小规模的数据集。
堆排序：基于二叉堆结构的排序算法，时间复杂度为 (O(n log n))。
堆排序通过建立一个最大堆或最小堆来进行排序。虽然堆排序的时间复杂度和快速排序相同，但它不需要额外的内存空间（不像归并排序）。
计数排序：时间复杂度为 (O(n+k))，适用于数据范围较小的场景。
它通过统计每个元素出现的次数来排序，适用于整数排序且数据范围不大的情况。计数排序的性能在数据范围较小时非常优异，但当数据范围很大时，空间消耗会过高。
桶排序：时间复杂度为 (O(n+k))，适合均匀分布的数据集。
它将元素分布到多个桶中，分别对每个桶进行排序，然后再合并所有桶中的元素。对于分布均匀的数据，桶排序的性能非常好，但如果数据分布不均，性能可能会退化。
基数排序：一种非比较排序算法，时间复杂度为 (O(n times k))，适用于处理位数固定的数据。
它通过按位（或数字）进行多次排序来完成整体排序，适用于对整数或字符串进行排序。基数排序的性能在处理大规模、固定位数的数字时较好。

2.1 排序算法例题讲解

2.1.1 LC215：找出数组中的第 `K` 大元素

题目描述：

给定一个未排序的数组，找出其中第 K 大的元素。

解题思路：

可以先对数组进行降序排序，然后直接返回排好序后的数组中的第 K 个元素。

代码实现：

C++
class Solution {
public:
    // 自定义比较函数，进行降序排序
    bool compareDesc(int a, int b) {
        return a > b;  // 返回 a > b 表示降序
    }

    int findKthLargest(vector<int>& nums, int k) {
        // 对数组进行降序排序
        sort(nums.begin(), nums.end(), compareDesc);
        // 返回第 K 个元素
        return nums[k - 1];
    }
};

说明：

这里我们通过定义 compareDesc 函数，该函数将两个整数 a 和 b 进行比较，并返回 true 如果 a > b，这就实现了降序排序。
sort() 函数的第三个参数传入自定义的比较函数 compareDesc 来控制排序顺序。

2.2 排序算法举一反三

2.2.1 LC56：合并区间

题目描述：

给定若干个闭合区间 [x1, y1], [x2, y2], ...，请将所有重叠的区间合并。例如，区间 [1, 3] 和 [2, 6] 可以合并为 [1, 6]。

解题思路：

首先，按照区间的起始值对所有区间进行排序。
然后遍历每个区间，若当前区间与前一个区间重叠，则合并它们；否则将当前区间直接加入结果列表。

代码实现：

C++
class Solution {
public:
    // 自定义比较函数，按区间的起始值进行排序
    bool compareIntervals(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];  // 按照起始位置升序排序
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};

        // 按区间起始位置排序
        sort(intervals.begin(), intervals.end(), compareIntervals);

        vector<vector<int>> merged;

        // 使用传统的 for 循环遍历区间
        for (int i = 0; i < intervals.size(); i++) {
            if (merged.empty() || merged.back()[1] < intervals[i][0]) {
                // 如果结果为空或当前区间与上一个区间不重叠，直接加入结果
                merged.push_back(intervals[i]);
            } 
            else {
                // 如果重叠，更新最后一个区间的结束位置
                merged.back()[1] = max(merged.back()[1], intervals[i][1]);
            }
        }

        return merged;
    }
};

讲解：

自定义排序：为了将所有区间按起始值升序排列，我们定义了 compareIntervals 函数，并将其传递给 sort() 函数，确保区间按照起始值排序，便于后续的合并操作。
遍历区间：排序后，我们遍历每一个区间。通过比较每个区间的起始值和上一个合并区间的结束值，判断它们是否重叠：
- 如果没有重叠，就将当前区间直接加入 merged 结果。
- 如果重叠，更新上一个合并区间的结束值，使得它可以涵盖当前区间。
合并逻辑：合并是通过比较 merged.back()[1]（已合并的最后一个区间的结束值）与当前区间的起始值来进行的。如果当前区间的起始值大于上一个区间的结束值，则说明它们不重叠，否则进行合并。

2.2.2 LC252：会议室

题目描述：

给定一系列会议时间区间，判断是否能让所有会议无冲突地安排在一间会议室中。

解题思路：

可以将所有的会议按照开始时间排序，然后遍历每个会议，检查是否有重叠区间。

代码实现：

C++
class Solution {
public:
    // 自定义比较函数，按会议的开始时间进行排序
    bool compareMeetings(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];  // 按照开始时间升序排序
    }

    bool canAttendMeetings(vector<vector<int>>& intervals) {
        // 使用自定义的比较函数进行排序
        sort(intervals.begin(), intervals.end(), compareMeetings);

        // 遍历会议，检查是否存在重叠
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }

        return true;
    }
};

讲解：

自定义排序函数：定义了 compareMeetings 函数来根据会议的开始时间对会议区间进行排序。函数通过比较会议的开始时间来决定会议的顺序。
排序会议：通过 sort() 函数并传入自定义比较函数 compareMeetings，我们将会议按开始时间进行排序。
检查重叠：排序完成后，我们依次检查每个会议是否与上一个会议时间重叠。如果发现重叠，返回 false；如果没有重叠，最终返回 true。

2.2.3 LC347：前 K 个高频元素

题目描述：

给定一个非空的整数数组，返回其中出现频率最高的前 K 个元素。

解题思路：

使用哈希表统计每个元素的出现次数。
将哈希表中的元素放入一个数组中，按出现次数从高到低排序。
返回排序后前 K 个元素。

代码实现：

C++
// 自定义比较函数，按频率降序排序
bool compareByFrequency(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;  // 按照频率降序排列
}

vector<int> topKFrequent(vector<int>& nums, int k) {
    // 使用哈希表统计每个元素的出现次数
    unordered_map<int, int> frequencyMap;
    for (int num : nums) {
        frequencyMap[num]++;
    }

    // 将哈希表中的元素转换为二维数组，第一维是数字，第二维是频率
    vector<pair<int, int>> frequencyList;
    for (auto& it : frequencyMap) {
        frequencyList.push_back(it);
    }

    // 使用自定义的比较函数进行排序
    sort(frequencyList.begin(), frequencyList.end(), compareByFrequency);

    // 取出前 K 个频率最高的元素
    vector<int> result;
    for (int i = 0; i < k; i++) {
        result.push_back(frequencyList[i].first);
    }

    return result;
}

讲解：

自定义比较函数：定义了 compareByFrequency 函数，用于比较 pair<int, int> 类型的数据，按频率降序排列。
哈希表统计频率：使用 unordered_map 来记录每个元素出现的次数，键为元素，值为该元素的出现次数。
转换为可排序列表：将 unordered_map 的键值对转换为 vector<pair<int, int>>，其中 pair.first 是数字，pair.second 是该数字的频率。
排序：使用 sort() 函数，并传入自定义的比较函数 compareByFrequency，实现按频率从高到低的排序。
取前 K 个元素：从排好序的 frequencyList 中取前 K 个元素的 first（即数字），并返回结果。

3. 贪心算法

贪心算法是一种解决问题的策略，其核心思想是：在解决问题的每一步中，总是选择当前看起来最优的选择，通过一系列这样的局部最优选择，最终希望获得全局最优解。

需要注意的是，贪心算法并不总是能得到全局最优解。它只有在某些特定问题中有效，特别是当问题满足贪心选择性质时。

贪心算法的特点

局部最优选择：
贪心算法在每一步中只做出当前看起来最优的选择，而不关心之后可能发生的情况。它不会考虑这次选择是否会影响后续决策，只看当下哪个选项是最有利的。例如，在分数背包问题中，贪心策略是每次优先选择单位重量价值最高的物品，因为它在当前的选择中带来的收益最大。
- 优点：通过每一步的最优选择，可以快速找到一个可行解。贪心算法的规则简单、直观，易于实现，通常可以通过一次扫描或排序解决问题，时间复杂度较低。例如在分数背包问题中，贪心算法只需要按单位价值排序，时间复杂度为 (O(n log n))。
- 缺点：局部最优解不一定能保证全局最优，因为在一些问题中，最佳的整体方案依赖于多步决策的综合效果，而不是单纯的每一步最优。贪心算法无法通过局部最优解找到全局最优解，尤其在复杂问题（如 0-1 背包问题）中，它可能会陷入次优解。
不可回溯：
贪心算法的一个重要特点是决策不可回头修改。一旦做出某个选择，算法就不会再考虑改变它，即使后续发现这个选择可能不是最优的。因为贪心算法依赖的是当前最优选择的策略，所以它不会为未来的选择留下回旋余地。
- 优点：由于不需要回溯，贪心算法执行速度非常快，时间复杂度通常比需要回溯的算法（如动态规划、回溯法等）更低。贪心算法的高效性体现在其快速、直接的解决思路上，适用于处理大规模问题时的高效求解。
- 缺点：由于贪心算法不具备回溯能力，它只能在符合贪心选择性质的问题中有效。如果问题不满足这种性质，算法可能会在后续步骤中陷入次优解或死胡同，无法达到全局最优解。

具体步骤

贪心算法通常遵循以下基本步骤：

明确贪心策略：确定每一步的局部最优解选择策略。
排序：如果问题涉及多个选择，通常需要对其进行排序（如按结束时间、单位价值等）。
逐步选择：根据贪心策略，按照排序结果逐步选择最优项。
检查可行性：每次选择时，确保当前选择满足问题的约束条件（如不冲突、不超出容量等）。
构造解：将所有的选择组合起来，形成问题的最终解。

贪心算法的适用条件

要判断一个问题是否适合使用贪心算法，可以观察以下特征：

贪心选择性质：在每一步中，选择的局部最优解能够保证不会影响后续选择的最优性，即贪心选择在每一步都能保持全局最优。
无后效性：当前的选择不会影响未来的选择。每个选择的结果只依赖当前状态，而不会依赖之前的决策。即一旦做出了某个选择，该选择就不可改变。

如果问题满足以上两点，那么通常可以使用贪心算法求解。

贪心算法 vs 动态规划的判定标准

在区分一个问题是否适合使用贪心算法或动态规划时，最优子结构和子问题重叠是关键的判定标准：

贪心选择的适用条件：
- 局部最优选择性质：贪心算法每一步做出的选择都是局部最优解，且这些局部最优解构成了全局最优解。这种性质一般存在于可以通过逐步选择解决的简单优化问题。
- 无后效性：未来的决策不依赖于之前的选择，因此一旦做出了选择，不需要回溯检查。例如，分数背包问题，每次选择单位价值最高的物品不会影响之后的选择。
动态规划的适用条件：
- 最优子结构：全局最优解依赖于子问题的最优解。如果每个子问题的解都影响到全局最优解，那么这种问题通常需要使用动态规划来解决。背包问题中的0-1 背包问题就属于此类问题，当前物品是否选入背包会影响未来的选择，因此无法简单通过贪心策略得到最优解。
- 子问题重叠：如果问题可以被拆分为多个子问题，且这些子问题之间存在重叠（即某个子问题的解会多次被使用），那么动态规划是更有效的选择。

总结来看，如果问题可以通过单纯的局部最优选择解决，并且未来的选择不依赖于过去的选择，通常可以使用贪心算法；否则需要通过动态规划来解决问题。

简单例子

1. 分数背包问题（贪心算法）

问题描述：你有一个容量为 50 的背包，和一堆物品，每件物品都有重量和价值。你可以将每件物品按任意比例装入背包（例如可以装入物品的一部分），目标是让背包里的物品总价值最大化。

贪心策略：优先选择单位重量价值最高的物品，尽可能多地装入背包。

分析步骤：

明确贪心策略：每次选择单位重量价值最高的物品，尽可能多装入背包。
排序：将所有物品按照单位重量的价值从高到低排序。
逐步选择：按照排序后的顺序，优先选择单位价值最高的物品，直到背包装满。
检查可行性：每次选择物品时，检查背包剩余容量是否足够。如果容量不足，将物品的一部分装入背包。
构造解：将选入背包的物品组合起来，计算总价值，得到问题的解。

2. 0-1 背包问题（动态规划）

问题描述：你有一个容量为 50 的背包和一堆物品，每件物品都有一个确定的重量和价值。你只能选择将某件物品完全放入背包或者不放入，不能只装一部分。目标是选择一些物品放入背包，使得背包中的物品总价值最大化。

动态规划思路：对于每件物品，你需要决定是否放入背包。每次的选择都依赖于背包当前的容量以及之前的选择。因为选择一次物品会影响到后续能装多少东西，所以我们不能使用贪心算法，而需要通过动态规划来考虑所有可能的组合。

用简单的话来理解动态规划的思路：

状态：我们用 dp[i][w] 表示前 i 个物品在容量为 w 的背包中所能装的最大总价值。换句话说，dp[i][w] 是一个中间结果，告诉我们如果只考虑前 i 个物品，并且背包容量为 w，我们能装的最高价值是多少。
状态转移方程：这个就是动态规划中的“规则”，用来指导我们如何根据前面的计算结果推导出当前的最优解。

对于每件物品 i，你有两种选择：

不选这件物品：那么最大价值就是 dp[i-1][w]，即背包容量保持不变，前面 i-1 个物品的最优解。
选这件物品：如果选择物品 i，则当前的背包容量减少 weight[i]，而我们还获得了 value[i] 这个物品的价值。所以最大价值变成了 dp[i-1][w - weight[i]] + value[i]。

两者取较大值： dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

理解这段公式：
- 如果你不选物品 i，那么你只能依赖前面 i-1 个物品在容量为 w 时的最优解，即 dp[i-1][w]。
- 如果你选了物品 i，那你需要腾出足够的空间来放它，也就是说背包容量会减少 weight[i]，然后你能获得这件物品的价值 value[i]，再加上前 i-1 个物品在减少了的容量 w - weight[i] 时的最优解，即 dp[i-1][w - weight[i]]。
如何求解：我们从空背包开始，逐步增加物品和容量，每次用上面这个公式去更新当前背包容量的最优解。通过这个递推过程，最后就能得到整个背包的最大价值。

举个简单例子：

假设我们有一个背包容量为 5，物品如下：

物品 1：重量 2，价值 3
物品 2：重量 3，价值 4
物品 3：重量 4，价值 5

动态规划表的构建过程：

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	3	4	5	7

当 i = 1（只考虑物品1）：物品1的重量为2，所以当背包容量小于2时，无法放入，价值为0；当容量等于2或大于2时，放入物品1，价值为3。
当 i = 2（考虑前两个物品）：在容量为3时，放入物品2比物品1好，价值为4；当容量为5时，放入物品1和物品2，价值为7。
当 i = 3（考虑三个物品）：物品3太重，不能放入背包，之前的最优值保持不变。

最终，我们得到的最大价值为7。

3. 活动选择问题（贪心算法）

问题：你有一系列活动，每个活动都有开始时间和结束时间。你需要选择尽可能多的活动，并且这些活动不能重叠。

贪心策略：每次选择结束时间最早且不与其他活动冲突的活动。

步骤：

明确贪心策略：每次选择结束时间最早的活动，以留出更多时间给其他活动。
排序：将活动按结束时间从早到晚排序。
逐步选择：从第一个活动开始，依次选择结束时间最早且与之前活动不冲突的活动。
检查可行性：每次选择活动时，检查该活动是否与已经选择的活动冲突。
构造解：将每次选择的活动加入最终解，直到没有活动可以再选。

贪心算法的局限性

贪心算法并不总是能找到最优解。比如：

1. 0-1 背包问题

在这个问题中，你必须选择完整的物品（要么全选，要么不选），而不能选择物品的一部分。如果你使用贪心算法来选择单位价值最高的物品，很可能会因为重量限制而无法选择最优组合。

2. 最短路径问题

在某些图上，贪心策略（总是选择距离最近的节点）并不总能找到最短路径。

总结：

贪心算法是一种简单而高效的策略，适合用在那些可以通过局部最优解得到全局最优解的问题上。它的关键在于每一步都做出最好的局部选择，希望最终得到最优解。虽然并不是所有问题都适合用贪心算法，但在合适的情况下，它能快速找到解。

3.1 贪心算法例题讲解

3.1.1 LC455: 分发饼干

题目描述：有 g 个孩子和 s 个饼干，每个孩子都有一个贪心指数，表示他最少需要多少饼干。每个饼干都有一个大小，表示它可以满足某个孩子的需求。你要分发尽可能多的饼干给孩子，使得最多的孩子能得到满足。

贪心算法步骤：

排序：将孩子的需求（贪心指数）和饼干的大小都进行升序排序。
- 这样可以确保我们可以用最小的饼干去满足最小需求的孩子，从而尽可能满足更多的孩子。
匹配：从最小的饼干和最小需求的孩子开始匹配。
- 每次如果饼干大小可以满足当前孩子的需求，就将这个饼干分配给这个孩子，然后移动到下一个孩子。
- 如果当前饼干不够满足孩子需求，就继续尝试下一个更大的饼干，直到所有孩子或饼干用完。

代码实现：

C++
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 将孩子的需求和饼干的大小排序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0, j = 0;

        // 遍历孩子和饼干数组
        while (i < g.size() && j < s.size()) {
            // 如果当前饼干能满足当前孩子
            if (s[j] >= g[i]) {
                i++;  // 满足了孩子 i，处理下一个孩子
            }
            j++;  // 尝试下一个饼干
        }

        return i;  // 返回满足的孩子数量
    }
};

讲解：

排序步骤：
- 首先将孩子的需求数组 g 和饼干大小数组 s 进行排序。排序后，较小的孩子需求和较小的饼干会排列在数组前面，这样可以尽量用最小的饼干去满足最小需求的孩子。
匹配过程：
- 通过两个指针 i 和 j 分别指向孩子和饼干的数组。初始时，i = 0，j = 0，表示从第一个孩子和第一个饼干开始。
- 当 s[j] >= g[i] 时，表示当前饼干可以满足当前孩子的需求，孩子被满足，移动指针 i，处理下一个孩子。
- 无论是否满足，饼干都会被使用，所以 j++ 每次都会移动到下一个饼干。
最终结果：
- 当遍历结束时，i 的值就是能够满足的孩子数量，即最后返回的结果。

3.2 贪心算法举一反三

3.2.1 LC 435: 无重叠区间

题目描述：给定一组区间，找到最少需要移除的区间数量，使得剩下的区间互不重叠。

贪心算法步骤：

排序：按照区间的结束时间进行升序排序。排序后，我们可以优先选择结束时间较早的区间，这样能够为后续区间留出更多空间，减少冲突。
选择区间：每次选择结束时间最早且不与前一个选择的区间重叠的区间。如果当前区间的开始时间小于前一个区间的结束时间，说明发生了重叠，我们就需要移除当前区间。否则，我们更新当前区间为新的结束时间，并继续处理下一个区间。

代码实现：

C++
class Solution {
public:
    // 自定义比较函数，按结束时间排序
    bool compareIntervals(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];  // 按照区间的结束时间升序排列
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        // 使用自定义的比较函数进行排序
        sort(intervals.begin(), intervals.end(), compareIntervals);

        int count = 0;
        int end = intervals[0][1];

        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < end) {
                count++;
            } 
            else {
                end = intervals[i][1];
            }
        }

        return count;
    }
};

讲解：

排序步骤：
- 按区间的结束时间对所有区间进行排序。排序后的区间按结束时间从小到大排列，这样可以确保我们每次选择的区间结束得最早，能够尽量避免后续区间与其发生重叠。
遍历选择区间：
- 初始化一个 end 变量，表示已选定区间的结束时间。遍历剩余区间时，检查每个区间的开始时间是否与当前选定的结束时间发生重叠。如果当前区间的开始时间小于 end，说明发生了重叠，必须移除当前区间。如果没有重叠，则更新 end 为当前区间的结束时间。
返回结果：
- count 记录了被移除的区间数，遍历结束后，返回这个移除的区间数。

3.2.2 LC 605: 种花问题

题目描述：
给定一个表示花坛的整数数组 flowerbed，其中 flowerbed[i] = 0 表示该位置是空的，flowerbed[i] = 1 表示该位置已经种了花。花坛中花不能种在相邻的地块上，问是否能够在不违反规则的情况下再种下 n 朵花。

例如： - 输入：flowerbed = [1,0,0,0,1], n = 1 - 输出：true - 解释：我们可以在下标为 2 的地方种一朵花。

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
解释：不能种下两朵花而不违反相邻规则。

贪心算法步骤：

遍历花坛：从左到右依次检查每个位置。如果当前位置是空的 0，并且它的前一个位置和后一个位置也是空的（如果存在），那么可以在这个位置种花。
计数并跳过相邻位置：每次成功种花后，增加计数，并跳过下一个位置，因为相邻位置不能种花。

代码实现：

C++
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int count = 0;  // 记录可以种花的数量

        // 遍历整个花坛
        for (int i = 0; i < flowerbed.size(); i++) {
            // 判断当前位置是否可以种花（检查前后位置，注意边界条件）
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;  // 种花
                count++;  // 计数增加
                i++;  // 跳过下一个位置，避免相邻种花
            }
            if (count >= n) return true;  // 如果种够 n 朵花，返回 true
        }
        return count >= n;  // 遍历结束，检查是否种够 n 朵花
    }
};

讲解：

遍历判断能否种花：
- 遍历整个花坛，检查每个位置是否可以种花。当前位置必须满足三个条件才能种花：当前为 0，前一个位置（如果存在）为 0，后一个位置（如果存在）也为 0。注意检查花坛的边界（即第一个和最后一个位置）时，不需要检查不存在的前后位置。
种花后跳过相邻位置：
- 每次成功种花后，跳过下一个位置，因为根据规则，相邻的位置不能种花。
提前终止：
- 如果在遍历过程中已经种够了 n 朵花，则可以提前返回 true。如果遍历结束后还没有种够，则返回 false。

3.2.3 LC 1029: 两地调度

题目描述：
有 2N 个人，每个人都需要飞往 A 市或 B 市。给定一个 costs 数组，其中 costs[i] = [aCost, bCost] 表示第 i 个人飞往 A 市的费用和飞往 B 市的费用。现在需要把这些人分配到两个城市，使得 N 个人飞往 A 市，N 个人飞往 B 市，要求总费用最小。

贪心算法步骤： 1. 计算成本差异：我们计算每个人去 A 市和 B 市的费用差，即 aCost - bCost。我们希望优先让那些去 B 市更便宜的人去 B 市，而让去 A 市更便宜的人去 A 市。

排序选择：根据去 A 市和 B 市的费用差异排序。差异越大的人，意味着去 A 市或 B 市对成本影响越大，因此我们优先考虑这些人。
分配城市：前 N 个人安排到 A 市，后 N 个人安排到 B 市，最终得到最小的总费用。

代码实现：

C++
class Solution {
public:
    // 自定义比较函数，按去 A 市和 B 市的费用差进行排序
    bool compareCosts(const vector<int>& a, const vector<int>& b) {
        return (a[0] - a[1]) < (b[0] - b[1]);  // 按 aCost - bCost 进行升序排序
    }
    int twoCitySchedCost(vector<vector<int>>& costs) {
        // 使用自定义的比较函数进行排序
        sort(costs.begin(), costs.end(), compareCosts);

        int totalCost = 0;
        int n = costs.size() / 2;

        // 前 N 个人去 A 市，后 N 个人去 B 市
        for (int i = 0; i < n; i++) {
            totalCost += costs[i][0];  // 去 A 市的费用
        }
        for (int i = n; i < 2 * n; i++) {
            totalCost += costs[i][1];  // 去 B 市的费用
        }

        return totalCost;
    }
};

讲解：

计算成本差异：
- 每个人都有去 A 市和 B 市的两种选择，我们可以通过 aCost - bCost 来衡量每个人去 A 市的额外成本。如果 aCost < bCost，说明让这个人去 A 市更划算，反之则去 B 市更划算。
排序步骤：
- 我们根据 aCost - bCost 对 costs 数组进行排序，优先让那些去 A 市更便宜的人去 A 市，去 B 市更便宜的人去 B 市。
分配城市：
- 排序后，前一半的人去 A 市，后一半的人去 B 市。这样可以确保在总费用最小的情况下，平衡去两座城市的人数。
返回结果：
- 最终返回总的费用，即前 N 个人的 A 市费用和后 N 个人的 B 市费用之和。

课后练习

排序问题

题目编号	题目名称	简介
LC1288	删除被覆盖的区间	给定一组区间，找出其中未被覆盖的区间，移除被覆盖的区间。
LC1024	视频拼接	给定一组区间，判断是否能够通过拼接区间覆盖整个视频长度。
LC763	划分字母区间	给定一个字符串，将其划分为尽可能多的不重叠的区间，使得每个字母最多出现在一个区间中。
LC57	插入区间	给定一组非重叠的区间和一个新的区间，将新区间插入并合并所有可能的重叠区间。
LC179	最大数	给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

贪心算法问题

题目编号	题目名称	简介
LC121	买卖股票的最佳时机	给定股票价格，找到在最佳时机买入和卖出以获得最大利润。
LC122	买卖股票的最佳时机 II	允许多次买卖，找到在最佳时机买入和卖出以获得最大利润。
LC55	跳跃游戏	给定一个数组，判断是否能跳到数组的最后一个位置。
LC45	跳跃游戏 II	给定一个数组，找到跳到数组最后一个位置的最少跳跃次数。
LC409	最长回文串	给定一个字符串，找到其中能组成的最长回文串的长度。

Lesson 13. 时间复杂度，排序和贪心算法

目录

1. 时间复杂度简介

常见的时间复杂度

时间复杂度总结

具体实例

步骤分析

随堂练习

判断以下代码的时间复杂度

解答

2. 排序算法与应用

适用场景

常用技巧

1. 内置排序函数

2. 自定义排序

3. 排序优化

2.1 排序算法例题讲解

2.1.1 LC215：找出数组中的第 K 大元素

题目描述：

解题思路：

代码实现：

2.2 排序算法举一反三

2.2.1 LC56：合并区间

题目描述：

解题思路：

代码实现：

2.2.2 LC252：会议室

题目描述：

解题思路：

代码实现：

讲解：

2.2.3 LC347：前 K 个高频元素

题目描述：

解题思路：

代码实现：

讲解：

3. 贪心算法

贪心算法的特点

具体步骤

贪心算法的适用条件

贪心算法 vs 动态规划的判定标准

简单例子

1. 分数背包问题（贪心算法）

分析步骤：

2. 0-1 背包问题（动态规划）

用简单的话来理解动态规划的思路：

举个简单例子：

3. 活动选择问题（贪心算法）

贪心算法的局限性

1. 0-1 背包问题

2. 最短路径问题

总结：

3.1 贪心算法例题讲解

3.1.1 LC455: 分发饼干

代码实现：

讲解：

3.2 贪心算法举一反三

3.2.1 LC 435: 无重叠区间

代码实现：

3.2.2 LC 605: 种花问题

代码实现：

3.2.3 LC 1029: 两地调度

代码实现：

课后练习

排序问题

贪心算法问题

2.1.1 LC215：找出数组中的第 `K` 大元素