算法入门第一课

发表于 更新于
本文字数： 4.1k 阅读时长 ≈ 15 分钟

Introduction Lec 01 / 2024.11.11

阅读前须知

本文是算法入门第一课，不是 0 基础第一课，如果你是武科大想要学习算法的新生，请先保证自己有一定的代码基础（如刷够 140 道 wustoj 上的入门题，并且初步了解 c 语言和 c++的区别…..

0x01 动手实现一个可变长度数组

前置要求：对 C 语言的指针和结构体有基本了解

在 C 语言学习初期我们可能会有写动态长度的数组的想法，就像下面这样

1
2
int n;  scanf("%d", &n);
int arr[n];

这个东西叫 VLA，Variable Length Array 可变长度数组。C11 标准规定 VLA 是一个可选项，不强制编译器实现 （虽然代码在你当前的编译器编过了，但换一个编译器可能就编挂了）。尽管 GCC 和 Clang 都支持 VLA，但是在 C++ 标准中没有规定编译器一定要实现这玩意儿。 此外，虽然对于现代编译器 VLA 不会给性能和可移植性造成很大的负面影响，但是编码实践中我们通常不使用 VLA。

那么现在我们来自己尝试写一个可变长度的数组。

我们跳过 C 的 malloc 函数，这里直接介绍 C++ 的 new 和 delete

new 用于申请内存，delete 用于释放 new 申请的内存。内存申请了要释放（回收），不然会漏内存。

内存泄漏会导致程序占用越来越多的内存，最终可能耗尽系统资源，导致系统性能下降或程序崩溃。

1
2
int* arr = new int[n];  // 申请内存，new[] 可以接受一个运行时确定的变量
delete[] arr;           // 释放内存

封装

我们用结构体封一下这个行为。

注意 C++ 的结构体是可以在里边写函数的，但 C 结构体不行。

这是一个很重要的特性，C++ 结构体允许包含数据（成员）和函数（方法），使一组数据和它对应的行为能够被封装在一起，对外隐藏细节只暴露接口，使代码更加模块化易于维护。

封装是面向对象编程的核心理念之一，还有两个是继承和多态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct VLArray {  // Variable Length Array
    int len;
    int* data = nullptr;

    void alloc(int n) {         // 申请内存
        int* newData = new int[n];
        if(data != nullptr) {   // 扩容或缩容，先拷贝已有数据
            for(int i = 0; i < (n < len ? n : len); i++)
                newData[i] = data[i];
            free();             // 释放已持有的内存
        }
        len = n;
        data = newData;         // data指向新申请的内存
    }

    // 类和结构体里面函数不用先定义后调用，留意一下
    void free() {  // 释放内存
        delete[] data;
        data = nullptr;
    }
};

// Usage 用法
VLArray arr;
arr.alloc(100);         // 申请内存
for(int i = 0; i < 100; i++)
    arr.data[i] = i;    // 0, 1, 2, ..., 99
arr.alloc(10);          // 0, 1, 2, ..., 9
arr.free();             // 记得释放内存，不然会有内存泄漏的问题

看起来还行，我们已经实现了一个可变长度的数组，能伸缩的那种。但是有个很不好的地方：每次用之前都要手动 调用 alloc ，用完了也不能忘记手动 free 。能不能让它自动做这件事？

构造和析构

当然可以。这里需要介绍面向对象经常提到的构造函数和析构函数。构造函数在一个对象被创建时自动调用，析构函数在一个对象被销毁时自动调用，我们只需要把 alloc 和 free 写到构造函数和析构函数里就行。C++ 构造函数就是结构体（或者类）内的同名函数，析构函数是结构体（类）名前面加一个 ~ 。

修改后的代码如下

1
2
3
4
5
6
7
8
9
10
11
struct VLArray {  // Variable Length Array
    VLArray(int len) { alloc(len); }    // 构造函数
    ~VLArray() { free(); }              // 析构函数
    // ...省略同上
};

// Usage 用法
VLArray arr(100);       // 这里隐式调用了构造函数
for(int i = 0; i < 100; i++)
    arr.data[i] = i;    // 0, 1, 2, ..., 99
arr.alloc(10);          // 0, 1, 2, ..., 9

建议课后尝试在 Linux 下使用 Valgrind 看看不手动释放且没有析构函数释放的内存泄漏。

这个动态数组可以做的更好吗？显然，比如使用 arr[] 直接访问里面的元素而不是用 arr.data[] （用运算符重载可以实现，自行了解），比如这个动态数组只支持 int 类型，如果需要其他类型我们需要自己重新写一遍。

关于它仅支持 int 类型这个问题，在 C++ 里通常会使用模板（一种泛型编程的实现方式）来解决。下一节我们会接触到。

泛型编程（Generic Programming）是一种编程范式，它允许你写一份代码用来处理多种不同类型的数据，避免大量无意义的重复劳动。泛型编程的核心思想是将类型视作参数来实现代码的复用和灵活性。

0x02 初识 STL

C++ STL（Standard Template Library，标准模板库）是 C++ 标准库的一部分，通过泛型编程的理念实现了一些常用算法和数据结构。

std::vector

刚才我们讲了如何自己实现一个简易的可变长度数组，本质上可以算作是 STL 中 std::vector 的一个子集。

std::vector 是一个动态数组容器，能够自动管理内存，按需扩容和缩容。

使用 std::vector 需要 #include <vector>

一些常用操作如下

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> v;     // 声明一个vector，里边装的是int。容量为 0
std::vector<int> v(10); // 同上，但容量为 10， 所有元素初始值为 0
std::vector<int> v = { 1, 1, 4, 5, 1, 4 }; // 容量为 6，有初始值

v.push_back(1);     // 在数组末尾添加一个 1
v.pop_back();       // 删除尾部元素
int sz = v.size();  // 获取当前元素数量
if(v.empty())       // 判空

// 遍历输出每个元素
for(int i = 0 ; i < v.size() ; i++) std::cout << v[i] << " ";
// C++ 11 引入的 Range-based for loop （基于范围的 for 循环）
for(int& x : v) std::cout << x << " ";

需要注意到最后一行 for(int& x : v) 这个写法。这里的 int& 表示 x 是 v 中元素的引用（别名），对 x 进行赋值操作会使 v 中的元素被更改。如果是 for(int x : v) 那么 x 就是 v 中元素的拷贝了，改变 x 不会影响到 v 中的元素。

std::map

这里再介绍一个 std::map 。它是一个关联容器，存储键值对（key-value pairs），或者说存储多对映射关系。

使用 std::map 需要 #include <map> ，下面简单介绍一下用法

1
2
3
std::map<char, int> mp;         // 建立一个 char 到 int 的映射
for(char ch = 'A' ; ch <= 'Z' ; ch++)   mp[ch] = int(ch);
std::cout << mp['A'] << "\n";   // 输出 65

需要注意的是，std::map 的键（也就是第一个类型参数，上面代码 std::map<char, int> 的 char）是不允许重复的，值可以重复。std::map 底层依赖红黑树实现，插入、查找、删除的复杂度都是优秀的 O(\log N) （关于复杂度后文再讲）。

队列 queue，双端队列 deque，优先队列 priority_queue，集合 set，链表 link 也是常用的 STL 容器，建议课后自行了解。

std::sort

STL 也实现了一些常用算法，这里讲个排序 std::sort。用法很简单

1
2
3
4
5
6
7
8
9
10
int arr[6] = { 1, 1, 4, 5, 1, 4 };
std::sort(arr, arr + 6);    // 第一个参数表示待排序的首元素，第二个参数表示待排序的末位元素的后一位
std::vector<int> v = { 1, 1, 4, 5, 1, 4 };
std::sort(v.begin(), v.end());  // 这里 v.end() 也表示 v 的最后一个元素的后一位

// std::sort 默认是从小到大排序，如果需要从大到小排序需要自己写一个排序规则
bool cmp(int a, int b) {
    return a > b;
}
std::sort(arr, arr + 6, cmp);   // 这样就能实现从大到小排序

std::sort 的实现方式类似于 Introsort 内省排序，使用快排但限制递归层数，递归到小区间后根据区间内元素乱序程度采用堆排序或插入排序，保证最坏情况下能够做到 O(N \log N) 。

下面我们简单介绍一下时间复杂度。

0x03 一种快速估测时间复杂度的方法

在设计算法时，时间复杂度和空间复杂度是衡量一个算法效率的重要标准。

时间复杂度指的是一个算法所用时间随着数据规模（比如输入数字的多少）增长的趋势。随着数据规模增长，算法用时增长越缓慢，那么这个算法的时间复杂度就越优秀。

同一个算法在不同的计算机上运行需要的时间会有一定的差别，并且实际运行速度难以在理论上进行计算，实际去测量又比较麻烦，所以我们通常考虑的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。

在普通的计算机上，加减乘除、访问变量（基本数据类型的变量，下同）、给变量赋值等都可以看作基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标。 （摘自 OI-WIKI）

列举几个常见复杂度 $$O(1) \ O(\log N) \ O(\sqrt N) \ O(N) \ O(N \log N) \ O(n^2) \ O(2^n) \ O(N!)$$（按照随数据规模增长速度由慢到快排序）

对时间复杂度进行快速估算时，可以关注算法中循环和递归的嵌套层数。通常，单层循环的时间复杂度为 $$O(N)$$，双层嵌套循环为 $$O(N^2)$$，以此类推。

对于一段代码，可能有多个循环体、递归调用，把它们的复杂度相加可以得到一个多项式。通常我们只保留最高阶项并忽略常数系数。

以下面这段代码为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long InnerProductSum(int arr[], int n) {
    long long ans = 0;
    for(int i = 0 ; i < n ; i++)
        for(int j = i + 1 ; j < n ; j++)
            ans += arr[i] * arr[j];
    return ans;
}

int arr1[N], arr2[N];                       // 1
for(int i = 0 ; i < N ; i++)    scanf("%d", &arr1[i]);  // N
for(int i = 0 ; i < N ; i++)    scanf("%d", &arr2[i]);  // N
long long sum1 = InnerProductSum(arr1, N);  // N^2
long long sum2 = InnerProductSum(arr2, N);  // N^2
printf("%lld", sum1 % sum2);                // 1

不妨认为基本操作数是

$$
f(n) = 2 \times n^2 + 2 \times n + 2
$$

在估算时我们忽略常数并保留最高阶项，认为其时间复杂度为 O(N^2)

然后你把 N 代进去算一下 N^2 不超过 2e8 一般就能在 1s 内跑过

0x04 卡常，关流同步和标准 IO 重定向

前置要求：会用 C++ std::cin 和 std::cout

卡常

前文提到，对于一个算法计算最小操作数可以得到一个多项式，其中每一项都会有一个常数系数。通常我们不考虑常数对时间复杂度的影响，但是不排除少数情况下常数过大导致我们的程序无法在限定时间内通过所有测试用例——你的算法因为常数被卡掉了。

我们认为，一道合理的题目应当考察时间复杂度是否正确，但不应在主观上故意用微小的常数优化区分参赛者的表现。

通常在比赛中，C / C++ 语言的编译选项会开启 O2 优化。编译器会进行函数内联、循环展开等操作以优化代码性能。现代编译器具备完善的机制处理各种情况，因此不必过分考虑常数优化问题。 高中生 OI 选手可能会手写一些东西避免使用 STL 因为 NOIP 不开 O2 而且 STL 常数大

关闭流同步提升 IO 性能

有的题目可能会提示输入数据量较大需要使用较快的数据读入方式，这里介绍 C++ 关闭 IO 流同步加快输入输出速度的方法和原理。默认情况下 C++ 的 std::cin 和 std::cout 与 C 标准库的输入输出函数保持同步（但会有额外性能开销）。为提高输入输出速度，可以关闭同步并解除绑定：

1
std::ios::sync_with_stdio(false);   // 关闭 C++ 与 C 标准库的输入输出流同步

有的题目可能输出行数较多，用 std::cout << std::endl 进行换行输出会导致超时，原因是 std::endl 包含了 std::cout << "\n" 和 std::cout.flush() 两个操作。其中 std::cout.flush() 会刷新输出缓冲区，频繁刷新缓冲区会消耗大量的时间，因此建议手动输出换行符。另外将 std::cin 与 std::cout 解绑也能够减少输出缓冲区的刷新。

1
2
std::cin.tie(nullptr);      // std::cin 时不再刷新 std::cout 缓冲区
std::cout << ans << "\n";   // 手动输出换行符而不是 std::endl

标准 IO 重定向

目前绝大多数题目都使用标准 IO，极少数题目可能会使用文件输入。另外，自己写题目的时候可以用文件输入避免每次都手动输入样例的麻烦。

笔者舍近求远， 这里先介绍一下操作系统的文件描述符。文件描述符 File Descriptor 可以理解为对当前进程打开的文件的编号，从 0 开始。通常 0，1，2 分别对应了标准输入、输出和错误信息，此时如果再自己开一个文件，那么它的描述符就是 3。

通常我们写算法题的简单程序，在本地运行，文件描述符 0，1，2 对应的都是控制台。

我们可以使用 freopen 函数将输入从控制台重定向到文件（输出不受影响）

1
freopen("./in.txt", "r", stdin);    // 以只读方式打开 in.txt 作为标准输入

同理，将输出重定向到文件也是可行的。 但是一定一定一定要注意如果写了死循环里边还有输出可能会在 10s 内写出一个 3GiB 的巨大 txt 文件然后把电脑卡住

1
freopen("./out.txt", "w", stdout);

使用条件编译实现仅本地文件读入

本地使用文件读入会有一个问题：OJ 上的题目没要求用文件读入，交上去读不到数据。这个时候就需要代码在本地和 OJ 上有不同的编译行为（本地编译执行 freopen ，但 OJ 上不执行）。实现方法是通过某个宏定义是否存在来判断。

在很多 OJ 上编译选项中都会包含一个 -DONLINE_JUDGE ，比如 WUST OJ 上的编译选项

1
/usr/bin/g++ -DONLINE_JUDGE -O2 -w -fmax-errors=3 -std=c++14 {src_path} -lm -o {exe_path}

这个选项的意思是定义一个宏 ONLINE_JUDGE （我们本地是没有这个宏的），这样我们就可以利用这个宏来区分是 OJ 还是本地环境。

1
2
3
4
5
#ifndef ONLINE_JUDGE    // 如果没定义 ONLINE_JUDGE，是本地
    freopen("./in.txt", "r", stdin);
#else                   // 定义了 ONLINE_JUDGE，是 OJ，关流加速
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
#endif

当然我们也可以在本地修改编译选项，自己添加一个比如 -DNOT_OJ

1
2
#ifdef NOT_OJ   // 如果定义了 NOT_OJ，是本地
// ...省略

这样本地可以使用文件输入，提交到 OJ 也能正常运行。

0x05 在命令行界面编译程序

命令行界面 Command Line Interface，简称 CLI

图形用户界面 Graphical User Interface，简称 GUI

集成开发环境 Intergrated Development Environment，简称 IDE

本节参考了 USTC Linux 101

现在假设我们有一份源码文件 main.c，内容如下：

1
2
3
4
5
6
7
// main.c
#include <stdio.h>

int main() {
  printf("Hello World!\n");
  return 0;
}

这是一个简单的 Hello World 程序。

要将它编译成二进制可执行文件，在 Windows 或 Mac OS X 这样带有 GUI 的系统上，可以使用 IDE 中的编译功能得到目标程序。这些带有图形界面的 IDE 的编译通常是封装了各种提供命令行接口的编译器。自然，我们也可以在 CLI 下手动去调用这些命令行接口进行编译。

GCC 和 Clang 是 Linux 下常用的编译器。 其中 GCC 由 GNU 组织维护，Clang 由 LLVM 组织维护的。

Windows 下 Visual Studio 默认使用微软的 MSVC 工具集，它的编译器是 cl.exe。

多文件的情况

使用构建工具

0x06 扯一嘴代码风格

\