算法复杂度 | Xingyu Yang

Definition时间复杂度

时间复杂度描述了算法运行时间如何随输入规模的增长而增长。它可以根据不同目的用不同的记号表示，为算法提供上界、下界或平均性能。

数学上，时间复杂度可以定义为一个函数 $T: A \times n \to F(n)$ ，其中 $A$ 是所有算法的集合¹， $n$ 是输入大小， $F(n)$ 是以 $n$ 为输入的可能函数的集合，通常 $F(n) = \{1, n^k, k^n, \log_n (x), \ln(x), n \log_n (x), n!\}$ ，其中 $k \in \mathbb{N}$ ， $n$ 是算法的输入大小。当算法 $a \in A$ 的输入大小为 $n$ 时，其时间复杂度为 $T(a) = f(n)$ ，其中 $f(n) \in F(n)$ 。

这可能有点抽象，但这并不是我们在实践中常用的通用时间复杂度定义。在实际应用中，我们为时间复杂度增加了另一层抽象，从不同方面对算法进行基准测试，例如最坏情况、最好情况和平均情况时间复杂度。我们将在以下章节中讨论这些。

让我们考虑线性搜索的例子，这是一种在数组中搜索目标元素的简单算法。线性搜索算法的伪代码如下所示。我们简单地指定一个目标元素，并从数组的开头到结尾遍历数组，将每个元素与目标进行比较。如果找到目标，我们返回元素的索引；否则，我们返回 -1 以表示目标不在数组中。现在我们将分析线性搜索算法的时间复杂度。

算法 1 线性搜索

Require: 数组 $A$ ，目标值 $x$

Ensure: $x$ 的索引，若不存在则返回 $-1$

1:for $i \gets 0$ to $n - 1$ do

2:if $A[i] = x$ then

3:return $i$ // 在索引 $i$ 处找到目标值

4:end if

5:end for

6:return $-1$ // 未找到目标值

Example线性搜索输入规模

为了弄清楚线性搜索的时间复杂度，我们首先需要确定哪个元数据决定了算法的输入大小。显然，在这个算法中，我们只线性地遍历数组，这意味着算法的输入大小是数组的长度。因此，我们将输入大小表示为 $n$ ，线性搜索算法的时间复杂度是 $n$ ，其中 $n$ 是数组的长度。

现在我们看一个稍微不同的例子，它也与线性搜索有关。

def linear_search(arr: list[int], target: int) -> int:
    """
    用于在数组中查找目标元素的线性搜索算法。
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 目标在索引 i 处找到
    return -1  # 在数组中未找到目标

target = 5
target_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(linear_search(target_list, target))  # 输出: 4

Problem固定输入上的线性搜索

在此调用中，线性搜索算法的时间复杂度是多少？

答案是常数函数， $f(n)=1$ ，而不是线性函数， $f(n)=n$ 。原因是这里的数组长度是固定的，而不是一个变量。因此，此调用中线性搜索算法的时间复杂度是常数。对于一个长度为 100,000 的给定数组也是如此，因为数组的长度是固定的。这个例子可能会让一些人感到困惑，但别担心，我们将在以下章节中使用线性搜索作为示例，明确讨论最坏情况、最好情况和平均情况时间复杂度。

最坏情况时间复杂度 (大O记号)

正如我们所说，当我们评估算法的时间复杂度时，我们通常会考虑某些因素，最常见的一个因素是算法的性能有多差。这被称为最坏情况时间复杂度，它为算法的运行时间提供了一个上界。我们使用大O记号来表示最坏情况时间复杂度，例如 $O(n)$ , $O(n^2)$ , $O(\log n)$ 等。

Definition大O记号

假设算法的输入是可变大小 $n$ ，我们使用大O记号来分析当 $n \to \infty$ 时时间复杂度的渐近上界。我们断言，在最坏情况下，输入大小为 $n$ 的算法的时间复杂度 $T(n)$ 满足 $T(n) = O(g(n))$ ，如果存在常数 $c > 0$ 和 $r \in \mathbb{N}$ 使得对于所有 $n > r$ ， $0 \le f(n) \le c \cdot g(n)$ 。其中 $f(n)$ 是算法的精确时间复杂度， $g(n)$ 是时间复杂度的上界。

用自然语言来说，如果存在一个常数 $c$ 和一个正整数 $r$ ，使得对于所有大于 $r$ 的输入大小 $n$ ，算法的时间复杂度上界为 $c \cdot g(n)$ ，那么我们说算法的时间复杂度是 $O(g(n))$ 。

尽管如此，我们仍然以线性搜索为例，尽管它很特殊，因为它的实际最坏情况时间复杂度与大O记号完全相同，但在其他算法中情况并非总是如此。我们将在未来看到更多例子。

Example线性搜索最坏情况复杂度

对于线性搜索算法，最坏情况时间复杂度是 $O(n)$ ，其中 $n$ 是数组的长度。这是因为，我们有 $f(n) = n$ ，和 $g(n) = n$ ，当 $c=1$ 时，对于所有 $n \in \mathbb{N}$ ， $0 \le f(n) \le 1 \cdot g(n)$ 。

在这种情况下，我们了解到的关于最坏情况时间复杂度的信息比我们需要的多，因为我们只需要对于所有 $n > r$ ， $0 \le f(n) \le c \cdot g(n)$ ，然而我们有对于所有 $n \in \mathbb{N}$ ， $0 \le f(n) \le c \cdot g(n)$ 。这是由线性搜索算法的性质决定的，它非常简单直接。然而，同样，这并非总是如此，我们将在未来看到更多例子。

最好情况时间复杂度 (大Omega记号)

与最坏情况时间复杂度相反，我们有最好情况时间复杂度，它为算法的运行时间提供了一个下界。我们使用大Omega记号来表示最好情况时间复杂度，例如 $\Omega(n)$ , $\Omega(n^2)$ , $\Omega(\log n)$ 等。

Definition大Omega记号

假设算法的输入是可变大小 $n$ ，我们使用大Omega记号来分析当 $n \to \infty$ 时时间复杂度的渐近下界。我们断言，在最好情况下，输入大小为 $n$ 的算法的时间复杂度 $T(n)$ 满足 $T(n) = \Omega(g(n))$ ，如果存在常数 $c > 0$ 和 $r \in \mathbb{N}$ 使得对于所有 $n > r$ ， $f(n) \ge c \cdot g(n)$ 。其中 $f(n)$ 是算法的精确时间复杂度， $g(n)$ 是时间复杂度的下界。

用自然语言来说，如果存在一个常数 $c$ 和一个正整数 $r$ ，使得对于所有大于 $r$ 的输入大小 $n$ ，算法的时间复杂度下界为 $c \cdot g(n)$ ，那么我们说算法的时间复杂度是 $\Omega(g(n))$ 。

我们再次使用线性搜索作为示例来说明最好情况时间复杂度。

Example线性搜索最好情况复杂度

对于线性搜索算法，最好情况时间复杂度是 $\Omega(1)$ ，这意味着最好情况时间复杂度是常数。这是因为，我们有 $f(n) = 1$ ，和 $g(n) = 1$ ，当 $c=1$ 时，对于所有 $n \in \mathbb{N}$ ， $f(n) \ge 1 \cdot g(n)$ 。

平均情况时间复杂度 (大Theta记号)

Definition平均时间复杂度

令 $I(n)$ 为所有大小为 $n$ 的输入实例的集合，令 $T(n, x)$ 表示算法在 $I(n)$ 中输入 $x$ 上的运行时间。假设这些输入上有一个概率分布 $P(x)$ ，例如均匀分布，这意味着对于所有 $x \in I(n)$ ，我们有 $P(x)=1/(|I(n)|).$ 那么平均运行时间定义为 $T_{\text{avg}} (n)= \sum_{x \in I(n)} P(x) \cdot T(n,x).$ 如果每个输入的可能性均等，则此表达式简化为 $T_{\text{avg}} (n)= 1/(|I(n)|) \sum_{x \in I(n)}T(n,x).$

我们说一个算法的平均情况时间复杂度为 $\Theta(g(n))$ ，如果存在正常数 $c_1$ 和 $c_2$ 以及一个函数 $f(n)$ ，使得对于所有足够大的 $n$ ，算法在大小为 $n$ 的输入上的平均运行时间被 $c_1 \cdot g(n)$ 和 $c_2 \cdot g(n)$ 分别从下方和上方界定。换句话说，平均情况时间复杂度是 $\Theta(g(n))$ ，如果存在常数 $c_1$ , $c_2$ , 和 $n_0$ ，使得对于所有 $n \ge n_0$ ，我们有 $c_1 \cdot g(n) \le T_{\text{avg}} (n) \le c_2 \cdot g(n)$ 。

平均情况分析是算法性能更现实的衡量标准，但它也比最坏情况或最好情况时间复杂度更难确定。它需要了解输入的概率分布以及算法在每个输入上的预期运行时间。

为了更容易理解，我们可以说，平均时间复杂度，在概率论中，是算法时间复杂度的期望值，给定一个输入的概率分布，这个分布通常是均匀的。

现在我们将讨论线性搜索算法的平均情况时间复杂度，作为平均情况分析的一个示例。

Example线性搜索平均情况复杂度

对于线性搜索算法，假设目标元素在数组中任何位置或根本不存在的可能性均等，平均情况时间复杂度是 $\Theta(n)$ 。如果目标存在，平均比较次数是 $(1+2+...+n)/n = (n+1)/2$ 。如果目标不存在，则需要 $n$ 次比较。假设这 $n+1$ 种情况（目标在索引 0 到 n-1，或不存在）的可能性均等，平均比较次数是 $[n(n+1)/2 + n^2] / [n(n+1)]$ ，这简化为一个与 $n$ 成正比的值。因此， $T_{\text{avg}}(n) \in \Theta(n)$ 。

空间复杂度

空间复杂度是对算法所需工作存储量的度量。也就是说，算法在任何一点需要的内存量，在最坏情况下是多少。与时间复杂度一样，我们通常关心的是空间需求如何随输入规模的增长而增长，并且我们使用渐近记号来描述这种增长。

令 $S(n)$ 为算法的空间复杂度，其中 $n$ 是输入大小。这包括输入变量、辅助变量和输出变量的空间。

辅助空间： 这指的是算法使用的临时空间，不包括输入所占用的空间。对于许多算法，辅助空间复杂度比总空间复杂度更有趣，特别是当输入给定且不能修改时。

Example线性搜索空间复杂度

所呈现的线性搜索算法的空间复杂度为 $S(n) \in \Theta(1)$ 。这是因为它只使用固定数量的变量（例如，i、target 和输入数组本身，它被认为是给定的）。所需的空间不会随输入数组 $n$ 的大小而增长。

Example递归算法与空间复杂度

对于递归算法，空间复杂度必须考虑调用栈使用的空间。考虑计算第 $n$ 个斐波那契数的递归实现：

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

虽然它的时间复杂度很高，但它的空间复杂度由递归树的最大深度决定，即 $n$ 。因此， $S(n) \in \Theta(n)$ 。

算法复杂度的严谨解释²

对于具有数学分析和集合论背景的读者，我们可以进一步形式化算法复杂度的概念。

形式化时间和空间

令 $\mathcal{A}$ 为一个固定算法。令 $\mathcal{I}$ 为 $\mathcal{A}$ 所有可能输入的集合。对于每个输入 $x \in \mathcal{I}$ ，令 $|x|$ 表示其大小。

成本函数 $C: \mathcal{I} \to \mathbb{R}^+$ 可以表示时间（操作数量）或空间（使用的内存单元数量）。
特定情况（最坏、最好、平均）的复杂度函数是一个函数 $F: \mathbb{N} \to \mathbb{R}^+$ 。
- 最坏情况复杂度： $F_{\text{worst}}(n) = \sup_{\substack{x \in \mathcal{I} \\ |x| = n}} C(x)$
- 最好情况复杂度： $F_{\text{best}}(n) = \inf_{\substack{x \in \mathcal{I} \\ |x| = n}} C(x)$
- 平均情况复杂度： 需要在输入集合 $\{x \in \mathcal{I} : |x| = n\}$ 上的概率分布 $\mu_n$ 。那么， $F_{\text{avg}}(n) = \mathbb{E}_{X \sim \mu_n}[C(X)] = \int_{\{x: |x|=n\}} C(x) d\mu_n(x)$ 。对于大小为 $n$ 的 $m_n$ 个可能输入上的离散均匀分布，这变为 $F_{\text{avg}}(n) = \frac{1}{m_n} \sum_{\substack{x \in \mathcal{I} \\ |x| = n}} C(x)$ 。

作为集合关系的渐近记号

记号 $O$ , $\Omega$ , 和 $\Theta$ 描述了函数集合之间的关系。令 $\mathcal{G}$ 为所有函数 $g: \mathbb{N} \to \mathbb{R}^+$ 的集合。

$O(g(n)) = \{ f(n) \mid \exists c>0, n_0 \in \mathbb{N} \text{ s.t. } \forall n \ge n_0, 0 \le f(n) \le c \cdot g(n) \}$
$\Omega(g(n)) = \{ f(n) \mid \exists c>0, n_0 \in \mathbb{N} \text{ s.t. } \forall n \ge n_0, 0 \le c \cdot g(n) \le f(n) \}$
$\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))$

当我们陈述 $F(n) \in O(g(n))$ 时，我们的意思是函数 $F$ （可以是 $F_{\text{worst}}$ , $F_{\text{best}}$ 等）是集合 $O(g(n))$ 的一个元素。

计算模型的作用

精确的成本函数 $C(x)$ 取决于底层的计算模型（例如，随机存取机，图灵机）。例如：

在 RAM 上，算术运算可能需要 $O(1)$ 时间。
在多带图灵机上，如果数字可以任意大，它们可能需要 $O(\log n)$ 时间。

然而，在计算机科学的大多数算法分析中，隐含地假设了 RAM 模型，并且重点在于相对于输入大小的操作数量，抽象掉了常数因子和低阶项。这就是为什么渐近分析如此强大——它提供了一种与机器无关的方式来按基本增长率对算法进行分类。

如果我们使用公理化集合论系统，这不是严谨的，而我们只使用朴素集合论来解释这个概念。 ↩
本节是可选的，推荐给熟悉函数、集合和数学分析的读者。 ↩