算法基础知识¶

Warning

该文章仍未经过正式校对

Note

本文作者：username

算法是解决问题的步骤和方法，而理解算法的效率对于编写高性能程序至关重要。在本节中，我们将介绍算法复杂度的基本概念，以及如何使用 C++ STL（标准模板库）来简化算法实现。

算法的复杂度¶

算法的复杂度指的是算法在执行过程中所需的资源量，通常包括时间复杂度和空间复杂度。

时间复杂度：衡量算法执行所需的时间
空间复杂度：衡量算法执行所需的内存空间

渐近符号¶

一般的，有三种符号来表示算法的复杂度：

大 O 符号（\(O\)）：表示算法的渐近上界，描述在最坏情况下的复杂度
大 Omega 符号（\(\Omega\)）：表示算法的渐近下界，描述在最好情况下的复杂度
大 Theta 符号（\(\Theta\)）：表示算法的渐近紧确界，描述在平均情况下的复杂度

一般地，我们用 \(n\) 表示问题的规模，而这些符号后面跟着的函数则表示随着 \(n\) 的增长，算法复杂度的增长趋势。

例如，\(O(n^2)\) 表示算法的时间复杂度在最坏情况下是平方级别的，而具体的常数和低阶项等则被忽略。

常见复杂度¶

下表列出了常见的时间复杂度，从最优到最差：

复杂度	名称	示例
\(O(1)\)	常数时间	数组访问、哈希表查找
\(O(\log n)\)	对数时间	二分查找
\(O(n)\)	线性时间	遍历数组
\(O(n \log n)\)	线性对数时间	快速排序、归并排序
\(O(n^2)\)	平方时间	冒泡排序、选择排序
\(O(2^n)\)	指数时间	递归求斐波那契数
\(O(n!)\)	阶乘时间	旅行商问题暴力求解

STL 的应用¶

STL（Standard Template Library）是 C++ 标准库的一部分，提供了一组通用的模板类和函数，用于数据结构和算法的实现。我们主要关注以下数据结构：

STL 容器选择指南¶

需求	使用的数据结构	说明
普通数组	`vector<T>`	不擅长在中间插入删除
字符串	`string`	-
按键值对查找	`unordered_map<K, V>`	哈希表，查找 \(O(1)\)
按键值对查找（保序）	`map<K, V>`	红黑树，查找 \(O(\log n)\)
去重/判断存在性	`unordered_set<T>`	哈希表，查找 \(O(1)\)
去重/判断存在性（保序）	`set<T>`	红黑树，查找 \(O(\log n)\)
最大/最小	`priority_queue<T>`	平衡二叉树，插入删除 \(O(\log n)\)
头尾插入删除	`deque<T>`	-
中间插入删除	`list<T>`	不擅长检索

容器适配器¶

值得注意的是，priority_queue、deque 以及 queue、stack 不仅是容器，还是"容器适配器"。我们可以手动指定底层容器（默认是 vector），但不能直接访问底层容器的元素，只能通过其提供的接口进行操作，例如 push、pop、top 等。

另一方面，priority_queue 默认是大顶堆，如果需要实现小顶堆，可以使用 greater<T> 作为比较器，例如：

priority_queue<int, vector<int>, greater<int>> minHeap;

STL 算法¶

至于 STL 已经实现的算法，常见的有：

排序和查找¶

std::sort - 排序元素¶

使用例如：

std::sort(v.begin(), v.end());

std::binary_search - 二分查找元素¶

使用例如：

std::binary_search(v.begin(), v.end(), value)

表示在已排序的容器 v 中查找 value 是否存在。

std::find - 查找元素¶

和二分查找相比不需要元素有序。使用例如：

std::find(v.begin(), v.end(), value)

表示在容器 v 中查找 value 第一次出现的位置。

修改操作¶

std::remove - 移除指定元素¶

使用例如：

std::remove(v.begin(), v.end(), value)

表示将容器 v 中所有不等于 value 的元素往前搬，返回新的逻辑结尾位置（并不实际删除元素）。搬运元素之后，容器 v 的大小并没有改变，仍然是原来的大小。新的逻辑结尾和旧的逻辑结尾之间的元素和原来这部分的元素是一样的，它们依然在容器中，因此该函数并不实际删除元素。

std::erase - 删除指定元素¶

使用例如：

v.erase(std::remove(v.begin(), v.end(), value), v.end())

表示删除容器 v 中所有等于 value 的元素（配合 std::remove 使用）。

std::insert - 插入元素¶

使用例如：

v.insert(position, value)

表示在容器 v 的指定位置 position 插入 value。

std::reverse - 反转元素顺序¶

使用例如：

std::reverse(v.begin(), v.end())

表示反转容器 v 中元素的顺序。

std::unique - 去除重复元素¶

使用例如：

v.erase(std::unique(v.begin(), v.end()), v.end())

表示去除容器 v 中相邻的重复元素（通常需要先排序）。然而我们通常会使用 std::set 或 std::unordered_set 来实现去重，而不是用这个。

统计和计算¶

std::count - 统计元素出现的次数¶

使用例如：

std::count(v.begin(), v.end(), value)

表示统计容器 v 中 value 出现的次数。

std::accumulate - 计算元素的累加和¶

使用例如：

std::accumulate(v.begin(), v.end(), init)

表示计算容器 v 中所有元素的累加和，初始值为 init。

查找最值¶

std::max_element - 找到最大元素¶

使用例如：

std::max_element(v.begin(), v.end())

表示返回容器 v 中最大元素的迭代器。

std::min_element - 找到最小元素¶

使用例如：

std::min_element(v.begin(), v.end())

表示返回容器 v 中最小元素的迭代器。

高级操作¶

std::nth_element - 找到第 n 小的元素¶

使用例如：

std::nth_element(v.begin(), v.begin() + n, v.end())

表示重新排列容器 v，使得第 \(n\) 小的元素位于第 \(n\) 个位置。

std::lower_bound - 找到第一个不小于给定值的元素¶

使用例如：

std::lower_bound(v.begin(), v.end(), value)

表示在已排序的容器 v 中找到第一个不小于 value 的元素的迭代器。

std::upper_bound - 找到第一个大于给定值的元素¶

使用例如：

std::upper_bound(v.begin(), v.end(), value)

表示在已排序的容器 v 中找到第一个大于 value 的元素的迭代器。

std::for_each - 对每个元素执行操作¶

使用例如：

std::for_each(v.begin(), v.end(), func)

表示对容器 v 中的每个元素执行函数 func。然而我们通常使用范围 for 循环来实现这个功能：

for (auto &item : v) {
    // function body
}

使用 STL 的注意事项¶

重要提示

在你使用 STL 之前，请务必确保你确实理解这两个名词，并能够用自己的语言解释出来：指针、迭代器。

不理解指针，就无法理解迭代器
不理解迭代器，就等于你不理解 STL 容器和算法的本质，你只能把它们当作黑盒子来使用，这样很容易出错
如果你确实是这种人，那请务必不要使用 STL

使用建议¶

我个人非常建议能够理解 STL 的同学们在考试的时候多使用 STL。它不仅能够大大地简化代码，代码的执行效率往往也比手写的代码更高。

对于大一的学生而言，如果你使用了 STL 但是考试的时候出现了 WA、TLE、MLE 等问题，请重新审视你算法的正确性与高效性，并检查你的代码是否正确地表达了你的意思；如果你确信你的算法是正确且高效的但是还是出现 TLE 或 MLE，则说明该题目并非你能够解决的，建议跳过，先做后面的题目。

例题 2.1：迭代器陷阱¶

题目

给定一个长度为 \(N\) 的整数序列，计算去掉所有最大值后剩余元素的和。

输入：一个整数 \(N\)，表示序列的长度；接下来 \(N\) 个整数，表示序列的元素。

输出：一个整数，表示去掉所有最大值后剩余元素的和。

小明写了这样一段代码，但是 WA 了。请指出下列代码的 bug，并使用两种办法修改 bug。

已知：出现错误的输入是 2 2 2，输出是 2。而正确答案是 0。

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N = 0;
    int sum = 0;
    cin >> N;
    vector<int> v;
    for (int i = 0; i < N; i++) {
        int j;
        cin >> j;
        v.push_back(j);
    }
    auto imax = max_element(v.begin(), v.end());
    for (int i = 0; i < N; i++) {
        if (v[i] == *imax) {
            v[i] = 0;
        }
        sum = sum + v[i];
    }
    cout << sum << endl;
    return 0;
}

解答¶

为了解决上述问题，我们首先应该问自己一个问题：迭代器到底是什么？只要理解了这个问题，你就找到了 bug 所在。

仔细观察下列代码：

auto imax = max_element(v.begin(), v.end());
for (int i = 0; i < N; i++) {
    if (v[i] == *imax) {
        v[i] = 0;
    }
    sum = sum + v[i];
}

上述代码中，imax 是一个迭代器，指向最大值的那个元素，看起来小明也知道。在循环中，v[i] == *imax 这个判断一开始确实是正确的；但是，一旦你把 v[i] = 0，*imax 的值也变成了 0（因为 imax 仍然指向那个位置），进而导致后面所有等于原最大值的元素，都不再等于 *imax（现在是 0），所以没有被清零。

最终这个问题就变成，只有一个最大值被清零，其余最大值被当成"非最大值"加进了 sum，导致结果错误。

问题根源

看起来小明犯这个错误的原因大概是他并不知道迭代器是什么东西。

因此，想要改正这个 bug，我们有以下两种方法：

方法一：避免修改迭代器指向的值
方法二：避免使用迭代器

方法一：避免修改迭代器指向的值¶

auto imax = max_element(v.begin(), v.end());
for (int i = 0; i < N; i++) {
    if (v[i] == *imax) {
        continue; // 直接跳过，不修改 v[i]
    }
    sum = sum + v[i];
}

方法二：避免使用迭代器¶

int imax = *max_element(v.begin(), v.end()); // 直接拷贝最大值
for (int i = 0; i < N; i++) {
    if (v[i] == imax) {
        v[i] = 0;
    }
    sum = sum + v[i];
}

总结¶

经验教训

觉得眼熟？上述问题实际上就是在课程作业中出现的错误。上述代码用了 auto 等 C++11 的特性，说明小明看起来已经学过 C++11 了；从 v[i] == *imax 能看出，他也知道 imax 是个迭代器，这说明他并不是遇事不决就拿 auto 往上乱糊的人；然而，因为对迭代器的理解不够深入，最终还是导致了这个 bug。

因此，我们在用 STL 之前，一定要确保自己真真切切理解了迭代器的含义。

总结¶

算法的复杂度分析是编写高效程序的基础，而 C++ STL 提供了丰富的数据结构和算法实现，可以大大提高开发效率。但是，使用 STL 需要对指针和迭代器有深入的理解，否则容易出现难以察觉的 bug。

建议在学习算法时：

理解算法的时间和空间复杂度
熟练掌握 STL 容器和算法的使用
深入理解指针和迭代器的概念
多做练习，在实践中加深理解

通过不断练习和思考，你将能够编写出既正确又高效的程序。