算法复杂度旨在描述输入数据量 $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(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^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(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(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(\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(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;
	}

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

时间复杂度

代码随想录：估计计算机在 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)$

算法空间复杂度常见种类