Java学习苦旅系列写到第八篇，前面聊了面向对象、集合框架、异常处理这些基础大件，这次我想聊聊一个很多人一听到就头疼、但其实完全没必要的概念——复杂度。不说虚的，这篇就是想让你看完之后，再遇到有人跟你讨论什么O(n)和O(log n)，你能心里不慌，甚至还能反问两句。先说说我自己的经历。我学Java那会儿，第一次接触算法相关的内容是在一本讲数据结构的书里，翻到“复杂度分析”那一章，满屏的数学符号和函数曲线，我直接跳过去了。后来写代码写多了，开始遇到程序跑得慢、内存飙高的问题，才意识到这个当时被我跳过的内容，恰恰是解决问题的基本工具。复杂度本质上不是什么高深的数学理论，它就像是给代码做了一次“体格检查”，衡量的是你的代码在数据规模变大之后，还能不能扛得住。这篇博文适合所有正在学Java的朋友，不管你是刚学完基础语法、准备往算法和数据结构方向深入，还是工作之后发现性能问题不知道怎么下手，都可以看看。我会尽量用实际代码和场景来拆解，不堆公式，把复杂度的思路讲透。1. 复杂度到底在衡量什么1.1 从一段Java代码说起先做一个最简单的实验。你写了一个Java方法，功能是从一个List里面找一个指定的数字，找到了就返回它的下标，找不到就返回-1。用最朴素的方式：public int findNumber(List<Integer> 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很小的时候，比如n=2，这些项加起来的差别很明显。但当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)这一级别，这个增长是非常可怕的，n=50的时候已经卡得没法看了。很多人写代码，一不留神写了个指数级复杂度的递归，还以为很优雅，实际上是大坑。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)，如果是一个ArrayList，get是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符号，不再觉得它是数学天书，而是能看到它背后描述的“代码规模增长时会发生什么”的朴素道理。勇于去分析手头代码的复杂度，你会发现，这其实是提升代码质量成本最低、回报最高的一种方式。
Java学习苦旅系列写到第八篇，前面聊了面向对象、集合框架、异常处理这些基础大件，这次我想聊聊一个很多人一听到就头疼、但其实完全没必要的概念——复杂度。不说虚的，这篇就是想让你看完之后，再遇到有人跟你讨论什么O(n)和O(log n)，你能心里不慌，甚至还能反问两句。先说说我自己的经历。我学Java那会儿，第一次接触算法相关的内容是在一本讲数据结构的书里，翻到“复杂度分析”那一章，满屏的数学符号和函数曲线，我直接跳过去了。后来写代码写多了，开始遇到程序跑得慢、内存飙高的问题，才意识到这个当时被我跳过的内容，恰恰是解决问题的基本工具。复杂度本质上不是什么高深的数学理论，它就像是给代码做了一次“体格检查”，衡量的是你的代码在数据规模变大之后，还能不能扛得住。这篇博文适合所有正在学Java的朋友，不管你是刚学完基础语法、准备往算法和数据结构方向深入，还是工作之后发现性能问题不知道怎么下手，都可以看看。我会尽量用实际代码和场景来拆解，不堆公式，把复杂度的思路讲透。1. 复杂度到底在衡量什么1.1 从一段Java代码说起先做一个最简单的实验。你写了一个Java方法，功能是从一个List里面找一个指定的数字，找到了就返回它的下标，找不到就返回-1。用最朴素的方式：public int findNumber(List<Integer> 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很小的时候，比如n=2，这些项加起来的差别很明显。但当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)这一级别，这个增长是非常可怕的，n=50的时候已经卡得没法看了。很多人写代码，一不留神写了个指数级复杂度的递归，还以为很优雅，实际上是大坑。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)，如果是一个ArrayList，get是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符号，不再觉得它是数学天书，而是能看到它背后描述的“代码规模增长时会发生什么”的朴素道理。勇于去分析手头代码的复杂度，你会发现，这其实是提升代码质量成本最低、回报最高的一种方式。