算法复杂度旨在描述输入数据量 $N$ 时，算法的 时间使用 和 空间使用 情况

时间：假设各操作的运行时间为固定常数，统计算法运行的 计算操作的数量 ，以代表算法运行所需时间
空间：统计在最差情况下 ，算法运行所需使用的 最大空间

输入数据大小 $N$ 指算法处理的输入数据量，根据不同算法，具有不同的定义，例如：

排序算法： $N$ 代表需要排序的元素数量
搜索算法： $N$ 代表搜索范围的元素总数，例如数组大小、矩阵大小、二叉树节点数、图节点和边数等

# 时间复杂度

统计的是算法的 计算操作数量 ，而不是运行的绝对时间

计算操作数量和运行绝对时间呈正相关关系，并不相等。算法运行时间受到「编程语言、计算机处理器速度、运行环境」等多种因素影响。

体现的是计算操作随数据大小 $N$ 变化时的变化情况。假设算法运行总共需要 $1$ 次操作、 $100$ 次操作，此两情况的时间复杂度都为常数级 $O(1)$ ；需要 $N$ 次操作、 $100N$ 次操作的时间复杂度都为 $O(N)$

# 符号表示

时间复杂度具有最差、平均、最佳三种情况，分别使用 $O$ , $\Theta$ , $\Omega$ 三种符号表示

题目：输入长度为 N 的整数数组 nums ，判断此数组中是否有数字 7 ，若有则返回 true ，否则返回 false

解题算法：线性查找，即遍历整个数组，遇到 7 则返回 true

代码：

bool findSeven(vector<int>& nums) {
    for (int num : nums) {
        if (num == 7)
            return true;
    }
    return false;
}

最佳情况 $\Omega(1)$ ：当数组首个数字为 7 时，无论 nums 有多少元素，线性查找的循环次数都为 $1$ 次

最差情况 $O(N)$ ： nums 中所有数字都不为 7 ，此时线性查找会遍历整个数组，循环 N 次

平均情况 $\Theta$ ：需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度。例如本题，需要考虑数组长度、数组元素的取值范围等

# 常见种类

根据从小到大排列，常见的算法时间复杂度主要有：

$O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(2^N) < O(N!)$

算法时间复杂度常见种类

# 示例解析

对于以下所有示例，设输入数据大小为 $N$ ，计算操作数量为 $count$ 。图中每个「蓝色方块」代表一个单元计算操作。

# 常数 $O(1)$

运行次数与 $N$ 大小呈常数关系，即不随输入数据大小 $N$ 的变化而变化

int algorithm(int N) {
    int a = 1;
    int b = 2;
    int x = a * b + N;
    return 1;
}

对于以下代码，无论 $a$ 取多大，都与输入数据大小 $N$ 无关，因此时间复杂度仍为 $O(1)$

int algorithm(int N) {
    int count = 0;
    int a = 10000;
    for (int i = 0; i < a; i++) {
        count++;
    }
    return count;
}

$O(1)$ 时间复杂度

# 线性 $O(N)$

循环运行次数与 $N$ 大小呈线性关系，时间复杂度为 $O(N)$

int algorithm(int N) {
    int count = 0;
    for (int i = 0; i < N; i++)
        count++;
    return count;
}

之前一个例子的循环次数并不随 $N$ 改变，而这里的循环次数会随 $N$ 变化

对于以下代码，虽然是两层循环，但第二层与 $N$ 大小无关，因此整体仍与 $N$ 呈线性关系

int algorithm(int N) {
    int count = 0;
    int a = 10000;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < a; j++) {
            count++;
        }
    }
    return count;
}

$O(N)$ 时间复杂度

# 平方 $O(N^2)$

两层循环相互独立，都与 $N$ 呈线性关系，因此总体与 $N$ 呈平方关系

int algorithm(int N) {
    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            count++;
        }
    }
    return count;
}

以 冒泡排序 为例，其包含两层独立循环：

第一层复杂度为 $O(N)$ ；
第二层平均循环次数为 $\frac{N}{2}$ ，复杂度为 $O(N)$ ，推导过程如下：

$O(\frac{N}{2}) = O(\frac{1}{2})O(N) = O(1)O(N) = O(N)$

因此，冒泡排序的总体时间复杂度为 $O(N^2)$ ，代码如下所示

vector<int> bubbleSort(vector<int>& nums) {
    int N = nums.size();
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
            }
        }
    }
    return nums;
}

$O(N^2)$ 时间复杂度

# 指数 $O(2^N)$

生物学科中的 “细胞分裂” 即是指数级增长

算法中，指数阶常出现于递归，算法原理图与代码如下所示

int algorithm(int N) {
    if (N <= 0) return 1;
    int count_1 = algorithm(N - 1);
    int count_2 = algorithm(N - 1);
    return count_1 + count_2;
}

$O(2^N)$ 时间复杂度

# 阶乘 $O(N!)$

阶乘阶对应数学上常见的 “全排列”

如下图与代码所示，阶乘常使用递归实现，算法原理：第一层分裂出 $N$ 个，第二层分裂出 $N - 1$ 个，…… ，直至到第 $N$ 层时终止并回溯

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

$O(N!)$ 时间复杂度

# 对数 $O(\log N)$

对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况” 。对数阶常出现于 二分法 、分治等算法中，体现着 “一分为二” 或 “一分为多” 的算法思想

设循环次数为 $m$ ，则输入数据大小 $N$ 与 $2^m$ 呈线性关系，两边同时取 $\log_2$ 对数，则得到循环次数 $m$ 与 $\log_2 N$ 呈线性关系，即时间复杂度为 $O(\log N)$

int algorithm(int N) {
    int count = 0;
    float i = N;
    while (i > 1) {
        i = i / 2;
        count++;
    }
    return count;
}

如以下代码所示，对于不同 $a$ 的取值，循环次数 $m$ 与 $\log_a N$ 呈线性关系，时间复杂度为 $O(\log_a N)$ 。无论底数 a 取值，时间复杂度都可以记作 $O(\log N)$ ：

$O(\log_a N) = \frac{O(\log_2 N)}{O(\log_2 a)} = O(\log N)$

int algorithm(int N) {
    int count = 0;
    float i = N;
    int a = 3;
    while (i > 1) {
        i = i / a;
        count++;
    }
    return count;
}

如下图所示，为二分查找的时间复杂度示意图，每次二分将搜索区间缩小一半，二分的次数为 $\log_2 N$

$$O(\log N)$ 时间复杂度$

# 线性对数 $O(N \log N)$

两层循环相互独立，第一层和第二层时间复杂度分别为 $O(\log N)$ 和 $O(N)$ ，则总体时间复杂度为 $O(N \log N)$

int algorithm(int N) {
    int count = 0;
    float i = N;
    while (i > 1) {
        i = i / 2;
        for (int j = 0; j < N; j++)
            count++;
    }
    return count;
}

线性对数阶常出现于排序算法，例如 快速排序 、归并排序 、堆排序 等，其时间复杂度原理如下图所示

$$O(N \log N)$ 时间复杂度$

代码随想录：估计计算机在 1s 内能执行多少次操作：

代码随想录：递归算法的时间复杂度分析

# 空间复杂度

空间复杂度涉及的空间类型有：

输入空间 ：存储输入数据所需的空间大小
暂存空间 ：算法运行过程中，存储所有中间变量和对象等数据所需的空间大小
输出空间 ：算法运行返回时，存储输出数据所需的空间大小

通常情况下，空间复杂度指在输入数据大小为 $N$ 时，算法运行所使用的 暂存空间 + 输出空间 的总体大小

空间类型

根据不同来源，算法使用的内存空间分为三类：

指令空间 ：编译后，程序指令所使用的内存空间

数据空间 ：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间

struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

void algorithm(int N) {
    int num = N;              // 变量
    int nums[N];              // 动态数组
    Node* node = new Node(N); // 动态对象
}```

栈帧空间 ：程序 调用函数 是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。如以下代码所示，在循环中调用函数，每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 $O(1)$
```
int test() {
    return 0;
}

void algorithm(int N) {
    for (int i = 0; i < N; i++) {
        test();
    }
}
```
算法中，栈帧空间的累计常出现于递归调用 。如以下代码所示，通过递归调用，会同时存在 $N$ 个未返回的函数 algorithm() ，此时累计使用 $O(N)$ 大小的栈帧空间
```
int algorithm(int N) {
    if (N <= 1) return 1;
    return algorithm(N - 1) + 1;
}
```

# 符号表示

通常情况下，空间复杂度统计 算法在 “最差情况” 下使用的空间大小 ，以体现算法运行所需预留的空间量，使用符号 $O$ 表示

最差情况有两层含义，分别为 最差输入数据 、算法运行中的 最差运行点

例如以下代码：输入整数 $N$ ，取值范围 $N \ge 1$

void algorithm(int N) {
    int num = 5;           // O(1)
    vector<int> nums(10);  // O(1)
    if (N > 10) {
        nums.resize(N);    // O(N)
    }
}

最差输入数据 ：当 $N \le 10$ 时，数组 nums 的长度恒定为 $10$ ，空间复杂度为 $O(10) = O(1) O(10) = O(1)$ 。当 $N > 10$ 时，数组 nums 长度为 $N$ ，空间复杂度为 $O(N)$ 。因此，空间复杂度应为最差输入数据情况下的 $O(N)$
最差运行点 ：在执行 nums(10) 时，算法仅使用 $O(1)$ 大小的空间；而当执行 nums.resize(N) 时，算法使用 $O(N)$ 的空间；因此，空间复杂度应为最差运行点的 $O(N)$

# 常见种类

根据从小到大排列，常见的算法空间复杂度有：

$O(1) < O(\log N) < O(N) < O(N^2) < O(2^N)$

算法空间复杂度常见种类

# 示例解析

对于以下所有示例，设输入数据大小为正整数 $N$ ，节点类 Node 、函数 test() 如以下代码所示

// 节点类 Node
struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

// 函数 test()
int test() {
    return 0;
}

# 常数 $O(1)$

普通常量、变量、对象、元素数量与输入数据大小 $N$ 无关的集合，皆使用常数大小的空间

void algorithm(int N) {
    int num = 0;
    int nums[10000];
    Node* node = new Node(0);
    unordered_map<int, string> dic;
    dic.emplace(0, "0");
}

如以下代码所示，虽然函数 test() 调用了 $N$ 次，但每轮调用后 test() 已返回，无累计栈帧空间使用，因此空间复杂度仍为 $O(1)$

void algorithm(int N) {
    for (int i = 0; i < N; i++) {
        test();
    }
}

# 线性 $O(N)$

元素数量与 $N$ 呈线性关系的任意类型集合（常见于 一维数组 、链表、哈希表 等），皆使用线性大小的空间

void algorithm(int N) {
    int nums_1[N];
    int nums_2[N / 2 + 1];

    vector<Node*> nodes;
    for (int i = 0; i < N; i++) {
        nodes.push_back(new Node(i));
    }

    unordered_map<int, string> dic;
    for (int i = 0; i < N; i++) {
        dic.emplace(i, to_string(i));
    }
}

如下图与代码所示，此递归调用期间，会同时存在 $N$ 个未返回的 algorithm() 函数，因此使用 $O(N)$ 大小的栈帧空间

int algorithm(int N) {
    if (N <= 1) return 1;
    return algorithm(N - 1) + 1;
}

$O(N)$ 空间复杂度

# 平方 $O(N^2)$

元素数量与 $N$ 呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间

void algorithm(int N) {
    vector<vector<int>> num_matrix;
    for (int i = 0; i < N; i++) {
        vector<int> nums;
        for (int j = 0; j < N; j++) {
            nums.push_back(0);
        }
        num_matrix.push_back(nums);
    }

    vector<vector<Node*>> node_matrix;
    for (int i = 0; i < N; i++) {
        vector<Node*> nodes;
        for (int j = 0; j < N; j++) {
            nodes.push_back(new Node(j));
        }
        node_matrix.push_back(nodes);
    }
}

如下图与代码所示，递归调用时同时存在 $N$ 个未返回的 algorithm() 函数，使用 $O(N)$ 栈帧空间；每层递归函数中声明了数组，平均长度为 $\frac{N}{2}$ ，使用 $O(N)$ 空间；因此总体空间复杂度为 $O(N^2)$

int algorithm(int N) {
    if (N <= 0) return 0;
    int nums[N];
    return algorithm(N - 1);
}

$O(N^2)$ 空间复杂度

# 指数 $O(2^N)$

指数阶常见于 二叉树 、多叉树

例如，高度为 $N$ 的满二叉树（perfect binary tree）的节点数量为 $2^N$ ，占用 $O(2^N)$ 大小的空间；同理，高度为 $N$ 的满 $m$ 叉树的节点数量为 $m^N$ ，占用 $O(m^N) = O(2^N)$ 大小的空间

$O(2^N)$ 空间复杂度

# 对数 $O(\log N)$

对数阶常出现于分治算法的栈帧空间累计、数据类型转换等，例如：

快速排序 ，平均空间复杂度为 $\Theta(\log N)$ ，最差空间复杂度为 $O(N)$ 。拓展知识：通过应用 Tail Call Optimization ，可以将快速排序的最差空间复杂度限定至 $O(N)$
数字转化为字符串 ，设某正整数为 $N$ ，则字符串的空间复杂度为 $O(\log N)$ 。推导如下：正整数 $N$ 的位数为 $\log_{10} N$ ，即转化的字符串长度为 $\log_{10} N$ ，因此空间复杂度为 $O(\log N)$

代码随想录：递归算法的性能分析

# 时空权衡

优良的算法应具备两个特性，即时间和空间复杂度皆较低

实际上，对于某个算法问题，同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度，往往是以提升空间复杂度为代价的，反之亦然

由于当代计算机的内存充足，通常情况下，算法设计中一般会采取「空间换时间」的做法，即 牺牲部分计算机存储空间，来提升算法的运行速度

以 LeetCode 1. 两数之和为例，暴力枚举和辅助哈希表分别为空间最优和时间最优的两种算法

注：以上内容来自于 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/r8ytog/

# 时间复杂度

# 符号表示

# 常见种类

# 示例解析

# 常数 O(1)O(1)O(1)

# 线性 O(N)O(N)O(N)

# 平方 O(N2)O(N^2)O(N2)

# 指数 O(2N)O(2^N)O(2N)

# 阶乘 O(N!)O(N!)O(N!)

# 对数 O(log⁡N)O(\log N)O(logN)

# 线性对数 O(Nlog⁡N)O(N \log N)O(NlogN)

# 空间复杂度

# 符号表示

# 常见种类

# 示例解析

# 常数 O(1)O(1)O(1)

# 线性 O(N)O(N)O(N)

# 平方 O(N2)O(N^2)O(N2)

# 指数 O(2N)O(2^N)O(2N)

# 对数 O(log⁡N)O(\log N)O(logN)

# 时空权衡

二叉树

LeetCode - 链表专题

# 常数 $O(1)$

# 线性 $O(N)$

# 平方 $O(N^2)$

# 指数 $O(2^N)$

# 阶乘 $O(N!)$

# 对数 $O(\log N)$

# 线性对数 $O(N \log N)$

# 常数 $O(1)$

# 线性 $O(N)$

# 平方 $O(N^2)$

# 指数 $O(2^N)$

# 对数 $O(\log N)$