数据结构和算法：算法复杂度

我们开始了算法复杂度的学习，本期教程我们学习后半段。

复杂度只考虑操作数目的一个数量级（忽略了其他的组分），这是一种近似。

为了表示这种近似，我们使用一个特定的符号，就是著名的 大 O 符号。

大 O 符号（Big O notation），又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项。在计算机科学中，它在分析算法复杂度的方面非常有用。大 O 符号是由德国数论学家 保罗·巴赫曼（Paul Bachmann）在其 1892 年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家 艾德蒙·朗道（Edmund Landau）的著作中才推广的，因此它有时又称为 朗道符号（Landau Notation）。代表“order of …”（…阶）的大 O，最初是一个大写希腊字母“Ο”（Omicron），现今用的是大写拉丁字母“O”。

例如，小鸭子们去度假这个故事里，农夫 Oscar 的第一种算法有 N2 个操作，我们就说此算法的复杂度是 O(N2)。类似地，第二种更快的算法的复杂度是 O(N)。

大 O 符号有点像一个大圆形的袋子，可以把不同的操作数目整合在一起，使之具有一个同样的数量级。

例如，如果有三个算法，它们的操作数目分别为 N，5N + 7 和 N / 4，我们就都用 O(N) （读作 “N 的 大 O”。当然了，读法其实不是那么固定）来表示这三个算法的复杂度。

类似地，如果一个算法的操作数是（2 * N2 + 5 * N + 7），那么它的复杂度是 O(N2)：我们忽略了 5 * N 和 7 这两项，因为它们与 2N2 相比数量级较小。随着 N 的增大，这两项的增长速率比 2N2 要慢，因此我们保留 2N2 即可，又因为常数乘法因子（这里是 2）不予考虑，因此记为 O(N2)。

我们说 f(N) 表示“N 的函数”（例如， f(N) = 2 * N2 + 5 * N + 7) ），那么 O(f(N)) 表示的是“大约有 f(N) 个操作的算法的复杂度”，这里的“大约”是非常关键的。

时间复杂度和空间复杂度

下面我们来学习算法中常听到的“时间复杂度”和“空间复杂度”。

为什么我竟然想到了漫威里面的大反派灭霸的无限手套呢？上面有时间宝石和空间宝石这两颗无限宝石。一定是因为我看了《复仇者联盟3：无限战争》和《复仇者联盟4：终局之战》的关系…