★ FEATURED ARTICLE Java学习苦旅系列写到第八篇前面聊了面向对象、集合框架、异常处理这些基础大件这次我想聊聊一个很多人一听到就头疼、但其实完全没必要的概念——复杂度。不说虚的这篇就是想让你看完之后再遇到有人跟你讨论什么O(n)和O(log n)你能心里不慌甚至还能反问两句。先说说我自己的经历。我学Java那会儿第一次接触算法相关的内容是在一本讲数据结构的书里翻到“复杂度分析”那一章满屏的数学符号和函数曲线我直接跳过去了。后来写代码写多了开始遇到程序跑得慢、内存飙高的问题才意识到这个当时被我跳过的内容恰恰是解决问题的基本工具。复杂度本质上不是什么高深的数学理论它就像是给代码做了一次“体格检查”衡量的是你的代码在数据规模变大之后还能不能扛得住。这篇博文适合所有正在学Java的朋友不管你是刚学完基础语法、准备往算法和数据结构方向深入还是工作之后发现性能问题不知道怎么下手都可以看看。我会尽量用实际代码和场景来拆解不堆公式把复杂度的思路讲透。1. 复杂度到底在衡量什么1.1 从一段Java代码说起先做一个最简单的实验。你写了一个Java方法功能是从一个List里面找一个指定的数字找到了就返回它的下标找不到就返回-1。用最朴素的方式public int findNumber(ListInteger list, int target) { for (int i 0; i list.size(); i) { if (list.get(i) target) { return i; } } return -1; }这段代码没什么特别的但问题来了如果list里面有10个元素它最多可能要看10次如果有100万个元素在最坏的情况下你要找的数在最后甚至不存在它就要看100万次。你会发现代码的执行时间跟数据规模之间存在一种“正相关”的关系。这就是复杂度要量化的问题。再往深一层想。同样是查找如果你面对的是一个已经排好序的数组用二分查找那情况完全不同。每次比较都可以把查找范围砍掉一半所以即便是100万个元素也只需要大概20次比较就能定位到目标。同一个问题两种解法在数据规模小的时候感觉不出差别一旦数据量上来就是毫秒级和秒级甚至分钟级的差别。复杂度的核心思想就是把这种“随着数据规模增长算法耗时或耗内存的增速”抽象成一个通用的衡量标准。它不是去算精确的运行时间——那会因为机器配置、JVM实现、输入数据分布不同而变化而是去看增长的“趋势”。拥有了这个趋势你就能在不运行代码的情况下大致判断一段逻辑的扩展性。1.2 时间复杂度和空间复杂度的直觉理解复杂度实际有两大维度时间复杂度和空间复杂度。这不难理解。时间复杂度衡量你的代码跑得快不快空间复杂度衡量你的代码占内存多不多。很多初学者只关注时间忽略空间但在真实的Java应用中比如一个高并发的服务端应用内存是宝贵的资源一个设计不当的缓存方案或者数据聚合逻辑完全可能把堆内存塞满引发频繁的GC甚至直接OOM。所以这两个维度要一起考虑。我想用一个生活的场景来帮助理解。假设让你整理1000本书有两种方案方案一每次从书堆里拿一本找到它应该在书架上的位置插进去方案二先把书全部搬到一张大桌子上分好类再一起放回书架。方案一省桌子空间但每次都要找位置费时间。方案二费桌子空间但整理过程可能更直截了当。复杂度的分析就是在做类似的权衡只是它把“费时间”和“费空间”的程度用数学方式描述出来了。在学习复杂度时一定不要把它和“实际运行时间”划等号。我在工作中跟人讨论代码优化时经常遇到一种误解有人说某个方法很慢因为“它执行了1000次循环”但另一个方法“只执行了10次循环”所以后者快。这种说法不完全对。如果你这10次循环里每次都在做文件IO而对方1000次循环只是简单的内存加法计算那实际运行时间可能是完成不同的结果。复杂度描述的是增长率不是绝对时间。2. 分析复杂度的实操方法2.1 大O记法的核心逻辑大O记法听起来很唬人但本质就是“忽略掉那些在规模变大之后影响不大的部分只留下主导趋势”。比如你有一段逻辑执行次数是3n^2 5n 8当n很小的时候比如n2这些项加起来的差别很明显。但当n是一百万的时候n^2这一项变成了一万亿级别而5n只有五百万8更是可以忽略不计。所以大O记法就记成 O(n^2)。这里有一个初学者容易困惑的点为什么要把常数系数也去掉。比如一个循环执行2n次为什么也记成O(n)不是应该更“慢”吗因为大O关注的是“增长趋势”2n和n一样都是线性增长数据量翻倍耗时也翻倍。系数只反映了具体的硬件或者JIT优化水平不是算法本身的特质。我们在用大O分析的时候默认是在比较同一种计算模型下的算法优劣而不是精确预测运行时间。大O还有一个容易被忽视的细节它分了很多种情形。我们常说的复杂度默认是“最坏情况”复杂度。比如在一个数组里找第n个元素不管数组多大只要通过下标访问都是一次操作时间复杂度是O(1)这没什么好分析的。但如果你在HashMap里查找元素最坏情况是哈希碰撞极其严重所有元素都落到同一个桶里查找退化成了O(n)而JDK在这个基础上做了优化当链表长度超过阈值时会转成红黑树于是最坏情况变成了O(log n)。所以讨论复杂度的时候要讲清楚是哪种情况否则容易产生误解。2.2 Java代码中常见的复杂度模式看代码看久了你会形成一种肌肉记忆看到某些代码结构心里大概就能浮现出对应的复杂度。我给你总结几种Java里最常见的模式。单层循环遍历整个数据集最典型的就是上面那个线性查找复杂度是O(n)。哪怕你用了增强for循环或者Java 8的Stream遍历本质上都是对整个集合过一次也是O(n)。要注意的是如果在循环体内部还调用了另一个完整的遍历逻辑比如在for循环里对一个List调用contains方法而contains底层就是线性扫描那复杂度就会叠加成O(n^2)。双层循环嵌套且每层都接近数据规模n这通常就是O(n^2)。经典的例子是冒泡排序for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { // 交换 } } }里层循环的次数虽然每次递减但总的操作次数约为 n^2/2所以还是O(n^2)。我在实际代码审查里见过很多这样的模式最典型的就是双重for循环求两个集合的交集。数据量小的时候没事数据量一变大这个方法的耗时就开始肉眼可见地增长。这时候就应该考虑用HashSet把其中一个集合装起来查找变成O(1)整体降到O(n)。还有一种很常见的模式是递归。递归的复杂度分析稍微绕一点但核心是看“一个递归调用里又产生了多少次新的递归调用”。比如常见的斐波那契数列朴素递归public long fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }每次调用会分裂成两个子调用形成了一个近似二叉树的结构所以时间复杂度是O(2^n)这一级别这个增长是非常可怕的n50的时候已经卡得没法看了。很多人写代码一不留神写了个指数级复杂度的递归还以为很优雅实际上是大坑。2.3 从代码到复杂度的一步步推导教你一个我常用的推导方法语句计数法。不需要特别严谨的数学只需要把一段代码当成若干条基本操作数一数在不同输入规模下这些基本操作的“总量”大概是多少。看这个例子public void printPairs(int[] arr) { for (int i 0; i arr.length; i) { for (int j i 1; j arr.length; j) { System.out.println(arr[i] , arr[j]); } } }外层循环执行了n次而内层循环在i取不同值的时候执行次数分别是n-1、n-2、...、1、0。加起来应该是n(n-1)/2。展开就是 (n^2 - n)/2。根据大O的规则取最高阶并去掉常数结果就是O(n^2)。这里有一点值得注意n的系数和低阶项都被忽略所以即便内层循环不是从0开始也不影响最终的量级判断。再来看一个更实际些的场景。你写一个方法入参是一个字符串数组方法内部先遍历一遍数组计算总长度然后又遍历一遍拼接结果public String buildString(String[] items) { int totalLen 0; for (String item : items) { totalLen item.length(); } StringBuilder sb new StringBuilder(totalLen); for (String item : items) { sb.append(item); } return sb.toString(); }两个循环是顺序关系不是嵌套关系所以复杂度是O(n)而不是O(n^2)。用上面说的大O定义看即使有两段操作总操作次数大约是2n仍属于线性增长。这里顺便说一个Java实战中的性能细节使用StringBuilder可以避免在循环中频繁创建新字符串对象。如果不预估容量直接append虽然时间复杂度在渐进意义下还是O(n)但实际运行时会付出更多的内存分配和拷贝代价。复杂度可以忽略常数真实性能不能。3. 常见复杂度对比与选择3.1 一张表看懂各量级我平时给团队新人进行代码走查培训时习惯先用一张表把常见复杂度量级铺开。因为有了全局视野后面遇到具体算法就不会慌。复杂度名称直观感受典型Java场景O(1)常数级无论数据多大操作次数固定数组按索引访问、HashMap无碰撞查询O(log n)对数级数据翻倍操作次数只增加一点点二分查找、TreeMap的查找O(n)线性级数据翻倍操作次数约翻倍遍历List、求最大值O(n log n)线性对数级比线性略慢但可接受快速排序、归并排序、Arrays.sortO(n^2)平方级数据增加耗时会快速上升冒泡排序、双层循环暴力查找O(2^n)指数级增长极快稍大的规模就不可用朴素递归的斐波那契说句实在话日常开发和面试中最常打交道的其实就是O(1)、O(log n)、O(n)、O(n log n)这几个量级。O(n^2)和O(2^n)通常是被优化的对象。你看到一段代码性能有问题第一反应就是看它能不能从n^2降到n log n甚至n。3.2 复杂度分析在集合框架中的实战体现Java的集合框架是复杂度分析的最佳练手素材。因为你在选择用哪个集合的时候本质上就是在做复杂度的取舍。我举几个高频对比。ArrayList和LinkedList的差异被讨论过很多次。ArrayList底层是数组所以按下标取元素是O(1)但在头部插入元素因为要移动后续所有元素是O(n)。LinkedList底层是双向链表头尾插入删除是O(1)但按下标查找是O(n)因为要沿着指针一个一个找。网上很多说法是“LinkedList插入快”这得看插在哪。如果是在中间位置插入光光是找到那个位置就已经O(n)了。在实际项目中我很少看到LinkedList有大展身手的场景大多数情况下ArrayList表现都足够好因为它的局部性更好CPU缓存命中率更高。再看HashMap和TreeMap。HashMap在理想情况下查询是O(1)但它的缺点是无序。如果你需要按照key的自然顺序遍历HashMap就无能为力了得用TreeMap它底层是红黑树查询和插入都是O(log n)。这个性能差异在数据量小的时候感觉不出来比如存100个元素log以2为底大约是7跟1差不太多。但是存100万个元素的时候HashMap一次操作可能只需要几次运算TreeMap需要大约20次差别就出来了。关于集合框架的选择我的一个习惯是默认用ArrayList和HashMap只有当明确的场景需求出现时比如需要排序功能、需要保持插入顺序才考虑其他替代品。复杂度只是选型的一个维度还有内存占用、并发安全等因素但复杂度是性价比最高的一个分析起点。4. 复杂度分析中的常见误区4.1 只看循环数量忽略循环内的操作很多时候我们分析复杂度轻易就给出了O(n^2)的结论但忽略了循环体内部的操作。比如下面这段代码for (int i 0; i n; i) { for (int j 0; j n; j) { if (list.get(j).equals(list.get(i))) { // do something } } }内层循环每次执行时用了list.get(j)和list.get(i)如果是一个ArrayListget是O(1)问题不大。但如果这里换成了LinkedList那么list.get(j)本身就是O(n)整个复杂度就上升到了O(n^3)。同一个双层循环结构因为底层数据结构不同复杂度出现了量级差异这在真实代码中是很容易被忽视的点。我审代码时特别留意循环体里是否有隐藏的集合操作、正则表达式调用、字符串的substring底层拷贝不同JDK版本实现不同、以及一些看似无害实则昂贵的工具类方法。这些都是“看起来只有一行实际消耗惊人”的典型。分析复杂度时一定要以“每一个循环迭代里做了什么”为单位而不是简单数循环层数。4.2 忽略常数系数和低阶项前面我们说了大O记法会忽略常数系数这在“理论分析”层面没有问题。但有些人把这个原则错误地延伸到工程实践里认为凡是O(n)的算法就一定比O(n^2)好这就不对了。举个实际场景你有一个长度很小的数组比如n总是小于10这时候一个写法简洁但复杂度为O(n^2)的暴力排序可能比一个实现复杂但复杂度为O(n log n)的快速排序还要快。因为在数据规模极小的情况下常数系数带来的开销可能占主导而复杂度分析恰恰掩盖了常数。我记得有一次优化一个内部工具方法从O(n^2)改成O(n)之后性能不但没提升反而变慢了。原因是原来的O(n^2)实现足够简单同时数据量几乎没有超过100而新方案引入了额外的数据结构初始化和更复杂的对象分配。这个案例给了我一个深刻的教训复杂度分析是帮我们判断“当数据规模变大时会发生什么”的它不是一切。真正的性能优化需要先进行测量用数据说话。复杂度分析的价值在于在写代码的时候就能排除掉那些明显会在大数据量下崩掉的方案。4.3 递归与均摊复杂度的困惑递归的复杂度很容易算错。初学者总觉得“既然递归调用了一次复杂度应该还好”。实际上要看分支数。如果一个递归方法里调用了两次自身每次规模只减少常数最后通常是指数级复杂度。前面提到的斐波那契就是一个反面教材。但还有一类情况很有意思均摊复杂度。Java里的ArrayList动态扩容就是一个典型的均摊分析例子。每次容量不够了就扩容为原来的1.5倍需要把旧数组的元素拷贝到新数组。单看某次扩容操作是O(n)的但如果把多次add操作一起看扩容发生得越来越少把拷贝的总代价均摊到每一次add上得到的结果仍然是O(1)。这意味着从整体趋势看你往ArrayList里逐个添加元素并不会因为偶尔的扩容而让总代价变成O(n^2)。这个结论在实际使用中非常有意义。理解均摊复杂度对阅读JDK源码也有帮助。比如ConcurrentHashMap的某些操作或者在实现自定义集合类时你可能会遇到“偶尔开销大、平时开销小”的设计用均摊的思路才能正确评估它的整体表现。初次接触这个概念的读者可能会觉得难但你可以把它理解为“长期平均账单”而不是紧盯某一次扣款。5. 性能问题定位与优化思路5.1 用复杂度思维定位Java应用卡顿我经常被问到“线上Java服务突然变慢怎么排查”排查的手段有很多线程dump、内存分析、JProfiler、Arthas……但在这些工具之下复杂度思维是第一层过滤网。你拿到一个可疑的方法先读代码快速估算各个分支的复杂度找出那个在数据规模变大时最可能出现问题的瓶颈。有一次我定位一个接口超时问题一开始代码逻辑非常长不好直接看出问题。后来我把关键路径抽出来发现里面有一处对List的contains调用出现在一个for循环中。List的大小在正常情况下只有几百问题表现不明显但有一个特殊入口会让这个List变成几万甚至几十万于是这段“正常”的代码就从O(n)变成了O(n^2)接口响应时间直接飙升。修复方式很简单把List换成HashSet一次性解决了问题。这个过程基本不需要复杂的性能剖析工具复杂度分析直接锁定了问题。所以我的建议是写Java代码前先花几秒钟问自己三个问题这个操作的数据规模最坏可能有多大这个循环体里会不会嵌套了另一个线性操作我选择的数据结构在最坏情况下的复杂度是多少这三个问题想清楚很多性能坑都可以提前避开。5.2 给Java初学者的复杂度练习建议如果你正在学Java想把复杂度的感觉培养起来我建议不要只抱着理论书啃而是多做一些“对比实验”。挑一个经典问题用两种或三种不同的解法写出来然后对比它们的复杂度再实际测试不同数据规模下的运行时间。我给的练习路径是这样的第一步找一个简单问题比如“判断两个数组是否有交集”。分别写暴力双层循环版本、用HashSet的版本、先排序再用双指针的版本然后分析各自的复杂度。第二步写一个二分查找的递归实现和迭代实现体会O(log n)这个概念从数学到代码的落地过程。第三步用朴素递归和带备忘录的递归分别实现斐波那契你会看到O(2^n)和O(n)的差距有多么惊人这也是理解动态规划的第一步。练习时可以用一个简单的计时工具来辅助观察long start System.nanoTime(); // 调用被测方法 long end System.nanoTime(); System.out.println(耗时: (end - start) / 1000_000.0 ms);但务必要记得对很小的数据规模反复测试结果里混着JIT预热、系统调度等噪声不要只看一次运行结果就下结论。想要观察复杂度趋势最好把数据规模拉大到至少一万、十万、百万这个级别然后看耗时的增长是否符合理论预期。我自己在给新人演示时最喜欢用斐波那契——同样的输入几种写法跑出来的耗时差异比任何理论讲解都更有冲击力。5.3 常见问题速查与避坑技巧做一个小的速查表把我这几年来常遇到的复杂度相关问题和解决方向整理出来。症状表现可能的复杂度原因常用解决思路接口在数据量稍微增大后明显变慢循环内调用contains、indexOf等线性操作用HashSet或HashMap转移成O(1)查询字符串拼接性能差不合预期循环中使用字符串加号拼接触发了多次字符串拷贝用StringBuilder必要时预估初始容量大规模数据下树结构相关操作偏慢可能使用了不平衡的二叉搜索树或数据分布不佳改用红黑树结构的TreeMap或调整hash函数递归方法在大输入时栈溢出或极慢递归分支过多复杂度达到指数级或栈深度过深改迭代显式栈或对重复子问题做备忘录排序很慢误用O(n^2)排序且数据量大改用Arrays.sort或Collections.sort这类优化实现最后再说一个我自己踩过的坑。有一段时间我写了一个工具方法看起来是“简洁优雅”的链式Stream操作满足了业务需求但后来在处理较大数据集时慢得离谱。原因是我在Stream的filter里嵌套了一个对集合的线性查找本质上和双层循环一样。Stream能让代码更短但不会自动改变复杂度。所以在享受函数式编程带来的表达简洁时复杂度分析这根弦不能松。这篇“不复杂的复杂度”就先聊到这里。如果你正在学Java希望你下次再看到一个大O符号不再觉得它是数学天书而是能看到它背后描述的“代码规模增长时会发生什么”的朴素道理。勇于去分析手头代码的复杂度你会发现这其实是提升代码质量成本最低、回报最高的一种方式。
阅读完成 · 觉得有帮助？
