第八篇了。前面我们用了几篇的篇幅，把Java的语法、面向对象、集合框架、I/O、异常这些基础内容过了一遍。今天想插一个看起来不太一样、但实际非常重要的主题——复杂度分析。为什么在这个节点讲它？因为我发现很多人在前面那些内容学完之后，开始刷算法题或者读源码时，经常被黑话拦住：你这代码是O(n²)的，数据规模一大就得超时；这个接口是O(1)的，放心随便用。什么O不O的，到底在说什么？我刚开始接触的时候也觉得这是搞算法的人用来唬人的词，后来才意识到，这是个特别朴素、特别有用的工具。这篇就想用最不吓人的方式，把“不复杂的复杂度”讲清楚，让后面的学习之路顺畅一点。这篇内容适合谁看？正在学Java基础、准备开始刷题或者看框架源码的人；也适合那些已经工作一两年、写代码时隐约感觉“自己代码好像很慢但不知道为什么”的人。看完之后，你会获得一个一眼扫过代码就能大致判断它耗不耗时的能力——这个能力在笔试、面试、排查线上性能问题的时候，都特别值钱。1. 复杂度到底在说什么1.1 为什么不能直接跑一下测耗时刚学编程的时候，我有一段时间觉得复杂度分析很鸡肋：想知道代码快不快，直接跑一下，看它花了多少毫秒不就行了？后来被现实教育了。同样的代码，在同事的高配机器上跑，可能只要0.2秒；换到我那个风扇呼呼转的老笔记本上，可能就要0.8秒。同样一台机器，CPU占有率不同、后台进程不同，跑出来的时间也不一样。更麻烦的是，同样的代码喂不同的数据，耗时差异巨大——这个差异有时候不是几倍，而是几百上千倍。复杂度分析解决的就是这个问题。它把“代码跑得有多快”这个事情，跟机器型号、语言实现、编译器优化全部剥离开，只看一个东西：当输入的数据规模n不断变大的时候，代码的执行时间是怎么跟着变的。这是一种“只看趋势、不看绝对值”的衡量方式。打个比方，你评价一个人跑步快不快，不会只看他在某一天某个路段跑了多少秒，而是看他在不同距离下配速稳不稳定——复杂度分析的思路也类似。所以复杂度分析不是用来替代实际跑程序的，它是用来在没跑程序之前，就能大致预判这代码在数据变大时行不行的工具。1.2 大O表示法：不追求精确，只看趋势复杂度分析通常用大O表示法来描述，比如O(1)、O(n)、O(n²)。第一次看到这些符号的人容易懵，其实它背后的数学定义虽然严谨，但落到应用层面就是一个很朴素的规则：忽略常数系数，忽略低阶项，只保留随着n增长得最快的那个部分。举个例子，假设一段代码的执行总次数是 T(n) = 3n² + 2n + 100。当n=10的时候，三项分别是300、20、100，第一项确实是主角；当n=1000的时候，三项分别是3000000、2000、100，后面两项基本可以忽略。所以这段代码的时间复杂度就是O(n²)。为什么可以这么粗粒度？因为复杂度分析要回答的从来不是“这段代码到底执行了多少条指令”，而是“当数据规模翻倍的时候，它的开销大概翻几倍”。如果是O(n)的代码，数据翻倍，开销大致翻倍；如果是O(n²)，数据翻倍，开销翻四倍；如果是O(1)，数据再怎么翻倍，开销纹丝不动。这种“缩放特性”才是我们真正关心的事。注意：大O本质上描述的是上界，也就是最坏情况下算法的增长速度。但日常交流中大家就用它来表示算法的大致量级，不用太较真数学定义。2. 七个常见复杂度量级复杂度不是越多越好记，实际开发里常见的就是七个量级。从快到慢分别是：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)、O(2ⁿ)、O(n!)。下面一个一个说，每个都给Java代码示例和识别特征。2.1 O(1)：常数级，最理想的状态O(1)的含义是，无论数据规模n是多少，执行时间基本不变。注意不是只执行一次，而是执行次数跟n无关，可能执行1次，可能执行100次，但这100次是固定的，n再大也不会变。典型的O(1)代码就是数组按下标访问、HashMap按key取value：int[] arr = new int[1000000]; // 不管数组多大，取某个下标的值，时间都是基本固定的 int val = arr[500000]; Map<String, Integer> map = new HashMap<>(); map.put("key", 100); // 理想情况下，get操作也是O(1) int num = map.get("key");为什么数组按下标访问是O(1)？因为数组在内存里是一段连续的空间，知道起始地址和下标，直接通过“起始地址 + 下标 × 元素大小”算出目标位置，一步到位，不需要挨个找。就像电影院座位都是连号的，你拿着第100排的票，直接走过去就行，不用从第1排开始挨个找。2.2 O(logn)：对数级，增长极其缓慢O(logn)是仅次于O(1)的优秀复杂度，而且它非常反直觉——n从1000涨到100万，logn只从10涨到20。之所以这么慢，核心就是“每次操作都把问题规模减半或者成倍放大”。最经典的例子是二分查找：// 在有序数组中查找target，返回下标 int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }每次循环，搜索范围就缩小一半：n → n/2 → n/4 → … → 1。一共需要多少次？假设需要k次，那 n / 2^k = 1，也就是 2^k = n，k = log₂n。所以复杂度是O(logn)。识别O(logn)代码有个很实用的标志：循环里的变量不是一次加1，而是每次乘以2或者除以2。比如：int i = 1; while (i < n) { i = i * 2; // 每次翻倍，循环次数大约是log2(n) }日常开发里，二分查找、平衡二叉树的查找、某些分治算法的合并过程，都是O(logn)的级别。2.3 O(n)：线性级，最常见的复杂度O(n)就是遍历一遍所有数据，数据量翻倍，时间也翻倍。这是最直观的复杂度，一眼就能认出来：一层循环，循环变量从0走到n。int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; }O(n)在开发里到处都是：遍历数组、遍历List、遍历Map的keySet、统计字符串长度、读取文件的所有行……凡是“把每个元素都过一遍”的操作，基本都是O(n)。这里顺便多说一句，很多人以为一层循环就是O(n)，这基本对，但要注意一个例外：如果循环里调用的方法本身不是O(1)的，那整体复杂度就要乘上那个方法的复杂度。比如这样一段代码：List<String> list = getList(); // 长度n for (int i = 0; i < n; i++) { boolean contains = list.contains(someItem); // contains内部还要遍历一次，是O(n) }外层O(n)、内层O(n)，整体就变成了O(n²)。这是日常开发里非常容易踩的坑，后面专门开一节讲。2.4 O(nlogn)：线性对数级，排序算法的分水岭O(nlogn)看起来有点怪，但它其实是很多优秀算法的标志性复杂度，典型代表就是快速排序、归并排序、堆排序这些主流排序算法。这个复杂度怎么来的？通常是“外层做O(logn)次拆分，每次合并过程要处理O(n)个元素”。以归并排序为例：数组每次对半拆，能拆logn层；每一层合并的时候，都要把当前层所有元素过一遍，总共n个元素。所以总工作量就是 n × logn。在Java里，你几乎天天在用O(nlogn)的算法而不自知：Arrays.sort(arr); // 底层是双轴快速排序，平均O(nlogn) Collections.sort(list); // 底层是TimSort，O(nlogn) list.stream().sorted().collect(Collectors.toList()); // 也是O(nlogn)如果代码里出现“外层循环n次、内层循环每次减半”的结构，那大概率也是O(nlogn)。比如：int count = 0; for (int i = 0; i < n; i++) { int j = 1; while (j < n) { j = j * 2; count++; } }外层要执行n次，内层每次执行logn次，乘起来就是O(nlogn)。2.5 O(n²)：平方级，要警惕的复杂度O(n²)就是两层循环嵌套，每层都跟n相关。数据规模小的时候感觉不到问题，但只要n上了万级别，O(n²)的代码就开始让人着急了。// 冒泡排序，经典O(n²) for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } }为什么O(n²)危险？因为n的增长对耗时的放大是指数级的平方放大。n=1000时，要执行大约50万次比较；n=10000时，就要大约5000万次；n=100000时，直接50亿次——不管机器多快，这个量级都扛不住。还有一种O(n³)甚至O(n⁴)的，写法就是三层、四层嵌套循环，常见于某些矩阵运算、暴力枚举组合的场景。这类复杂度在数据规模稍大时几乎不可用，通常需要寻找更优的算法替代。2.6 O(2ⁿ)与O(n!)：指数级和阶乘级，基本上不可用这两个复杂度是“算法地狱”级别的，数据规模稍微大一点就无解。O(2ⁿ)的典型代表是递归计算斐波那契数列的朴素写法：int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }为什么这个这么慢？每次调用fib(n)会分裂成两个子调用，每个子调用又分裂成两个，整个递归树像爆炸一样扩展。n=30的时候大约要计算上千万次，n=50的时候已经是个天文数字。O(n!)就更恐怖了，典型是暴力求解旅行商问题、列出所有排列。n=10是3628800种排列，n=12就接近4.8亿。这种复杂度在工程上基本意味着“换个思路，别硬算”。遇到O(2ⁿ)或O(n!)，通常的优化方向是动态规划、回溯剪枝或者启发式算法，核心思想都是“避免重复计算、尽量剪掉不可能的分支”。提示：看到递归代码，先别急着判断它是O(n)还是O(2ⁿ)。画出递归树就知道，一棵树有多少节点，大致就是多少次调用。3. Java代码里的复杂度实战3.1 先看三段代码，你来判断光看理论容易飘，记住“不复杂”的最好方式就是动手分析。下面三段代码，先别往下看答案，自己在心里判断一下每段的时间复杂度。代码一：int sum = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { sum += (i * j); } }代码二：int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 100; j++) { count++; } }代码三：public int find(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; }答案分别是：O(n²)、O(n)、O(n)——注意第三段这里有个悬念，稍后细讲。代码一的内层循环执行次数是1+2+3+…+n，也就是n(n+1)/2，保留最高阶就是O(n²)。代码二的内层循环是固定的100次，跟n无关，所以总次数是100n，也就是O(n)。很多人一看“两个for嵌套”就条件反射写O(n²)，其实内层是常数次，本质就只是O(n)。代码三有意思的地方在于，它最好情况是目标刚好在第一个位置，O(1)；最坏情况是目标不在数组里或者排在最后一位，O(n)。这就是下面要讲的“一个算法有多个复杂度”的问题。3.2 复杂度分析的三条基本法则分析复杂度不用每次都从零推导，记住三条法则就够了：加法法则：总复杂度等于量级最大的那段代码的复杂度。如果一段代码先做一个O(n)的遍历，又做一个O(logn)的查找，总复杂度就是O(n)。原因很简单，当n很大的时候，O(n)是绝对的主角。乘法法则：嵌套代码的复杂度等于内外层代码复杂度的乘积。外层循环O(n)，内层循环O(logn)，整体O(nlogn)；外层O(n)，内层O(n)，整体O(n²)。这个跟数学里的乘法一样直觉。只关注循环次数最多的那段代码。常见的组合拳是：前面有一段O(1)的初始化，中间有一段O(n)的处理，最后有一段O(n²)的输出——直接看O(n²)那段就好。这三条法则看起来简单，但真正常被问到的坑在于：有人会把“加法法则”理解成“把所有复杂度加起来”，其实应该是“取最大”。比如一段代码先做O(n²)的排序，再做O(n)的遍历，复杂度是O(n²)而不是O(n²+n)——这在增长趋势上没有任何区别。3.3 递归的复杂度怎么算递归的复杂度比迭代稍微绕一点，很多人在递归上栽跟头。用一个不算严谨但很好用的思路：递归复杂度 = 递归深度 × 每次递归内的时间复杂度。还是用斐波那契那个例子。fib(n)会调用fib(n-1)和fib(n-2)，这两个又各自继续分裂，所以递归深度大约是n，但每一层调用的次数是指数级增长的。这时候“递归深度 × 每次递归内的时间复杂度”这套公式就不太适用了，因为它算的是“递归链单条路径”的开销，而实际上每一层都有大量分支。正确的方法是看递归树：fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ └── fib(1) │ └── fib(2) └── fib(3) ├── fib(2) └── fib(1)每往下一层，节点数翻倍，树的总节点数大约是2ⁿ量级，所以复杂度O(2ⁿ)。为什么很多时候我们觉得“好像不太慢”？因为n一旦超过40，慢得就非常明显，机器扛不住指数爆炸。多提一句递归的空间复杂度。递归过程中每次调用都在系统调用栈上压入一层，递归深度是多少，栈空间就是多少。所以fib(n)的空间复杂度是O(n)，不是O(1)。很多人只算时间不算空间，结果在递归深层级时遇到栈溢出。3.4 空间复杂度：别只盯着时间看前面一直在说时间，但空间复杂度同样重要，它衡量的是算法运行需要的额外内存空间。分析方法和时间复杂度基本一致，只是把“执行次数换成了内存占用”。最常见的是O(1)：只用了几个临时变量，不随数据规模变化。比如交换两个数的值、单层遍历计数器这些。O(n)：需要额外开一个跟输入规模等长的数组、集合或者字符串。比如：// 把数组每个元素取绝对值，放到新数组里 int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = Math.abs(arr[i]); }这段代码的时间是O(n)，额外空间也是O(n)。O(n²)：二维数组、矩阵的存储，比如n×n的二维数组。空间复杂度有个常见的“交易”思维：以空间换时间。HashMap的O(1)查找背后是哈希表占用额外内存；缓存中间结果的动态规划也是典型空间换时间。实际开发里要平衡着来：内存本来就很紧张的时候，就不能一味追求时间最优。提示：Java里分析空间复杂度时，要注意你创建的容器真正的容量和实际使用量的区别。ArrayList扩容到capacity=16但size=3，实际额外空间按size算才合理。4. 最好、最坏、平均、均摊复杂度4.1 同一个算法，为什么有三个复杂度回到代码三那个例子：一个循环查找数组中的目标值。目标可能出现在第一个位置（最好情况O(1)），可能出现在最后一个位置或者根本不存在（最坏情况O(n)）。如果面试官问“这段代码复杂度是多少”，只回答O(n)不够完整——最好情况O(1)、最坏情况O(n)，这才是完整答案。为什么要有最好和最坏之分？因为同样的代码，在不同的数据分布下表现完全不同。最典型的例子是快速排序：平均情况下O(nlogn)，但如果数据本身已经有序且每次选的基准值都很倒霉，会退化到O(n²)。如果你在技术讨论里只说“快排是O(nlogn)”，其实不够严谨，要说“平均O(nlogn)、最坏O(n²)”。理解最好、最坏复杂度的关键，是要意识到“复杂度描述的是算法在什么场景下的表现”。最好情况给的是下限感知，最坏情况给的是安全底线。平时做技术方案的时候，我习惯先看最坏情况能不能接受，因为它决定了系统的稳定性。4.2 平均情况复杂度：加权平均的产物最好、最坏往往比较极端，日常更关心的是平均情况。拿查找数组来说，如果目标值一定存在，并且出现在每个位置的概率都相同，那期望的查找次数是：(1 + 2 + 3 + … + n) / n = (n+1) / 2去掉常数和低阶项，平均复杂度就是O(n)。对于大多数遍历类查找算法，平均和最坏都是O(n)，差别不大。但有些算法的平均复杂度需要认真算一下概率分布，比如哈希表的查找，平均O(1)，最坏O(n)——前提是哈希函数设计得当、冲突控制良好。如果你知道数据分布不均匀，那就要按真实分布去算，而不是默认“均匀”。4.3 均摊复杂度：一个让面试官眼前一亮的词均摊复杂度是最好/最坏/平均之后第四个重要概念，也是容易混淆的一个。它的场景是：大多数操作都是低开销的，偶尔有高开销的操作，但这高开销操作不是每次都发生。把高开销的成本分摊到所有操作上，整体的复杂度并不高。最经典的Java例子是ArrayList的add操作。List<Integer> list = new ArrayList<>(); // 初始容量10 for (int i = 0; i < n; i++) { list.add(i); }大多数情况下add只是往数组末尾放一个元素，O(1)。但当元素数量超过当前容量时，ArrayList需要扩容：申请一个更大的新数组，把旧数组所有元素拷贝过去。这一步是O(n)的。问题是，扩容不是每次都发生。每次扩容后容量大约变为原来的1.5倍，所以之后再插入很多元素都不需要扩容。把偶尔一次O(n)的拷贝成本，平摊到n次add操作上，每次add的均摊成本还是O(1)。我见过不少人在讨论ArrayList和LinkedList时，只说“ArrayList的add是O(1)，LinkedList的add是O(1)”，其实ArrayList的add更应该描述为“均摊O(1)”。别小看这个区别，它在设计高并发写库、批量插入场景时有实际意义：如果没意识到扩容会有单次O(n)的尖峰，你可能会被某个瞬间的卡顿打个措手不及。注意：均摊复杂度和平均复杂度不是一回事，很多讲复杂度的文章混着说。平均复杂度是针对“不同输入数据”的加权平均；均摊复杂度是针对“同一数据结构连续操作”的成本分摊。一个是数据维度，一个是时间维度。5. 复杂度分析在Java开发中的应用5.1 集合框架的复杂度对照表Java集合框架是分析复杂度最实用的练兵场，因为底层实现决定了接口的性能。我把常用集合的关键操作复杂度整理成一张表：集合类查询/查找插入删除备注ArrayListget: O(1)，contains: O(n)尾部add: 均摊O(1)，中间add: O(n)尾部remove: O(1)，中间remove: O(n)底层是可变数组LinkedListget: O(n)，contains: O(n)头部add: O(1)，尾部add: O(1)已知节点删除: O(1)底层是双向链表HashMapget: 平均O(1)，最坏O(n)put: 平均O(1)，最坏O(n)remove: 平均O(1)Java 8后冲突长链表会转红黑树TreeMapget: O(logn)put: O(logn)remove: O(logn)底层红黑树，有序HashSetcontains: 平均O(1)add: 平均O(1)remove: 平均O(1)底层是HashMapPriorityQueuepeek: O(1)offer: O(logn)poll: O(logn)底层二叉堆这张表值得反复看几遍。它解释了非常多日常开发中“奇怪”的现象：明明用List.contains判断是否存在，数据量一涨就慢得离谱；为什么明明LinkedList添加元素看起来方便，实际在中间大量插入时反而比ArrayList慢（因为要遍历找到插入位置）。5.2 日常开发里的复杂度陷阱这里整理几个我见过很多次的真实踩坑场景，每个都值得记住。陷阱一：在循环里调用contains。这个前面提过，本质是外层O(n)乘上内层O(n)，变成O(n²)。如果集合里元素比较多，这段代码会肉眼可见地越来越慢。解决办法是改用HashSet辅助判断，把contains从O(n)变成O(1)。陷阱二：循环里用+拼接字符串。很多人以为字符串拼接很简单：String result = ""; for (int i = 0; i < n; i++) { result = result + data[i]; }Java里String是不可变对象，每次拼接都要创建一个新字符串，并把旧字符串内容整体拷贝过去。这段代码的复杂度是O(n²)。数据量小看不出来，字符串一长就非常慢。正确做法是用StringBuilder，它的append在大多数情况下是O(1)均摊，整体复杂度O(n)。陷阱三：遍历Map时反复get。有人习惯这样写：for (String key : map.keySet()) { Integer value = map.get(key); // 又做了一次哈希查找 }每次get都是O(1)，本身没问题，但既然已经拿到了key，直接遍历entrySet拿value不香吗？省掉了每次重新哈希的开销。复杂度没变，但常数小很多。复杂度分析的是“量级”，但实际优化时“常数”也不能完全无视。经验：复杂度分析管的是“数量级”，常数优化管的是“实际体验”。两者都要看。数据规模大时先解决复杂度问题，数据规模小时先优化常数。5.3 复杂度相同，性能未必相同还要破除一个迷信：O(1)一定比O(n)快、O(nlogn)一定比O(n²)快。不是的。复杂度描述的是“趋势”，不描述“绝对值”。一个高性能的O(n)算法可能比一个实现很烂的O(nlogn)算法，在小数据规模上跑得更快；甚至在很大的数据规模上，如果O(nlogn)那个算法有巨大的常数系数，也可能干不过常数很小的O(n)算法。举个例子，数组顺序查找是O(n)，但如果数据量只有几十个，它查找起来一点都不慢；而一个构造复杂的索引结构虽然是O(logn)，但构建索引本身可能就要花很大的开销。另外，CPU缓存、内存访问局部性、JIT编译优化这些都会影响实际耗时。复杂度分析解决的是“会不会随着数据规模增长而失控”的数学问题，实际性能还要靠benchmark来验证。所以在面试或评审代码时，讨论“量级是否合理”是第一步；真正上生产之前，用实际数据压测是第二步。两步不能互相替代。6. 常见问题与排查技巧实录6.1 初学阶段最常见的几个误判误判一：看到两个for嵌套就写O(n²)。如果内层循环次数是固定的、不随n变化，那整体是O(n)。这个判断方法前面说过，这里再强调一次：嵌套本身不重要，内层是否与n相关才重要。误判二：把一个for循环里的方法调用当作O(1)。写代码时容易忘记自己调用的方法也不是免费的。list.contains()、String.indexOf()、数组的Arrays.copyOf()，这些都有自己的复杂度，要一层一层看进去。误判三：忽略递归栈空间。时间复杂度算对了，空间复杂度总写O(1)。递归函数每调用一次，系统就要压一层栈，空间至少是O(递归深度)。误判四：把数据规模看成常数。有些代码在本地测试时没问题，一上线上就卡顿，就是因为测试数据规模太小，掩盖了复杂度问题。分析复杂度时要假设n很大，甚至可以画一画n=10万、100万时会发生什么。6.2 面试笔试中怎么快速判断复杂度刷题或者面试时，经常需要在几秒内给出复杂度估算。我总结了一个经验流程：先看数据规模。如果题目说n最大10^5，那你脑子里要有数：O(n²)意味着大约10^10次操作，基本不可行；O(nlogn)意味着大约1.7×10^6次操作，可行。如果n最大100，那O(n²)、甚至O(n³)都完全没问题。数据规模是复杂度选型的硬约束。再看代码结构。一个循环一层层往下剥：外层是什么循环，内层变量怎么变化，中间有没有break、continue、提前return，有没有调用其他方法。把这些都用前面的三条法则组装起来。最后再确认最坏情况的合理性。面试官问复杂度时，默认问的是最坏复杂度；如果能补充最好情况和均摊情况，会显得你的分析更完整。6.3 我自己的学习心得说回这篇的标题——“不复杂的复杂度”。我特别理解为什么有人觉得它复杂，因为学校里的讲法经常从数学定义开始，上来就是渐进符号、紧致界、主定理，把人吓得够呛。但你如果真的每天写代码，就会慢慢发现复杂度根本不是用来“计算”的，而是用来“感知”的。写一个循环的时候，感觉一下这个循环会跑多少遍；写递归的时候，画一下递归树长什么样；选数据结构的时候，想想最常用的操作大概什么代价——这些感觉建立起来之后，复杂度就变成了一种本能，你真的不需要背任何公式。最后再分享一个特别实用的小技巧：分析一个不熟悉的工具类或框架方法时，不用去翻源码，最有效的方式是直接看它的JavaDoc，很多JDK方法都会标注时间复杂度；如果没有标注，就去搜一下它内部的实现结构，是数组、链表还是哈希表，基本就能猜个大概。这个方法帮我快速理解了很多类库的“性能底色”，强烈推荐你也试试。
第八篇了。前面我们用了几篇的篇幅，把Java的语法、面向对象、集合框架、I/O、异常这些基础内容过了一遍。今天想插一个看起来不太一样、但实际非常重要的主题——复杂度分析。为什么在这个节点讲它？因为我发现很多人在前面那些内容学完之后，开始刷算法题或者读源码时，经常被黑话拦住：你这代码是O(n²)的，数据规模一大就得超时；这个接口是O(1)的，放心随便用。什么O不O的，到底在说什么？我刚开始接触的时候也觉得这是搞算法的人用来唬人的词，后来才意识到，这是个特别朴素、特别有用的工具。这篇就想用最不吓人的方式，把“不复杂的复杂度”讲清楚，让后面的学习之路顺畅一点。这篇内容适合谁看？正在学Java基础、准备开始刷题或者看框架源码的人；也适合那些已经工作一两年、写代码时隐约感觉“自己代码好像很慢但不知道为什么”的人。看完之后，你会获得一个一眼扫过代码就能大致判断它耗不耗时的能力——这个能力在笔试、面试、排查线上性能问题的时候，都特别值钱。1. 复杂度到底在说什么1.1 为什么不能直接跑一下测耗时刚学编程的时候，我有一段时间觉得复杂度分析很鸡肋：想知道代码快不快，直接跑一下，看它花了多少毫秒不就行了？后来被现实教育了。同样的代码，在同事的高配机器上跑，可能只要0.2秒；换到我那个风扇呼呼转的老笔记本上，可能就要0.8秒。同样一台机器，CPU占有率不同、后台进程不同，跑出来的时间也不一样。更麻烦的是，同样的代码喂不同的数据，耗时差异巨大——这个差异有时候不是几倍，而是几百上千倍。复杂度分析解决的就是这个问题。它把“代码跑得有多快”这个事情，跟机器型号、语言实现、编译器优化全部剥离开，只看一个东西：当输入的数据规模n不断变大的时候，代码的执行时间是怎么跟着变的。这是一种“只看趋势、不看绝对值”的衡量方式。打个比方，你评价一个人跑步快不快，不会只看他在某一天某个路段跑了多少秒，而是看他在不同距离下配速稳不稳定——复杂度分析的思路也类似。所以复杂度分析不是用来替代实际跑程序的，它是用来在没跑程序之前，就能大致预判这代码在数据变大时行不行的工具。1.2 大O表示法：不追求精确，只看趋势复杂度分析通常用大O表示法来描述，比如O(1)、O(n)、O(n²)。第一次看到这些符号的人容易懵，其实它背后的数学定义虽然严谨，但落到应用层面就是一个很朴素的规则：忽略常数系数，忽略低阶项，只保留随着n增长得最快的那个部分。举个例子，假设一段代码的执行总次数是 T(n) = 3n² + 2n + 100。当n=10的时候，三项分别是300、20、100，第一项确实是主角；当n=1000的时候，三项分别是3000000、2000、100，后面两项基本可以忽略。所以这段代码的时间复杂度就是O(n²)。为什么可以这么粗粒度？因为复杂度分析要回答的从来不是“这段代码到底执行了多少条指令”，而是“当数据规模翻倍的时候，它的开销大概翻几倍”。如果是O(n)的代码，数据翻倍，开销大致翻倍；如果是O(n²)，数据翻倍，开销翻四倍；如果是O(1)，数据再怎么翻倍，开销纹丝不动。这种“缩放特性”才是我们真正关心的事。注意：大O本质上描述的是上界，也就是最坏情况下算法的增长速度。但日常交流中大家就用它来表示算法的大致量级，不用太较真数学定义。2. 七个常见复杂度量级复杂度不是越多越好记，实际开发里常见的就是七个量级。从快到慢分别是：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)、O(2ⁿ)、O(n!)。下面一个一个说，每个都给Java代码示例和识别特征。2.1 O(1)：常数级，最理想的状态O(1)的含义是，无论数据规模n是多少，执行时间基本不变。注意不是只执行一次，而是执行次数跟n无关，可能执行1次，可能执行100次，但这100次是固定的，n再大也不会变。典型的O(1)代码就是数组按下标访问、HashMap按key取value：int[] arr = new int[1000000]; // 不管数组多大，取某个下标的值，时间都是基本固定的 int val = arr[500000]; Map<String, Integer> map = new HashMap<>(); map.put("key", 100); // 理想情况下，get操作也是O(1) int num = map.get("key");为什么数组按下标访问是O(1)？因为数组在内存里是一段连续的空间，知道起始地址和下标，直接通过“起始地址 + 下标 × 元素大小”算出目标位置，一步到位，不需要挨个找。就像电影院座位都是连号的，你拿着第100排的票，直接走过去就行，不用从第1排开始挨个找。2.2 O(logn)：对数级，增长极其缓慢O(logn)是仅次于O(1)的优秀复杂度，而且它非常反直觉——n从1000涨到100万，logn只从10涨到20。之所以这么慢，核心就是“每次操作都把问题规模减半或者成倍放大”。最经典的例子是二分查找：// 在有序数组中查找target，返回下标 int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }每次循环，搜索范围就缩小一半：n → n/2 → n/4 → … → 1。一共需要多少次？假设需要k次，那 n / 2^k = 1，也就是 2^k = n，k = log₂n。所以复杂度是O(logn)。识别O(logn)代码有个很实用的标志：循环里的变量不是一次加1，而是每次乘以2或者除以2。比如：int i = 1; while (i < n) { i = i * 2; // 每次翻倍，循环次数大约是log2(n) }日常开发里，二分查找、平衡二叉树的查找、某些分治算法的合并过程，都是O(logn)的级别。2.3 O(n)：线性级，最常见的复杂度O(n)就是遍历一遍所有数据，数据量翻倍，时间也翻倍。这是最直观的复杂度，一眼就能认出来：一层循环，循环变量从0走到n。int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; }O(n)在开发里到处都是：遍历数组、遍历List、遍历Map的keySet、统计字符串长度、读取文件的所有行……凡是“把每个元素都过一遍”的操作，基本都是O(n)。这里顺便多说一句，很多人以为一层循环就是O(n)，这基本对，但要注意一个例外：如果循环里调用的方法本身不是O(1)的，那整体复杂度就要乘上那个方法的复杂度。比如这样一段代码：List<String> list = getList(); // 长度n for (int i = 0; i < n; i++) { boolean contains = list.contains(someItem); // contains内部还要遍历一次，是O(n) }外层O(n)、内层O(n)，整体就变成了O(n²)。这是日常开发里非常容易踩的坑，后面专门开一节讲。2.4 O(nlogn)：线性对数级，排序算法的分水岭O(nlogn)看起来有点怪，但它其实是很多优秀算法的标志性复杂度，典型代表就是快速排序、归并排序、堆排序这些主流排序算法。这个复杂度怎么来的？通常是“外层做O(logn)次拆分，每次合并过程要处理O(n)个元素”。以归并排序为例：数组每次对半拆，能拆logn层；每一层合并的时候，都要把当前层所有元素过一遍，总共n个元素。所以总工作量就是 n × logn。在Java里，你几乎天天在用O(nlogn)的算法而不自知：Arrays.sort(arr); // 底层是双轴快速排序，平均O(nlogn) Collections.sort(list); // 底层是TimSort，O(nlogn) list.stream().sorted().collect(Collectors.toList()); // 也是O(nlogn)如果代码里出现“外层循环n次、内层循环每次减半”的结构，那大概率也是O(nlogn)。比如：int count = 0; for (int i = 0; i < n; i++) { int j = 1; while (j < n) { j = j * 2; count++; } }外层要执行n次，内层每次执行logn次，乘起来就是O(nlogn)。2.5 O(n²)：平方级，要警惕的复杂度O(n²)就是两层循环嵌套，每层都跟n相关。数据规模小的时候感觉不到问题，但只要n上了万级别，O(n²)的代码就开始让人着急了。// 冒泡排序，经典O(n²) for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } }为什么O(n²)危险？因为n的增长对耗时的放大是指数级的平方放大。n=1000时，要执行大约50万次比较；n=10000时，就要大约5000万次；n=100000时，直接50亿次——不管机器多快，这个量级都扛不住。还有一种O(n³)甚至O(n⁴)的，写法就是三层、四层嵌套循环，常见于某些矩阵运算、暴力枚举组合的场景。这类复杂度在数据规模稍大时几乎不可用，通常需要寻找更优的算法替代。2.6 O(2ⁿ)与O(n!)：指数级和阶乘级，基本上不可用这两个复杂度是“算法地狱”级别的，数据规模稍微大一点就无解。O(2ⁿ)的典型代表是递归计算斐波那契数列的朴素写法：int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }为什么这个这么慢？每次调用fib(n)会分裂成两个子调用，每个子调用又分裂成两个，整个递归树像爆炸一样扩展。n=30的时候大约要计算上千万次，n=50的时候已经是个天文数字。O(n!)就更恐怖了，典型是暴力求解旅行商问题、列出所有排列。n=10是3628800种排列，n=12就接近4.8亿。这种复杂度在工程上基本意味着“换个思路，别硬算”。遇到O(2ⁿ)或O(n!)，通常的优化方向是动态规划、回溯剪枝或者启发式算法，核心思想都是“避免重复计算、尽量剪掉不可能的分支”。提示：看到递归代码，先别急着判断它是O(n)还是O(2ⁿ)。画出递归树就知道，一棵树有多少节点，大致就是多少次调用。3. Java代码里的复杂度实战3.1 先看三段代码，你来判断光看理论容易飘，记住“不复杂”的最好方式就是动手分析。下面三段代码，先别往下看答案，自己在心里判断一下每段的时间复杂度。代码一：int sum = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { sum += (i * j); } }代码二：int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 100; j++) { count++; } }代码三：public int find(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; }答案分别是：O(n²)、O(n)、O(n)——注意第三段这里有个悬念，稍后细讲。代码一的内层循环执行次数是1+2+3+…+n，也就是n(n+1)/2，保留最高阶就是O(n²)。代码二的内层循环是固定的100次，跟n无关，所以总次数是100n，也就是O(n)。很多人一看“两个for嵌套”就条件反射写O(n²)，其实内层是常数次，本质就只是O(n)。代码三有意思的地方在于，它最好情况是目标刚好在第一个位置，O(1)；最坏情况是目标不在数组里或者排在最后一位，O(n)。这就是下面要讲的“一个算法有多个复杂度”的问题。3.2 复杂度分析的三条基本法则分析复杂度不用每次都从零推导，记住三条法则就够了：加法法则：总复杂度等于量级最大的那段代码的复杂度。如果一段代码先做一个O(n)的遍历，又做一个O(logn)的查找，总复杂度就是O(n)。原因很简单，当n很大的时候，O(n)是绝对的主角。乘法法则：嵌套代码的复杂度等于内外层代码复杂度的乘积。外层循环O(n)，内层循环O(logn)，整体O(nlogn)；外层O(n)，内层O(n)，整体O(n²)。这个跟数学里的乘法一样直觉。只关注循环次数最多的那段代码。常见的组合拳是：前面有一段O(1)的初始化，中间有一段O(n)的处理，最后有一段O(n²)的输出——直接看O(n²)那段就好。这三条法则看起来简单，但真正常被问到的坑在于：有人会把“加法法则”理解成“把所有复杂度加起来”，其实应该是“取最大”。比如一段代码先做O(n²)的排序，再做O(n)的遍历，复杂度是O(n²)而不是O(n²+n)——这在增长趋势上没有任何区别。3.3 递归的复杂度怎么算递归的复杂度比迭代稍微绕一点，很多人在递归上栽跟头。用一个不算严谨但很好用的思路：递归复杂度 = 递归深度 × 每次递归内的时间复杂度。还是用斐波那契那个例子。fib(n)会调用fib(n-1)和fib(n-2)，这两个又各自继续分裂，所以递归深度大约是n，但每一层调用的次数是指数级增长的。这时候“递归深度 × 每次递归内的时间复杂度”这套公式就不太适用了，因为它算的是“递归链单条路径”的开销，而实际上每一层都有大量分支。正确的方法是看递归树：fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ └── fib(1) │ └── fib(2) └── fib(3) ├── fib(2) └── fib(1)每往下一层，节点数翻倍，树的总节点数大约是2ⁿ量级，所以复杂度O(2ⁿ)。为什么很多时候我们觉得“好像不太慢”？因为n一旦超过40，慢得就非常明显，机器扛不住指数爆炸。多提一句递归的空间复杂度。递归过程中每次调用都在系统调用栈上压入一层，递归深度是多少，栈空间就是多少。所以fib(n)的空间复杂度是O(n)，不是O(1)。很多人只算时间不算空间，结果在递归深层级时遇到栈溢出。3.4 空间复杂度：别只盯着时间看前面一直在说时间，但空间复杂度同样重要，它衡量的是算法运行需要的额外内存空间。分析方法和时间复杂度基本一致，只是把“执行次数换成了内存占用”。最常见的是O(1)：只用了几个临时变量，不随数据规模变化。比如交换两个数的值、单层遍历计数器这些。O(n)：需要额外开一个跟输入规模等长的数组、集合或者字符串。比如：// 把数组每个元素取绝对值，放到新数组里 int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = Math.abs(arr[i]); }这段代码的时间是O(n)，额外空间也是O(n)。O(n²)：二维数组、矩阵的存储，比如n×n的二维数组。空间复杂度有个常见的“交易”思维：以空间换时间。HashMap的O(1)查找背后是哈希表占用额外内存；缓存中间结果的动态规划也是典型空间换时间。实际开发里要平衡着来：内存本来就很紧张的时候，就不能一味追求时间最优。提示：Java里分析空间复杂度时，要注意你创建的容器真正的容量和实际使用量的区别。ArrayList扩容到capacity=16但size=3，实际额外空间按size算才合理。4. 最好、最坏、平均、均摊复杂度4.1 同一个算法，为什么有三个复杂度回到代码三那个例子：一个循环查找数组中的目标值。目标可能出现在第一个位置（最好情况O(1)），可能出现在最后一个位置或者根本不存在（最坏情况O(n)）。如果面试官问“这段代码复杂度是多少”，只回答O(n)不够完整——最好情况O(1)、最坏情况O(n)，这才是完整答案。为什么要有最好和最坏之分？因为同样的代码，在不同的数据分布下表现完全不同。最典型的例子是快速排序：平均情况下O(nlogn)，但如果数据本身已经有序且每次选的基准值都很倒霉，会退化到O(n²)。如果你在技术讨论里只说“快排是O(nlogn)”，其实不够严谨，要说“平均O(nlogn)、最坏O(n²)”。理解最好、最坏复杂度的关键，是要意识到“复杂度描述的是算法在什么场景下的表现”。最好情况给的是下限感知，最坏情况给的是安全底线。平时做技术方案的时候，我习惯先看最坏情况能不能接受，因为它决定了系统的稳定性。4.2 平均情况复杂度：加权平均的产物最好、最坏往往比较极端，日常更关心的是平均情况。拿查找数组来说，如果目标值一定存在，并且出现在每个位置的概率都相同，那期望的查找次数是：(1 + 2 + 3 + … + n) / n = (n+1) / 2去掉常数和低阶项，平均复杂度就是O(n)。对于大多数遍历类查找算法，平均和最坏都是O(n)，差别不大。但有些算法的平均复杂度需要认真算一下概率分布，比如哈希表的查找，平均O(1)，最坏O(n)——前提是哈希函数设计得当、冲突控制良好。如果你知道数据分布不均匀，那就要按真实分布去算，而不是默认“均匀”。4.3 均摊复杂度：一个让面试官眼前一亮的词均摊复杂度是最好/最坏/平均之后第四个重要概念，也是容易混淆的一个。它的场景是：大多数操作都是低开销的，偶尔有高开销的操作，但这高开销操作不是每次都发生。把高开销的成本分摊到所有操作上，整体的复杂度并不高。最经典的Java例子是ArrayList的add操作。List<Integer> list = new ArrayList<>(); // 初始容量10 for (int i = 0; i < n; i++) { list.add(i); }大多数情况下add只是往数组末尾放一个元素，O(1)。但当元素数量超过当前容量时，ArrayList需要扩容：申请一个更大的新数组，把旧数组所有元素拷贝过去。这一步是O(n)的。问题是，扩容不是每次都发生。每次扩容后容量大约变为原来的1.5倍，所以之后再插入很多元素都不需要扩容。把偶尔一次O(n)的拷贝成本，平摊到n次add操作上，每次add的均摊成本还是O(1)。我见过不少人在讨论ArrayList和LinkedList时，只说“ArrayList的add是O(1)，LinkedList的add是O(1)”，其实ArrayList的add更应该描述为“均摊O(1)”。别小看这个区别，它在设计高并发写库、批量插入场景时有实际意义：如果没意识到扩容会有单次O(n)的尖峰，你可能会被某个瞬间的卡顿打个措手不及。注意：均摊复杂度和平均复杂度不是一回事，很多讲复杂度的文章混着说。平均复杂度是针对“不同输入数据”的加权平均；均摊复杂度是针对“同一数据结构连续操作”的成本分摊。一个是数据维度，一个是时间维度。5. 复杂度分析在Java开发中的应用5.1 集合框架的复杂度对照表Java集合框架是分析复杂度最实用的练兵场，因为底层实现决定了接口的性能。我把常用集合的关键操作复杂度整理成一张表：集合类查询/查找插入删除备注ArrayListget: O(1)，contains: O(n)尾部add: 均摊O(1)，中间add: O(n)尾部remove: O(1)，中间remove: O(n)底层是可变数组LinkedListget: O(n)，contains: O(n)头部add: O(1)，尾部add: O(1)已知节点删除: O(1)底层是双向链表HashMapget: 平均O(1)，最坏O(n)put: 平均O(1)，最坏O(n)remove: 平均O(1)Java 8后冲突长链表会转红黑树TreeMapget: O(logn)put: O(logn)remove: O(logn)底层红黑树，有序HashSetcontains: 平均O(1)add: 平均O(1)remove: 平均O(1)底层是HashMapPriorityQueuepeek: O(1)offer: O(logn)poll: O(logn)底层二叉堆这张表值得反复看几遍。它解释了非常多日常开发中“奇怪”的现象：明明用List.contains判断是否存在，数据量一涨就慢得离谱；为什么明明LinkedList添加元素看起来方便，实际在中间大量插入时反而比ArrayList慢（因为要遍历找到插入位置）。5.2 日常开发里的复杂度陷阱这里整理几个我见过很多次的真实踩坑场景，每个都值得记住。陷阱一：在循环里调用contains。这个前面提过，本质是外层O(n)乘上内层O(n)，变成O(n²)。如果集合里元素比较多，这段代码会肉眼可见地越来越慢。解决办法是改用HashSet辅助判断，把contains从O(n)变成O(1)。陷阱二：循环里用+拼接字符串。很多人以为字符串拼接很简单：String result = ""; for (int i = 0; i < n; i++) { result = result + data[i]; }Java里String是不可变对象，每次拼接都要创建一个新字符串，并把旧字符串内容整体拷贝过去。这段代码的复杂度是O(n²)。数据量小看不出来，字符串一长就非常慢。正确做法是用StringBuilder，它的append在大多数情况下是O(1)均摊，整体复杂度O(n)。陷阱三：遍历Map时反复get。有人习惯这样写：for (String key : map.keySet()) { Integer value = map.get(key); // 又做了一次哈希查找 }每次get都是O(1)，本身没问题，但既然已经拿到了key，直接遍历entrySet拿value不香吗？省掉了每次重新哈希的开销。复杂度没变，但常数小很多。复杂度分析的是“量级”，但实际优化时“常数”也不能完全无视。经验：复杂度分析管的是“数量级”，常数优化管的是“实际体验”。两者都要看。数据规模大时先解决复杂度问题，数据规模小时先优化常数。5.3 复杂度相同，性能未必相同还要破除一个迷信：O(1)一定比O(n)快、O(nlogn)一定比O(n²)快。不是的。复杂度描述的是“趋势”，不描述“绝对值”。一个高性能的O(n)算法可能比一个实现很烂的O(nlogn)算法，在小数据规模上跑得更快；甚至在很大的数据规模上，如果O(nlogn)那个算法有巨大的常数系数，也可能干不过常数很小的O(n)算法。举个例子，数组顺序查找是O(n)，但如果数据量只有几十个，它查找起来一点都不慢；而一个构造复杂的索引结构虽然是O(logn)，但构建索引本身可能就要花很大的开销。另外，CPU缓存、内存访问局部性、JIT编译优化这些都会影响实际耗时。复杂度分析解决的是“会不会随着数据规模增长而失控”的数学问题，实际性能还要靠benchmark来验证。所以在面试或评审代码时，讨论“量级是否合理”是第一步；真正上生产之前，用实际数据压测是第二步。两步不能互相替代。6. 常见问题与排查技巧实录6.1 初学阶段最常见的几个误判误判一：看到两个for嵌套就写O(n²)。如果内层循环次数是固定的、不随n变化，那整体是O(n)。这个判断方法前面说过，这里再强调一次：嵌套本身不重要，内层是否与n相关才重要。误判二：把一个for循环里的方法调用当作O(1)。写代码时容易忘记自己调用的方法也不是免费的。list.contains()、String.indexOf()、数组的Arrays.copyOf()，这些都有自己的复杂度，要一层一层看进去。误判三：忽略递归栈空间。时间复杂度算对了，空间复杂度总写O(1)。递归函数每调用一次，系统就要压一层栈，空间至少是O(递归深度)。误判四：把数据规模看成常数。有些代码在本地测试时没问题，一上线上就卡顿，就是因为测试数据规模太小，掩盖了复杂度问题。分析复杂度时要假设n很大，甚至可以画一画n=10万、100万时会发生什么。6.2 面试笔试中怎么快速判断复杂度刷题或者面试时，经常需要在几秒内给出复杂度估算。我总结了一个经验流程：先看数据规模。如果题目说n最大10^5，那你脑子里要有数：O(n²)意味着大约10^10次操作，基本不可行；O(nlogn)意味着大约1.7×10^6次操作，可行。如果n最大100，那O(n²)、甚至O(n³)都完全没问题。数据规模是复杂度选型的硬约束。再看代码结构。一个循环一层层往下剥：外层是什么循环，内层变量怎么变化，中间有没有break、continue、提前return，有没有调用其他方法。把这些都用前面的三条法则组装起来。最后再确认最坏情况的合理性。面试官问复杂度时，默认问的是最坏复杂度；如果能补充最好情况和均摊情况，会显得你的分析更完整。6.3 我自己的学习心得说回这篇的标题——“不复杂的复杂度”。我特别理解为什么有人觉得它复杂，因为学校里的讲法经常从数学定义开始，上来就是渐进符号、紧致界、主定理，把人吓得够呛。但你如果真的每天写代码，就会慢慢发现复杂度根本不是用来“计算”的，而是用来“感知”的。写一个循环的时候，感觉一下这个循环会跑多少遍；写递归的时候，画一下递归树长什么样；选数据结构的时候，想想最常用的操作大概什么代价——这些感觉建立起来之后，复杂度就变成了一种本能，你真的不需要背任何公式。最后再分享一个特别实用的小技巧：分析一个不熟悉的工具类或框架方法时，不用去翻源码，最有效的方式是直接看它的JavaDoc，很多JDK方法都会标注时间复杂度；如果没有标注，就去搜一下它内部的实现结构，是数组、链表还是哈希表，基本就能猜个大概。这个方法帮我快速理解了很多类库的“性能底色”，强烈推荐你也试试。