第8.8章: 时间与空间复杂度

English

概述

时间复杂度和空间复杂度描述的是：随着输入规模的增长，算法的运行时间和内存占用如何增长。本章重点讲时间复杂度，同时也会解释为什么空间复杂度通常给出时间的下界。

你将学到：

0. 计算模型

当我们谈论时间复杂度时，谈的始终是某个特定抽象机器模型上算法的运行时间。最常见的模型是 RAM 模型（随机访问机）。

RAM 模型假设：

这些假设使得我们能用 Θ(n)、O(n ln n) 这样简洁的记号来描述算法。

1. 空间复杂度作为下界

空间复杂度衡量算法使用的内存量随输入规模 n 变化的函数关系；时间复杂度衡量它运行多久。

空间复杂度通常是时间复杂度的下界。如果一个算法使用了 S(n) 的空间，那么它至少要花 Ω(S(n)) 的时间去分配、初始化、读取或操作这块空间。

例子：

2. 三种基本记号

时间复杂度使用三种相互关联的记号：

我们要严格地使用它们：

3. 基本的 Θ 计算


Θ(3n^3) = Θ(n^3)
      

Θ(n^3 + 10000000000n^2) = Θ(n^3)

只有最高阶项起作用。

4. 简单循环的复杂度


for (::std::size_t i{}; i != n; ++i) {
    // constant-time work
}

Θ(n)


for (::std::size_t i{}; i != n; ++i)
    for (::std::size_t j{}; j != n; ++j)
        ;

Θ(n^2)

5. 线性时间算法

例子：


::std::size_t ones = ::std::ranges::count(v, 1);

Θ(n)

6. 二分查找：O(ln n)


auto it = ::std::ranges::lower_bound(v, value);

每次迭代把搜索空间减半 → O(ln n)。

7. 排序：O(n ln n)


::std::ranges::sort(v, {}, &Item::key);

C++ 标准只保证上界 → O(n ln n)。

8. 为什么投影的开销很重要


::std::ranges::sort(v, {}, &Item::key);
      

::std::ranges::sort(v, {}, [](Item const& x) {
    return expensive_computation(x);
});

昂贵的投影会主导运行时间。

9. 数值算法


::std::size_t total = ::std::transform_reduce(
    v.begin(), v.end(),
    ::std::size_t{},
    ::std::plus<>(),
    &Item::value
);

Θ(n)

10. 递归斐波那契：指数时间


::std::size_t fib(::std::size_t n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Θ(2^n)

11. NP 问题与困难的搜索空间

现实世界中的许多问题拥有指数规模的搜索空间，并且人们认为它们无法在指数时间内被精确求解。

12. 为什么围棋对计算机极其困难


200^200

围棋的博弈树是指数级的 → 穷举不可能。

13. 为什么 AlphaGo 能成功

AlphaGo 并没有精确地求解围棋，它使用了：

它用近似的方式找出好棋，而不是遍历整棵指数级的树。

14. 附录：第8.8.1章 —— 主定理

许多递归算法的时间复杂度可以用如下形式的递推式来描述： 


T(n) = a · T(n / b) + f(n)

附录将教你如何用主定理求解这类递推式，并给出归并排序和快速排序等例子。

你可以在这里阅读完整附录：

打开第8.8.1章: 主定理 →

要点

← 第8.7章: 数值算法 ↑ 主页 第8.9章: RAM 模型及其局限 →