一文吃透算法的「时间复杂度」与「空间复杂度」

一文吃透算法的「时间复杂度」与「空间复杂度」本文从如何衡量一个算法的好坏出发系统梳理算法效率、时间复杂度、空间复杂度三大主题配套 10 道经典代码实例逐行剖析帮助你建立完整的大 O 分析思维。目录一、引言如何衡量一个算法的好坏二、算法效率时间效率与空间效率三、时间复杂度3.1 时间复杂度的概念3.2 大 O 的渐进表示法3.3 推导大 O 阶的方法3.4 最好、平均与最坏情况3.5 常见时间复杂度计算举例四、空间复杂度4.1 空间复杂度的概念4.2 常见空间复杂度计算举例五、常见复杂度量级对比与总结一、引言如何衡量一个算法的好坏先看一个最朴素的问题求斐波那契数列下面这段递归代码到底好不好为什么我们凭什么来判断它的好坏publicstaticlongFib(intN){if(N3){return1;}returnFib(N-1)Fib(N-2);}直觉上它写得简洁、逻辑清晰似乎是好代码。但当你试着计算Fib(50)时程序会卡很久很久——这就是问题所在代码短小不等于算法高效。要客观评价一个算法的优劣我们不能凭感觉也不能只靠把程序放到机器上跑一遍计时而需要一套与机器无关、能反映算法本质的衡量标准。这套标准就是对算法效率的分析具体落地为时间复杂度与空间复杂度。二、算法效率时间效率与空间效率算法效率分析分为两种第一种是时间效率第二种是空间效率。时间效率被称为时间复杂度主要衡量一个算法的运行速度空间效率被称为空间复杂度主要衡量一个算法运行过程中所需要的额外空间。在计算机发展早期计算机的存储容量非常小因此当时人们不太舍得在空间上开销对空间复杂度并不特别在乎。而随着计算机行业的飞速发展硬件存储容量已经达到了很高的程度内存价格也一直走低所以我们如今已经不需要再特别关注一个算法的空间复杂度评估算法时更看重的是时间复杂度。补充说明这并不意味着空间复杂度完全不重要。在嵌入式、移动端、海量数据等内存受限场景下空间优化依然关键。只是对于一般的算法入门与日常业务开发时间复杂度是首要指标。三、时间复杂度3.1 时间复杂度的概念时间复杂度的定义在计算机科学中算法的时间复杂度是一个数学函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能精确算出来的——只有你把程序放到机器上真正跑起来才能知道具体耗时。但是我们需要每个算法都上机测试吗理论上可以但这非常麻烦而且结果还会受机器性能、负载、编译器等各种因素干扰。于是人们想到了用**“基本操作的执行次数”**来代替运行时间这就是时间复杂度这种分析方式的由来。一个算法所花费的时间与其语句的执行次数成正比例关系因此算法中基本操作的执行次数就是该算法的时间复杂度。记作T(N) O(F(N))其中F(N)是基本操作执行次数关于问题规模N的函数。3.2 大 O 的渐进表示法来看一段代码先尝试计算它的基本操作执行了多少次voidfunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}func1实际执行的基本操作次数为F(N) N^2 2*N 10代入几个规模感受一下N精确执行次数 F(N)101301001021010001002010仔细观察当N不断变大时N^2这一项的增长速度远远把2*N和常数10甩在身后。当N 1000时N^2 1,000,000占了总数的绝大部分而2*N 10 2010几乎可以忽略。实际中我们计算时间复杂度时并不需要计算精确的执行次数而只需要大概的执行次数。这就是大 O 渐进表示法的意义所在。大 O 符号Big O notation是用于描述函数渐进行为的数学符号它只保留对结果影响最大的主导项去掉那些影响不大的项。3.3 推导大 O 阶的方法把精确次数函数简化成大 O 阶只需三步用常数 1取代运行次数函数中所有的加法常数在修改后的运行次数函数中只保留最高阶项如果最高阶项存在且系数不为 1则去掉与该项相乘的常数得到的结果就是大 O 阶。用大 O 渐进表示法后func1的时间复杂度推导过程为F(N) N^2 2*N 10 → N^2 2*N 1 (步骤1常数 10 用 1 替代) → N^2 (步骤2只保留最高阶项 N^2) → O(N^2) (步骤3N^2 系数为 1无需再去常数)N精确次数 F(N)大 O 估算 O(N^2)101301001001021010000100010020101000000通过对比你会发现大 O 渐进表示法去掉了那些对结果影响不大的项简洁明了地表示出了执行次数并且随着N增大估算值与精确值越来越接近。3.4 最好、平均与最坏情况有些算法的时间复杂度存在最好、平均和最坏三种情况最坏情况任意输入规模下的最大运行次数上界最好情况任意输入规模下的最小运行次数下界平均情况在各种输入下运行次数的期望值。举例在一个长度为N的数组中顺序搜索一个数据x。最好情况1 次就找到x恰好在第一个位置最坏情况N次才找到x在最后一个位置或者根本不存在。在实际中我们一般关注的是算法的最坏运行情况。因为最坏情况给出了一个性能底线的保证——即使遇到了最不利的输入算法也不会比这更差。所以上例中数组搜索数据的时间复杂度记为O(N)。3.5 常见时间复杂度计算举例下面 7 个实例覆盖了循环、嵌套循环、常数、双变量、二分、递归等典型场景逐一分析。实例 1// 计算 func2 的时间复杂度voidfunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}分析第一个循环执行2N次while循环固定执行 10 次精确次数为2N 10。按大 O 推导2N 10 → 2N 1 → 2N → N。时间复杂度为O(N)。实例 2// 计算 func3 的时间复杂度voidfunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}System.out.println(count);}分析两个相互独立的循环分别执行M次和N次精确次数为M N。这里有两个相互独立的未知数谁也不能省略。时间复杂度为O(N M)。注意因为M、N规模关系未知不能简化为O(N)或O(M)。实例 3// 计算 func4 的时间复杂度voidfunc4(intN){intcount0;for(intk0;k100;k){count;}System.out.println(count);}分析循环固定执行 100 次与规模N无关是常数阶。按规则用常数 1 取代所有加法常数。时间复杂度为O(1)。实例 4冒泡排序// 计算 bubbleSort 的时间复杂度voidbubbleSort(int[]array){for(intendarray.length;end0;end--){booleansortedtrue;for(inti1;iend;i){if(array[i-1]array[i]){Swap(array,i-1,i);sortedfalse;}}if(sortedtrue){break;}}}分析这是一个带提前终止优化的冒泡排序。最好情况数组本身已经有序第一轮扫描后sorted仍为truebreak跳出基本操作约N次最坏情况数组完全逆序内层比较次数为(N-1) (N-2) ... 1 (N*(N-1))/2即O(N^2)。由于时间复杂度一般看最坏情况最终时间复杂度为O(N^2)。实例 5二分查找// 计算 binarySearch 的时间复杂度intbinarySearch(int[]array,intvalue){intbegin0;intendarray.length-1;while(beginend){intmidbegin((end-begin)/2);if(array[mid]value)beginmid1;elseif(array[mid]value)endmid-1;elsereturnmid;}return-1;}分析二分查找每比较一次就把待查找区间缩小一半。最好情况1 次就命中O(1)最坏情况一直对半切到只剩 1 个元素。为什么最坏是O(logN)想象折纸一张纸对折 1 次剩N/2层对折 2 次剩N/2/2 N/4层……对折x次后剩N / 2^x层。当N / 2^x 1时切完解得x log₂N。也就是二分每次排除掉一半不适合的值最坏需要log₂N次。最坏时间复杂度为O(logN)。说明在算法分析中logN默认表示底数为 2、真数为 N的对数有些地方也写作lgN。在大 O 表示下底数不同只差一个常数倍所以省略底数不影响量级。实例 6阶乘递归// 计算阶乘递归 factorial 的时间复杂度longfactorial(intN){returnN2?N:factorial(N-1)*N;}分析每次递归规模减 1递归链为factorial(N) → factorial(N-1) → ... → factorial(1)共递归调用N次每层只做常数次乘法。时间复杂度为O(N)。实例 7斐波那契递归// 计算斐波那契递归 fibonacci 的时间复杂度intfibonacci(intN){returnN2?N:fibonacci(N-1)fibonacci(N-2);}分析每次递归产生两个分支N-1和N-2递归展开是一棵二叉树节点总数随N呈指数级增长基本操作被递归了约2^N次。这正解释了一开始Fib(50)会卡死的原因——存在大量重复子问题。时间复杂度为O(2^N)。建议自己动手画出递归的调用栈帧二叉树能非常直观地看到指数爆炸是怎么来的。若想优化可用记忆化缓存中间结果或动态规划把O(2^N)降到O(N)。时间复杂度实例小结实例精确次数 / 行为时间复杂度实例 12N 10O(N)实例 2M N双变量O(N M)实例 3常数 100O(1)实例 4 冒泡最坏 (N*(N-1))/2O(N^2)实例 5 二分最坏 log₂NO(logN)实例 6 阶乘递归递归 N 次O(N)实例 7 斐波那契递归递归约 2^N 次O(2^N)四、空间复杂度4.1 空间复杂度的概念空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。需要特别强调的是空间复杂度算的不是程序占用了多少 bytes 的空间因为这个绝对数字本身意义不大且与数据类型、平台相关而是临时创建的变量的个数。空间复杂度的计算规则与时间复杂度基本类似同样使用大 O 渐进表示法。理解空间复杂度时要抓住两个关键只算额外/临时空间传入的参数、原本就存在的输入数据不计入只算算法运行中新开辟的空间常数个变量记作O(1)递归会开辟栈帧每一层栈帧占用的空间也要累加。4.2 常见空间复杂度计算举例实例 1冒泡排序// 计算 bubbleSort 的空间复杂度voidbubbleSort(int[]array){for(intendarray.length;end0;end--){booleansortedtrue;for(inti1;iend;i){if(array[i-1]array[i]){Swap(array,i-1,i);sortedfalse;}}if(sortedtrue){break;}}}分析排序全程只用了end、sorted、i等固定几个变量无论数组多大额外空间个数不变。空间复杂度为O(1)这类原地排序称为原地算法in-place。实例 2迭代法求斐波那契数组// 计算 fibonacci 的空间复杂度int[]fibonacci(intn){long[]fibArraynewlong[n1];fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;}分析这里new出了一个长度为n1的数组动态开辟了 N 个额外空间并且要把结果数组返回给调用者不能释放。空间复杂度为O(N)。实例 3阶乘递归// 计算阶乘递归 factorial 的空间复杂度longfactorial(intN){returnN2?N:factorial(N-1)*N;}分析递归调用了N次因此开辟了 N 个栈帧每个栈帧使用了常数个空间参数N、返回地址等。空间复杂度为O(N)。这也是递归的典型代价时间上换来了代码简洁空间上要付出与递归深度成正比的栈开销。空间复杂度实例小结实例额外空间来源空间复杂度实例 1 冒泡排序常数个临时变量O(1)实例 2 斐波那契数组动态开辟 N 个数组单元O(N)实例 3 阶乘递归递归 N 层栈帧 × 常数空间O(N)五、常见复杂度量级对比与总结把本文涉及的所有复杂度按从快到慢增长从慢到快排成一个量级阶梯方便记忆与对比O(1) O(logN) O(N) O(N*logN) O(N^2) O(2^N) O(N!) 常数阶 对数阶 线性阶 线性对数阶 平方阶 指数阶 阶乘阶O(1)常数阶运行时间与规模无关如实例 3 的固定 100 次循环。O(logN)对数阶每步规模减半二分查找是典型代表。O(N)线性阶一次遍历阶乘递归、单循环。O(N^2)平方阶嵌套循环冒泡、选择、插入排序等。O(2^N)指数阶二叉递归树未优化的斐波那契递归需警惕。核心记忆要点衡量算法好坏靠效率分为时间效率时间复杂度与空间效率空间复杂度当今硬件环境下更看重时间复杂度。时间复杂度 基本操作的执行次数用大 O 渐进表示法简化三步走常数换 1 → 保留最高阶 → 去最高阶系数。实际看最坏情况性能上界保证如数组顺序查找记O(N)。空间复杂度算的是临时变量个数而非字节数递归要累加栈帧空间。递归代码简洁但有栈空间代价且像斐波那契这种二叉递归会带来指数级时间爆炸遇到重复子问题应优先考虑记忆化 / 动态规划优化。把以上这套先看基本操作次数 → 用大 O 简化 → 关注最坏情况 → 顺带评估栈空间的流程练熟你就能在面试和实战中对任意一段代码快速给出它的时间与空间复杂度。