首页 > 编程笔记 > C++笔记 阅读：1

时间复杂度和空间复杂度详解（新手必看）

在讨论算法设计时，必须澄清一个常见的误解，所谓的“复杂度”，并非指算法的复杂性或理解上的难度，而是指衡量算法运行效率的标准。

在深入学习算法设计之前，首要任务是掌握如何准确分析算法的复杂度。这种复杂度与算法的直观复杂性或理解难度无关，而是提供了一个理论模型，用于评估算法本身的计算需求规模，即其效率。

通常，较低的复杂度意味着算法更加高效；相反，较高的复杂度则表明算法的效率较低。在某些情况下，我们可能会采取“空间换时间”的策略，即通过增加空间复杂度为代价，显著降低时间复杂度，从而提升整体性能。

复杂度分为时间复杂度和空间复杂度两大类。在大多数情况下，我们主要关注最坏情况下的复杂度，并用O来表示，读作“大欧”。

时间复杂度分析

时间复杂度是衡量算法效率的关键指标，它不仅体现了算法性能的优劣，而且通常是算法题目考察的重点。

为了深入理解时间复杂度，我们首先需要明确“基本操作”的概念。基本操作指的是算法中的单一计算步骤，例如基本的算术运算（加、减、乘、除）、位运算、变量赋值以及条件判断等。

在分析算法时，我们通常将这些操作视为单一的计算单元，尽管在底层机器指令层面，它们所需的具体操作步骤可能有所不同。在时间复杂度的分析中，这些“基本操作”被认为具有常数时间，即 O(1)。

以下是一些示例代码，演示了 O(1) 时间复杂度的基本操作： 
// 头文件、变量声明等部分已省略
a += 3;           // 简单的算术运算
b += a;           // 简单的算术运算
a = b;            // 变量赋值
a *= -1;          // 简单的算术运算
b >>= 7;          // 位运算
if(a == b){}      // 条件判断
a ++;             // 简单的算术运算
时间复杂度通常源于算法中的“循环”和“递归”结构，因此，在分析时间复杂度时，我们应重点关注这些结构。

在评估时间复杂度时，我们主要关注的是操作的数量级，即运算的规模和增长速度，而非精确的操作次数。例如：
在某些情况下，时间复杂度不易精确分析，此时我们通常会估计一个上界，即确保实际计算规模不会超过这个估计值。然而，是否能进一步缩减这个上界则不一定。

除非特别指明，提到的“复杂度”一般指“时间复杂度”。这是因为大多数算法题目的挑战通常在于时间效率，而非空间效率，而且很多算法优化的本质是“用空间换时间”。

【实例 1】分析以下程序的时间复杂度。 
// 输入 a 数组
int ans = 0;
for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= m; ++j)
        ans = max(ans, a[i][j]);
cout << ans << '\n';
该代码段包含一个双重循环结构。外层循环对 i 进行迭代，共执行 n 次；内层循环对 j 进行迭代，共执行 m 次（实际上是 m-i 次，但是我们认为这是 m 级别的，所以在计算复杂度时是 m）。因此，整个程序的时间复杂度为两层循环的乘积，即 O(nm)。

【实例 2】分析以下程序的时间复杂度。 
int a[N], n;
bitset<N> vis;

void dfs(int dep) {
    if (dep == n + 1) {               // 递归到第 n+1 层，说明已经得到 1~n 的一个排列
        for (int i = 1; i <= n; ++i)
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            vis[i] = true;
            a[dep] = i;
            dfs(dep + 1);
            vis[i] = false;           // 回溯
        }
    }
}
这段代码实现了深度优先搜索。在最坏的情况下，即没有剪枝的情况下，这段代码会枚举所有可能的排列，共有 n! 种。对于每一种排列方案，内部的循环需要 O(n)时间来遍历和输出。因此，总的时间复杂度为 O(n!×n)。即使加入了剪枝策略，由于剪枝效果难以量化，我们通常认为时间复杂度保持不变，以最坏情况（即不进行剪枝的情况）作为时间复杂度的上界。

空间复杂度分析

空间复杂度虽然不是主要关注点，但了解其计算方法依然重要。

在计算机中，内存的基本单位是比特（Bit），它可以是 0 或 1。为了便于处理，8 个比特组成一个字节（Byte）。计算机操作通常以字（Word）为单位，不同的计算机架构会将字节组合成不同大小的字，常见的是 2 字节或 4 字节。

在 C++ 中，1Byte=8Bit，我们通常称 Byte 为大 B，Bit 为小 b。常见单位还有 1MB=1024KB，1KB=1024B。

在解决问题时，空间复杂度通常指数组大小或递归深度。不同数据类型及其占用的字节数如下表所示。

表：不同数据类型及其占用的字节数
数据类型 占用的字节数
int 4
long long 8
char 1
float 4
double 8
long double 8~16
bool 1

需要注意的是，unsigned 类型的数据和没用 unsigned 修饰的数据，它们占用的字节数是一样的，例如 unsigned int 和 int 都占用 4 字节。

现在，我们可以大致估算在给定的空间限制下可以声明的数组大小。假设题目提供了 128MB 的空间，我们要计算可以声明多大的 int 类型数组。由于每个 int 通常占用 4 字节（即 4Byte），那么需要满足 4x<128×10^6，解得 x 的最大值约为 3×10^7。这意味着我们可以声明一个包含大约 3000 万个元素的 int 数组。

通常情况下，题目不会对空间限制过于严格，除非使用的内存非常巨大，如声明一个包含 10 亿个元素的数组，或者几个包含一亿个元素的数组。

至于递归的最大深度，这通常取决于运行环境的栈大小。一般在 Windows 上是 1MB，而在 Linux 上可能是 8MB。在递归过程中，每一层都需要一定的空间来保存参数和局部变量，因此如果有 n 层递归，且每层递归开辟的空间为常数大小，则总的空间复杂度为 O(n)。

如果栈空间不足，则可能会导致“栈溢出”。在线编程环境通常会增加栈空间来避免这种情况，但在本地运行时可能更容易遇到栈溢出问题。一般建议递归层数不要超过 5×10^5，若递归过深且在线评测系统对栈空间限制较为严格，则可能会遇到超出内存限制（Memory Limit Exceeded，MLE）错误或运行时错误。

相关文章