复杂度分析

时游大约 15 分钟

复杂度分析

复杂度分析犹如浩瀚的算法宇宙中的时空向导，带领我们从时间跟空间两个维度深入探索，寻找更优雅的解决方案。

算法效率评估

在算法设计中，追求以下两个层次的目标：

  • 找到问题解法：算法需要在规定的输入范围内可靠的在·求得问题的正确解。
  • 寻找最优解：同一个问题可能存在多个解法，算法效率要求获取尽可能的高效解法。

算法效率已经成为衡量算法优劣的主要指标，包括以下两个维度：

  • 时间效率：算法运行速度的快慢。
  • 空间效率：算法运行所需要的内存大小。

简而言之，我们的目标是设计既快又省的数据结构与算法。效率的评估方法主要分：实际测试与理论估算。

实际测试

实际测试主要依赖机器实际运行，通过监控算法运行时占用的内存以及运行所需的时间比较。但是这种方式有较大的局限性，具体如下：

  • 难以排除测试环境的干扰因素：系统硬件可能对不同的算法有所影响。
  • 开展完整的测试非常占用资源，随着数据量的增加算法会得出不一样的效率结果，这就需要占用大量的资源进行测试。

理论测试

由于实际测试具有较大的局限性，通常我们仅通过计算来评估算法的效率。这种估算方法被称为渐近复杂度分析，简称复杂度分析。

复杂度分析能够提现算法运行所需的时间和空间资源随着输入的数据大小之间的关系。它描述了输入数据大小的增加，算法执行所需的时间和空间的增长趋势，分为以下三个重点：

  • “时间和空间资源”：代表时间复杂度和空间复杂度。
  • “随着数据大小的增加”：反映了算法运行效率与输入数据体量之间的关系。
  • “时间和空间的增长趋势”：表示复杂度分析关注的并不是运行时间或占用空间的具体值，而是时间和空间增长的快慢。

迭代与递归

迭代

迭代是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某个代码，直到不满足条件为止。

for循环

for循环是常见的一种迭代形式之一，适合在预先知道循环次数时使用。

// 求和1+2+3+...+n
function add(n) {
	let res = 0;
	for (let i = 0; i <= n; i++) {
		res += i;
	}
	return res;
}

add(3);
求和流程图
求和流程图

该求和函数的操作数量与输入的n成正比，即线性关系，而时间复杂度就是描述的这个线性关系。

while循环

while循环也是一种实现迭代的方法，在while循环中，程序每次都会先检查条件是否成立，成立则继续执行代码，否则就结束循环。

function whileAdd(n) {
	let res = 0;
	let i = 0;
	while (i <= n) {
		res += i;
		++i
	}
    return res
}

whileAdd(3)

相对于for循环而言，while循环更加灵活。

嵌套循环

可以在一个循环结构中再嵌套一个循环结构，这种嵌套结构称为嵌套循环。

function nest(n) {
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= n; j++) {
			// 
		}
	}
}

nest()
嵌套循环
嵌套循环

在该种情况下，函数的操作数量与输入的n呈现指数关系，会将时间复杂度提升至O(n^2)。

递归

递归是一种算法策略，通过函数调用自身来解决问题，主要包含两个阶段：

  1. 递：程序不断深入调用自身，通常传入更小或更简洁的参数，直到满足终止条件。
  2. 归：触发终止条件后，程序从最底层的递归函数开始逐层返回，汇集每一层结果。

递归代码三要素：

  • 终止条件：决定什么时候从递转到归。
  • 递归调用：递归调用自身，通常传入更小或更简洁的参数。
  • 返回结果：对于归，将当前递归层级的结果返回上一层。
// 递归
function recursionAdd(n) {
	let res = 1;
	if (n == 1) return res;
	res = recursionAdd(n - 1);
	return n + res;
}

console.log(recursionAdd(3));
递归流程图
递归流程图

递归和迭代都可得到相同的结果，但是这是两种完全不同的思考和解决方法。递归是自下而上的解决问题，例如从1遍历到n执行求和操作。而递归是自上而下的解决问题，通常将大问题分解为更小的问题，直到解决出答案后再汇总。，例如f(n) = n + f(n-1)，不断的分解下去，直到f(1)时结束。

  1. 调用栈：函数调用时，系统会为其开启新的函数分配内存，用于存储局部变量、调用地址以及其他信息等，只有函数结束后这部分内存才会被释放。而递归，则会不断的产生新的调用栈，会产生额外的开销，因此递归通常会比迭代更消耗内存空间，且时间效率会更低，同时过深的递归可能会导致内存溢出。 普通递归流程图

  2. 尾调用：如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器进行优化，使其在空间效率与迭代相当，这叫做尾递归。

    1. 普通递归：当函数返回到上一层的函数后，需要执行上一层的结果，因此系统需要保存上一层调用上下文。
    2. 尾递归：递归调用是函数返回前的最后一步，因此系统不需要保存上一层调用上下文，因此尾递归可以节省空间。 尾递归流程图
// 尾递归
function tailRecursionAdd(n, res = 1) {
	if (n == 1) return res;
	return tailRecursionAdd(n - 1, n + res);
}
console.log(tailRecursionAdd(3));
  • 普通递归：求和操作是在归的过程中，每层返回后都要再执行一次求和操作。
  • 尾递归：求和操作是在递的过程中执行的，归的过程中不需要再执行求和操作，只需要层层返回即可。
  1. 递归树

斐波那契数列(兔子数列)问题，在函数内递归调用了两个函数，从一个调用产生了两个调用分支。如下图所示，这样不断递归调用下去，最终将产生一棵层数为n的递归树。

// 兔子数列问题
function rabbit(n) {
	if (n == 1 || n == 2) return n - 1;
	res = rabbit(n - 1) + rabbit(n - 2);
	return res;
}
console.log(rabbit(5));  // 0、1、1、2、3、5、8、13、21、34
递归树流程
递归树流程

递归体现了“将问题分解为更小的问题”的思想，适合进行分治策略、

  • 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用了这种思维方式。
  • 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

时间复杂度

算法程序运行时间可以直观且准确的反映算法的效率。但是如何准确的预估运行时间？

  • 确定运行平台，包括硬件配置、编程语言、系统环境等，这些因素都会影响代码的运行效率。
  • 评估各种计算操作所需的时间，了例如加法操作需要1ms，乘法操作需要10ms，打印操作需要5ms
  • 统计代码中所有的计算操作。
// 时间复杂度
function algorithm(n) {
	let a = 2;  // 1
	a = n * 2;  // 10
	for (let i = 0; i < n; i++) {  // n
		console.log(n); // 5n
	}
}

// 时间复杂度：11 + 6n

统计算法的运行时间既不合理也不现实

统计时间增长趋势

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

// 时间增长趋势
function A(n) {
	console.log(1);
}

function B(n) {
	for (let i = 0; i < n; i++) {
		console.log(0);
	}
}

function C(n) {
	for (let i = 0; i < 10000; i++) {
		console.log(0);
	}
}

A只有一个打印操作，且不随着数据n的变化而增长，因此时间复杂度为O(1)。B的打印操作是随着n的增大而线性增长，因此时间复杂度为O(n)。C的打印操作固定10000，不随着n的变化而增长，因此时间复杂度为O(1)。

算法 A、B 和 C 的时间增长趋势
算法 A、B 和 C 的时间增长趋势

时间复杂度分析特点：

  • 时间复杂度能有效评估算法效率：例如算法B的运行时间随着n呈线性变化，在n>1但是n<10000时，算法B比A慢，但是比C快。在n>10000时，算法B运行时间则会比C长。
  • 时间复杂度推算方法简单：在时间复杂度分析中可以将所有操作的耗时都一样，从而将计算操作时间统计简化为计算操作数量统计。
  • 有一定的局限性：算法的运行时间很依赖于n的影响，很难在特定的情况下判断算法效率的高低，例如n>10000时。

函数渐近上界

给定一个输入大小为n的函数，记为T(n)

function algorithm(n) {
	let a = 2;  // 1
	a = n * 2;  // 1
	for (let i = 0; i < n; i++) {  // n
		console.log(n); // n
	}
}

上述时间复杂度为：2 + 2n，T(n)其运行时间是线性的，因此时间复杂度为O(n)，O(n)记为函数T(n)的渐近上界。 时间复杂度分析本质上是计算”操作数量T(n)“的渐近上界。定义为：若存在正实数c和实数n0，使得所有的n>n0时，均有T(n)<=c*f(n)，则可认为f(n)给出了T(n)的一个渐近上界，记为T(n)=O(f(n))。 渐近上界

推算方法

依据定义可以获取时间复杂度O(f(n))，但是如何确定渐近上界f(n)呢？分为两步：首先统计操作数量，然后判断渐近上界。

  1. 统计操作数量：针对代码逐行计算，对于c.f(n)中的常数项C可以取任意大小，因此操作数量T(n)中的各种系数、常数项均可忽略，例如2n + 12可简化为n。
// 操作数量示例
function actionAccount(n) {
	let a = 0;  // 0
	a += n;  // 0
	for (let i = 0; i < n; i++) {  // n
		console.log(i);
	}
	for (let i = 0; i < n; i++) {  // n*n
		for (let j = 0; j < n; j++) {
			console.log(i, j);
		}
	}
}

// 该函数复杂度为O(n^2)
  1. 判断渐近上界 时间复杂度由T(n)中最高阶来决定，因为随着n趋向于无穷大时，最高阶将发挥决定性作用，其余函数均可忽略不计。例如针对以下操作数量，复杂度为分别为：10000：O(1)、3n+2：O(n)、2n2+3n+1：O(n2)、2n2+10000n10000：O(2^n)

常见类型

假设数据大小为n，常见的时间复杂度从低到高排序为： O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) 常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶

常见时间复杂度
常见时间复杂度
常数阶O(1)

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

线性阶O(n)

线性阶的操作数量与输入的数据大小n成线性变化，常常出现于单层循环中。

平方阶O(n^2)

平方阶的操作数量与输入的数据大小n成平方变化，常常出现于嵌套循环中。

常数阶、线性阶、平方阶对比)
常数阶、线性阶、平方阶对比)
指数阶O(2^n)

生物学的细胞分裂是指数阶增长的经典案例，初始状态为1，分裂一次后为2，再分裂为4，n轮后有2^n个细胞。

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

对数阶O(log n)

与指数阶相反，对数阶反映了每轮减一半的情况。对数阶通常用于分治策略的算法中，体现了一分为多跟化繁为简的算法思路，它增长缓慢，是仅次于常数阶的时间复杂度。

对数阶O(log n)
对数阶O(log n)
线性对数阶O(nlogn)

线性对数阶常出现于嵌套循环中，分别为O(n)和O(log n)进行组合，常用与快速排序、归并排序以及堆排序等。

线性对数阶O(nlogn)
线性对数阶O(nlogn)
阶乘阶O(n!)

阶乘阶对应数学上的全排序问题，给定n个互补重复的元素，求其所有可能的排列方案，即n!=n*(n-1)(n-2)...*1。

阶乘阶O(n!)
阶乘阶O(n!)

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

算法的时间效率往往不是固定的，而是与输入数据的分布有关。假如输入一个长度为n的数组nums，由1~n的数字组成，每个数字仅出现一次，但是顺序是打乱的，目标是返回元素1的索引。

  • 当1位于末尾时，需要完整遍历数组，此时就为最差时间复杂度，最差时间复杂度符号为大写O表示。
  • 当1位于起始时，无论数组多长，都是最佳时间复杂度，最佳时间复杂度符号为Ω。
  • 现实情况下，最佳时间复杂度只有很小概率才能达到，最差时间复杂度更加实用，它提供了一个效率安全值。我们通常使用最差时间复杂度作为算法效率的评判标准。

空间复杂度

空间复杂度用于衡量算法占用的内存空间随着数据量变大时的增长趋势。相对于时间复杂度而言，空间复杂度就目前算法而言并不关注，因为目前设备内存空间较大，通常采用的算法策略就是以空间换取时间。

算法相关空间

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

  1. 输入空间：用于存储算法的输入数据。
  2. 暂存空间：用于存储算法在运行过程中的遍历、对象、函数上下文等数据。
  3. 输出空间：用于存储算法的输出数据。 一般情况下，算法的空间复杂度统计范围是“暂存空间”+“输出空间”。

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

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

推算方法

空间复杂度的推算方法类似于时间复杂度推算方法，只需将统计对象从操作数量转为使用空间大小。我们常常只需关注最差空间复杂度即可，因为必须确保所有的输入数据都有足够的内存空间预留。

function algorithm(n) {
    const a = 0;                   // O(1)
    const b = new Array(10000);    // O(1)
    if (n > 10) {
        const nums = new Array(n); // O(n)
    }
}

// 在n小于10时，不创建nums数组，空间复杂度始终为O(1)
// 在n大于10时，创建nums数组，需要占用O(n)空间，所以空间复杂度为O(n)

常见类型

设数据大小为n，以下从低到高空间复杂度排序:O(1) < O(logn) < O(n) < O(n^2) < O(2^n)

空间复杂度排序
空间复杂度排序

常数阶O(1)

常见于数量与输入数据大小n无关的常量、变量和对象。在循环中初始化变量或调用函数而占用的空间，在进入下一循环后会被释放，因此空间复杂度为O(1)。

线性阶O(n)

常见于元素数量与n成正比的数组、链表、栈、队列等。

平方阶O(n^2)

常见于矩阵和图中，元素数量与n成平方关系。

指数阶O(2^n)

常见于二叉树中。

对数阶O(log n)

常见于分治算法。

权衡时间与空间

理想情况下我们想将时间复杂度与空间复杂度均取其最优，但是很难实现。降低时间复杂度的代价往往需要占用较大的空间，这就是以空间换时间，反之则称为以时间换空间。

上次编辑于:
贡献者: Sunshine,minmengwei
Loading...
时游的个人技术博客
Copyright © 2026 时游