时间和空间复杂度

时间复杂度

时间复杂度 是一个函数，也是一个算法执行基本运算的次数，用来衡量一个算法在时间上的效率。

一般而言，我们用大 O 符号来表示时间复杂度。在书写时，省略常数，保留最高阶项。例如在数据规模为 \(n\) 的情况，有一个算法的执行基本运算的次数为 \(n + \log n\)，则该算法的时间复杂度一般写作 \(O(n)\)。

计算

先看一个简单的例子：

例 1

int solve(int n){
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cnt++;
    return cnt;
}

执行一次例 1 的算法会有

\[ \sum^n_{i=1} i \]

次基本运算，由等差数列求和公式，他的结果为 \(\dfrac{n(n + 1)}{2}\)，所以该算法时间复杂度为 \(O(n^2)\)。

例 2

const int N = 1005;
vector<int> g[N];
int a[N], dp[N][N], tmp[N];
int n, m; // 节点数 n，容量 m，每个节点的重量为 1
void dfs(int u){
    for(int i = 1; i <= m; i++)
        dp[u][i] = a[u];
    for(auto v : g[u]){
        dfs(v);
        for(int i = 1; i <= m; i++)
            tmp[i] = dp[u][i];
        for(int i = 1; i <= m; i++)
            for(int j = 0; j < i; j++)
                dp[u][i] = max(dp[u][i], tmp[i - j] + dp[v][j]);
    }
}

例 2 实际上是一个树形背包的代码，显然，它的时间复杂度为 \(O(nm^2)\)。但是，因为在以 \(u\) 为根的子树上做树形背包容量最大为这棵子树的节点数，所以我们可以进行优化。那么优化后的时间复杂度为多少呢？其实是 \(O(nm)\)¹。

证明的感性理解

两棵子树合并时，只会选取两棵子树各自的所有点对进行合并，而每对点只会在 LCA 处进行合并，所以整棵树一共会合并 \(n^2\) 次。

因为 \(m \le n\)，所以时间复杂度的上限是 \(O(n^2)\)（当 \(m = n\) 时）。

所以，在计算时间复杂度时，要仔细计算，而不能“一眼”得答案。

空间复杂度

空间复杂度 是一个函数，也是一个算法 额外 使用单位大小空间的次数，用来衡量一个算法在空间上的效率。

我们一般也用大 O 符号表示空间复杂度。

信息

本节我们讨论的是 空间复杂度，而不是空间的使用是否合理。对 C/C++ 而言，开不开 long long 不是 我们讨论的话题。

我们来计算两个排序算法的空间复杂度：快速排序和普通的归并排序。

快速排序只额外使用了几个变量，所以它的空间复杂度是 \(O(1)\)。

归并排序额外使用一个长度为 \(n\) 的数组来存放两个子区间的合并结果，所以它的空间复杂度是 \(O(n)\)。

引言

时间换空间，空间换时间。

我们在解决算法问题时，要仔细判断所写算法的时间和空间复杂度，才能更好的深刻理解代码和代码所带来的知识。

---

1. dengchengyu，树上背包的复杂度证明 ↩