复杂度分析

Akkiri...大约 15 分钟数据结构与算法

算法效率评估

算法效率是衡量算法优劣的主要评价指标，它包括一下两个维度。

时间效率：算法运行速度的快慢。
空间效率：算法占用内存空间的大小。

**我们的目标是设计 “即快又省” 的数据结构与算法。**而有效地评估算法效率至关重要，效率评估方法主要分为两种：实际测试、理论估算。由于实际测试无法排除环境的干扰元素导致难以精确描述算法效率，所以下面主要介绍算法效率的理论估算。

理论估算

由于实际测试的局限性，我们考虑仅通过一些计算来评估算法的效率。这种估算方法被称为「渐近复杂度分析 asymptotic complexity analysis」，简称「复杂度分析」。

复杂度分析体现算法运行所需的时间（空间）资源与输入数据大小之间的关系。**它描述了随着输入数据大小的增加，算法所需时间和空间的增长趋势。**我们可以将其分为三个重点以便理解。

「时间和空间资源」分别对应「时间复杂度 time complexity」和「空间复杂度 space complexity」。
「随着输入数据大小的增加」意味着复杂度反映了算法效率与输入数据量之间的关系。
「时间和空间的增长趋势」表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的「快慢」。

复杂度分析客服了实际测试方法的弊端

它独立于测试环境，分析结果适用与所有运行平台。
它可以体现不同数据量下的算法效率。

时间复杂度

统计时间增长趋势

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

下面通过一个例子来理解。假设输入数据大小为 $n$ ，给定三个函数 A、B 和 C：

# A 的时间复杂度：常数阶
def A(n: int):
    print(0)
    
# B 的时间复杂度：线性阶
def B(n: int):
    for i in range(0):
        print(0)

# C 的时间复杂度：常数阶
def C(n: int):
    for i in range(10000):
        print(0)

函数 A 只有 1 个打印操作，算法运行时间不随着 $n$ 增大而增长。我们称此算法的时间复杂度为「常数阶」。
函数 B 中的打印操作需要循环 $n$ 次，算法运行时间随着 $n$ 增大呈线性增长。此算法的时间复杂度被称为「线性阶」。
函数 C 中的打印操作需要循环 1000000 次，虽然运行时间很长，但它与输入数据大小 $n$ 无关。因此 C 的时间复杂度和 A 相同，仍为「常数阶」。

函数渐近上界

给定一个输入大小为 $n$ 的函数：

def algorithm(n: int):
    a = 1	    # +1
    a = a + 1	# +1
    a = a * 2	# +1 
    
    #循环 n 次
    for i in range(n):	# +1
        print(0)	    # +1

设算法的操作数量是一个关于输入数据大小 $n$ 的函数，记为 $T(n)$ ，则以上函数的操作数量为：

T(n)=3+2n

$T(n)$ 是一次函数，说明其运行时间的增长趋势是线性的，因此它的时间复杂度是线性阶。

我们将线性阶的时间复杂度记为 $O(n)$ ，这个数学符号被称为「大 $O$ 记号 big- $O$ notation」，表示函数 $T(n)$ 的「渐近上界 asymptotic upper bound」。

时间复杂度分析本质上是计算「操作数量函数 $T(n)$ 」的渐近上界，其具有明确的数学定义。

函数渐近上界

若存在正实数 $c$ 和实数 $n_0$ ，使得对于所有的 $n>n_0$ ，均有 $T(n)\le c\cdot f(n)$ ，则可认为 $f(n)$ 给出了 $T(n)$ 的一个渐近上界，记为 $T(n)=O(f(n))$ 。

渐近上界推算方法

第一步： 统计操作数量

首先提出以下计数简化技巧：

忽略 $T(n)$ 中的常数项。因为它们都与 $n$ 无关，对时间复杂度不产生影响。
省略所有系数。例如，循环 $2n$ 次、 $5n+1$ 次等，都可以简化记为 $n$ 次，因为 $n$ 前面的系数对时间复杂度没有影响。
循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积。

void algorithm(int n) {
    int a = 1;  // +0
    a = a + n;  // +0
    
    for (int i = 0; i < 5 * n + 1; i++) {
        System.out.println(0);
    }  // +n
    
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            System.out.println(0);
        }
    }  // +n*n
}

最后推出时间复杂度为 $O(n^2)$ 。

T(n)=n^2+n

第二步： 判断渐近上界

时间复杂度由多项式 $T(n)$ 中最高阶的项来决定。这是因为在 $n$ 趋于无穷大时，最高阶的项将发挥主导作用，其他项的影响都可以被忽略。

下表是不同操作数量对应的时间复杂度：

操作数量 $T(n)$	时间复杂度 $O(f(n))$
$10000$	$O(1)$
$3n+2$	$O(n)$
$2n^2+3n+2$	$O(n^2)$
$n^3+10000n^2$	$O(n^3)$
$2^n+10000n^{10000}$	$O(2^n)$

常见类型

设输入数据大小为 $n$ ，常见的时间复杂度类型如下所示（按从低到高排列）：

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) \newline \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{线性对数阶} < \text{平方阶} < \text{指数阶} < \text{阶乘阶}

常数阶 $O(1)$

常数阶的操作数量与输入的数据大小 $n$ 无关，即不随着 $n$ 的变化而变化。

在以下函数中，尽管操作数量 size 可能很大，但由于其与输入的数据大小 $n$ 无关，因此时间复杂度仍为 $O(1)$ ：

int constant(int n) {
    int count = 0;
    int size = 10000;
    for(int i = 0; i < size; i++) {
        count++;
    }
    
    return count;
}

线性阶 $O(n)$

线性阶的操作数量相对于输入数据大小 $n$ 以线性级别增长。线性阶通常出现在单层循环中：

int linear(int n) {
    int count = 0;
    
    for(int i = 0; i < n; i++) {
        count++;
    }
    
    return count;
}

平方阶 $O(n^2)$

平方阶的操作数量相对于输入数据大小 $n$ 以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层循环都为 $O(n)$ ，因此总体为 $O(n^2)$ ：

int quadratic(int n) {
    int count = 0;
    
    // 循环次数与数组长度成平方关系
    for(int i = 0; i < n; i++) {
        for(int j  = 0; j < n; j++) {
            count++;
        }
	}
    
    return count;
}

指数阶 $O(2^n)$

生物学的 “细胞分裂” 是指数阶增长的典型例子：初始状态为 1 个细胞，分裂一轮后变为两个，分裂两轮后变为 4 个，以此类推，分裂 $n$ 轮后有 $2^n$ 个细胞。

/* 指数阶（循环实现） */
int exponential(int n) {
    int count = 0, base = 1;
    
    // 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < base; j++) {
            count++;
        }
        base *= 2;
    }
    
    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count;
}

在实际算法中，指数阶常出现于递归函数中。例如在以下代码中，其递归地一分为二，经过 $n$ 次分裂后停止：

/* 指数阶（递归实现） */
int expRecur(int n) {
    if (n == 1)
        return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}

指数阶增长非常迅速，在穷举法（暴力搜索、回溯等）中比较常见。对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心等算法来解决。

对数阶 $O(logn)$

与指数阶相反，对数阶反映了“每轮缩减到一半”的情况。设输入数据大小为 � ，由于每轮缩减到一半，因此循环次数是 $log_2{n}$ ，即 $2^n$ 的反函数。

int logarithmic(float n) {
    int count = 0;
    
    while (n > 1) {
        n = n / 2;
        count++;
    }
    
    return count;
}

线性对数阶 $O(nlogn)$

线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 $O(logn)$ 和 $O(n)$ 。相关代码如下：

int linearLogRecur(float n) {
    if (n <= 1)
        return 1;
    
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
    for (int i = 0; i < n; i++) {
        count++;
    }
    
    return count;
}

阶乘阶 $O(n!)$

阶乘阶对应数学上的“全排列”问题。给定 $n$ 个互不重复的元素，求其所有可能的排列方案，方案数量为：

n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1

阶乘通常使用递归实现，如下：


int factorialRecur(int n) { 
    int count = 0;
    
    if (n == 0) {
        return 1;
    }
    
    for (int i = 0; i < n; i++) {
        count += factorialRecur(n - 1);
    }
    
    return count;
}

最差、最佳、平均时间复杂度

算法的时间效率往往不是固定的，而是与输入数据的分布有关，所以我们引入最差、最佳时间复杂度。“最差时间复杂度” 对应函数渐近上界，使用大 $O$ 记号表示。相应地，“最佳时间复杂度” 对应函数渐近下界，用 $\Omega$ 记号表示：

假设输入一个长度为 $n$ 的数组 nums ，其中 nums 由从 1 至 $n$ 的数字组成，每个数字只出现一次；但元素顺序是随机打乱的，任务目标是返回元素 1 的索引。我们可以得出以下结论。

当 nums = [*, *, ..., 1]，即当末尾元素是 1 时，需要完整遍历数组，达到最差时间复杂度 $O(n)$ 。
当 nums = [1, *, ..., *]，即当首个元素是 1 时，无论数组多长都不需要继续遍历数组，达到最佳时间复杂度 $\Omega(1)$ 。

从上述示例可以看出，最差或最佳时间复杂度只出现于“特殊的数据分布”，这些情况的出现概率可能很小，并不能真实地反映算法运行效率。相比之下，平均时间复杂度可以体现算法在随机输入数据下的运行效率，用 $\Theta$ 记号来表示。

提示

我们在实际中很少使用最佳时间复杂度，因为通常只有在很小概率下才能达到，可能会带来一定的误导性。而最差时间复杂度更为实用，因为它给出了一个效率安全值，让我们可以放心地使用算法。

空间复杂度

算法相关空间

算法在运行过程中使用的内存空间主要包括以下几种：

输入空间： 用于存储算法的输入数据。
**暂存空间：**用于存储算法在运行过程中的变量、对象、函数上下文等数据。
**输出空间：**用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是 “暂存空间” 加上 “输出空间”。

暂存空间可以进一步划分为三个部分：

**暂存数据：**用于保存算法运行过程中的各种常量、变量、对象等。
**栈帧空间：**用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
**指令空间：**用于保存编译后的指令，在实际统计过程中通常忽略不计。

分析一段程序的空间复杂度，我们通常只统计暂存数据、栈帧空间和输出数据三部分。

/* 类 */
class Node {
    int val;
    Node next;
    Node(int x) { val = x; }
}

/* 函数 */
int function() {
    // 执行某些操作...
    return 0;
}

int algorithm(int n) {        // 输入数据
    final int a = 0;          // 暂存数据（常量）
    int b = 0;                // 暂存数据（变量）
    Node node = new Node(0);  // 暂存数据（对象）
    int c = function();       // 栈帧空间（调用函数）
    return a + b + c;         // 输出数据
}

推算方法

空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从 “操作数量” 转为 “使用空间大小”。

而与时间复杂度不同的是，我们通常只关注最差时间复杂度。这是因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留。

观察以下代码，最差空间复杂度中的 “最差” 有两层含义：

void algorithm(int n) {
    int a = 0;                   // O(1)
    int[] b = new int[10000];    // O(1)
    if (n > 10)
        int[] nums = new int[n]; // O(n)
}

**以最差输入数据为准：**当 $n<10$ 时，空间复杂度为 $O(1)$ ；但当 $n>10$ 时，初始化的数组 nums 占用 $O(n)$ 空间；因此最差空间复杂度为 $O(n)$ 。
**以算法运行中的峰值内存为准：**例如，程序在执行最后一行之前，占用 $O(1)$ 空间；当初始化数组 nums 时，程序占用 $O(n)$ 空间；因此最差空间复杂度为 $O(n)$ 。

在递归函数中，需要注意统计栈帧空间。例如在以下代码中：

int function() {
    // 执行某些操作
    return 0;
}
/* 循环 O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        function();
    }
}
/* 递归 O(n) */
void recur(int n) {
    if (n == 1) return;
    return recur(n - 1);
}

函数 loop() 在循环中调用了 $n$ 次 function() ，每轮中的 function() 都返回并释放了栈帧空间，因此空间复杂度仍为 $O(1)$ 。
递归函数 recur() 在运行过程中会同时存在 $n$ 个未返回的 recur() ，从而占用 $O(n)$ 的栈帧空间。

常见类型

设输入数据大小为 $n$ ，常见的空间复杂度类型如下所示（按从低到高排列）：

O(1) < O(\log n) < O(n) < O(n^2) < O(2^n) \newline \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{平方阶} < \text{指数阶}

常数阶 $O(1)$

常数阶常见于数量与输入数据大小 $n$ 无关的常量、变量、对象。

int function(){
    // 某些操作
	return 0;
}

// 常数阶
void constant(int n){
    // 常量、变量、对象占用 O(1) 的空间
    final int a = 0;
    int b = 0;
    int[] nums = new int[10000];
    
    // 循环中的变量占用 O(1) 的空间
    for(int i = 0; i < n; i++){
        int c = 0;
    }
    
    // 循环中的函数占用 O(1) 的空间
    for(int i = 0; i < n; i++){
        function();
    }
}

提示

在循环中初始化变量或调用函数而占用的内存，在进入下一个循环后就会被释放，因此不会累积占用空间，空间复杂的仍为 O(1)。

线性阶

线性阶常见于元素数量与 $n$ 成正比的数组、链表、栈、队列等：

void linear(int n){
    // 长度为 n 的数组占用 O(n) 的空间
    int[] nums = new int[n];
    
    // 长度为 n 的列表占用 O(n) 的空间
    List<String> nodes = new ArrayList<>();
    for(int i = 0; i < n; i++){
        nodes.add(String.valueOf(i))
    }
    
    // 长度为 n 的哈希表占有 O(n) 的空间
    Map<Integer, String> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        map.put(i, String.valueOf(i));
    }
}

下面是一个函数递归调用的例子，函数的递归深度为 n，即同时存在 n 个未返回的 linearRecur() 函数，使用了 O(n) 大小的栈帧空间：

void linearRecur(int n) {
    System.out.println("递归 n = " + n);
    if(n == 1)
        return;
    linearRecur(n - 1);
}

平方阶 $O(n^2)$

平方阶常见于矩阵和图，元素数量与 $n$ 成平方关系：

void quadratic(int n) {
    // 矩阵占用 O(n^2) 空间
    int[][] numMatrix = new int[n][n];
    
    // 二维列表占用 O(n^2) 空间
    List<List<Integer>> numList = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<Integer> tmp = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            tmp.add(0);
        }
        numList.add(tmp);
    }
}

函数递归深度为 $n$ ，在每个递归函数中都初始化了一个数组，长度分别为 $n,n-1,\dots,2,1$ ，平均长度为 $n/2$ ，因此总体占用 $O(n^2)$ 空间：

int quadraticRecur(int n) {
    if (n <= 0)
        return 0;
    
    // 数组 nums 长度为 n, n-1, ..., 2, 1
    int[] nums = new int[n];
    System.out.println("递归 n = " + n + " 中的 nums 长度 = " + nums.length);
    return quadraticRecur(n - 1);
}

指数阶 $O(2^n)$

指数阶常见于二叉树，高度为 $n$ 的 “满二叉树” 的节点数量为 $2^n-1$ ，占用 $O(2^n)$ 空间：

TreeNode buildTree(int n) {
    if (n == 0)
        return null;
    TreeNode root = new TreeNode(0);
    root.left = buildTree(n - 1);
    root.right = buildTree(n - 1);
    return root;
}

对数阶 $O(log n)$

对数阶常见于分治算法。例如归并排序，输入长度为 $n$ 的数组，每轮递归将数组从中点划分为两半，形成高度为 $log n$ 的递归树，使用 $O(log n)$ 的帧栈空间。

权衡时间和空间

理想情况下，我们希望算法的时间复杂度和空间复杂度都能达到最优。然而在实际情况下，同时优化时间复杂度和空间复杂度是非常困难的。

**降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。**我们将牺牲内存空间来提升算法运行速度的思路称为 “以空间换时间”；反之，则称为 “以时间换空间”。

选择哪种思路取决于我们更看重哪个方面。在大多数情况下，时间比空间更宝贵，因此 “以空间换时间” 通常是更常用的策略。当然，在数据量很大的情况下，控制空间复杂度也是非常重要的。

昵称

邮箱

网址

按正序
按倒序
按热度

复杂度分析

# 算法效率评估

# 理论估算

# 时间复杂度

# 统计时间增长趋势

# 函数渐近上界

# 渐近上界推算方法

# 常见类型

# 最差、最佳、平均时间复杂度

# 空间复杂度

# 算法相关空间

# 推算方法

# 常见类型

# 权衡时间和空间

预览:

算法效率评估

理论估算

时间复杂度

统计时间增长趋势

函数渐近上界

渐近上界推算方法

常见类型

最差、最佳、平均时间复杂度

空间复杂度

算法相关空间

推算方法

常见类型

权衡时间和空间