先提个问题：你写一段Java代码，输入规模从100条变成100万条，程序会不会从"秒出"变成"等到地老天荒"？如果你没法在写代码之前就回答这个问题，那你在写的是"能跑的代码"，还不是"能扛的代码"。这个从"能跑"到"能扛"之间最短的那座桥，正好就是复杂度分析。很多初学者一听到"时间复杂度""空间复杂度"就头皮发麻，觉得这是算法竞赛选手或者大厂面试才需要关心的事。我在这篇"Java学习苦旅"系列第八篇里想讲的恰恰相反：复杂度这个概念本身就两件事——数一数你的代码执行了多少步操作，再看一看它额外占了多少内存。把它说成"不复杂"，不是标题党，是因为这里面的核心思路确实简单直接，难的是你在学习过程中给自己加戏。如果你正在学Java的基础语法、刚接触数据结构，或者写了一段能跑但不知道性能会怎么变化的代码，这篇文章就是给你准备的。我会用最容易理解的方式讲清楚复杂度的核心思想，然后用真实的Java代码一步步演示怎么分析一段代码的时间复杂度和空间复杂度，最后再聊聊实际写代码时该怎么判断什么值得优化、什么不值得优化。1. 复杂度到底在衡量什么：不是时间，是操作次数先澄清一个最常见的误解：我们说一个算法是 O(n) 还是 O(n²)，并不是用秒表去测一段代码跑了多少毫秒。时间复杂度描述的是"当输入规模变大时，这段代码的核心操作次数会以什么样的速度增长"。举个例子。你用手机给100个人发消息和给200个人发消息，时间差不了太多；但如果你给100个人每人单独建一个群，再把另外100个人也拉进来，那创建群的操作次数就会暴涨。复杂度的本质，就是在回答"你的操作次数和输入规模之间的关系到底是什么形状"。1.1 用"数豆子"来理解函数的增长假设有两个任务：任务A是"数一下盒子里有多少颗豆子"，任务B是"数一下盒子里每一颗豆子跟其他所有豆子的重量差"。豆子数量用 n 表示。任务A：你每数一颗豆子做一次计数，总共数了 n 次，操作次数是 n。任务B：你拿起第一颗豆子，跟剩下 n-1 颗逐个比较，然后拿起第二颗，再跟剩下 n-1 颗比较……总次数大概是 n × (n-1)，约等于 n²。当 n=10 时，任务A是10次操作，任务B是90次操作，还能接受。当 n=10000 时，任务A是10000次操作，任务B是约1亿次操作。计算机再快也扛不住这种差距。这就是为什么我们看复杂度而不是看某一次运行时间——运行时间会受机器性能影响，操作次数是算法本身的属性，换个电脑它也不会变。1.2 空间复杂度衡量的又是什么空间复杂度就更直接了：你的算法除了存原始数据本身，还额外开辟了多少内存。一个排序算法是原地操作的（只用了O(1)额外空间），还是在排序过程中又复制了一份整个数组（那额外空间就是O(n)），这直接决定了它能不能在一个内存紧张的环境里跑起来。初学者最容易忽略的是递归的空间成本：递归每次调用都会在调用栈上占一层空间，所以一个深度为 n 的递归，空间复杂度就是 O(n)。这一点在分析后面斐波那契数列的例子时会体现得非常明显。2. 大O记号：大幅度化简才是它的精髓复杂度分析的第一步不是写出精确公式，而是做化简。大O记号（Big O notation）干的事情就是"丢掉不重要的东西，只留下决定命运的部分"。化简规则就两条：只保留增长最快的那一项。比如 T(n) = 3n² + 5n + 100，只留下 n²。丢掉所有常数系数。比如 T(n) = 5n，直接写成 n。为什么可以这么简化？因为大O关心的是 "n 很大时" 的趋势。n 足够大之后，5n 里的 5，n²+100n 里的 100n，都只是小得可怜的噪声。这就好比你评估一个人二十年后的职业发展，不会把他今天早饭吃了一个还是两个鸡蛋当重要变量。2.1 最常用的几个复杂度级别，以及它们对应的直觉我把几乎百分之九十的代码都会遇到的复杂度级别列出来，并配上一个生活化的直觉，你对照着看很容易建立感觉。复杂度名称生活直觉典型代码O(1)常数级无论盒子多大，你只需要打开盖子看一眼数组按下标取值O(log n)对数级一本有 n 页的书，你从中间翻，不断缩小查找范围二分查找O(n)线性级一本有 n 页的书，你从第一页逐页看到最后一页单层for循环O(n log n)线性对数级先把一堆乱序扑克牌拆成单张，再按大小两两合并归并排序、快速排序O(n²)平方级班里 n 个人，每两个人之间都要互相打一次招呼双层嵌套for循环O(2ⁿ)指数级你想列举 n 个元素的每一种可能组合暴力递归这里我想特别强调对数级 O(log n)。很多初学者搞不懂 log n 是怎么来的，因为在 Java 代码里你几乎看不到一个真实的"log"。它的来源是这样的：如果你每执行一步操作，把问题的规模缩小一半，那么从 n 缩小到 1，你需要执行的步数就是 log₂(n) 次。二分查找就是这样——每比较一次，搜索范围减半，所以它的复杂度是 O(log n)。同样的道理，一个有序数组里找一个数，用遍历是 O(n)，用二分查找是 O(log n)，当 n 是一亿时，前者上亿次操作，后者大约27次操作。2.2 千万别被"大O优化"骗了有一点要提前说清楚：O(1) 并不永远比 O(n) 快。大O描述的是"增长趋势"，不是"绝对速度"。数组按下标取值是 O(1)，但这一步操作本身很快；哈希表插入均摊也是 O(1)，可常数因子并不小。反过来，一个 O(n) 算法如果每一步操作极其简单，在小规模数据上很有可能反而比 O(1) 哈希表更快。我见过不少人一看见复杂度分析就陷入"只要 O(1) 就好，只要 O(n log n) 就好"的思维定式，然后为了把一个本来就很快的 O(n) 遍历改成"看起来更高级"的结构，引入大量复杂度和bug，得不偿失。复杂度分析是帮你判断"当数据规模增长时会发生什么"的工具，不是让你做无意义的常数级优化的借口。3. 手把手把Java代码翻译成复杂度下面进入这篇文章最实际的部分——怎么从一段Java代码里准确地推出复杂度。我打算用几个典型的例子，从简单到复杂，一步步做完整个分析过程。3.1 单层循环：先找"核心操作"再数次数public long sumArray(int[] arr) { long sum = 0; for (int num : arr) { sum += num; } return sum; }这段代码的核心操作是sum += num——它可以代表整个循环体的成本。这个操作执行了 n 次（n 是数组长度），所以时间复杂度是 O(n)。注意这里我们没有把long sum = 0和return sum算进去，因为它们的执行次数是常数，对增长趋势没影响。大多数单层循环，不管循环体里有几句代码，只要没有在循环内部引发额外的循环或递归，就都是 O(n)。你在分析时只需要问自己一个问题：循环每走一遍，我处理掉了多少个"待处理单元"？如果每个待处理单元都恰好被处理一次，就是 O(n)。3.2 嵌套循环：乘起来的操作次数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=0时走 n-1 次，在i=1时走 n-2 次，一直递减。总的打印次数是 (n-1) + (n-2) + ... + 1 = n(n-1)/2。去掉系数和低阶项，得到 O(n²)。理解这种"二重循环天然是 O(n²)"特别重要。很多实际代码的性能瓶颈都藏在两个看似无辜的嵌套循环里。比如你在一层业务逻辑里对数组做双循环比较，数据量上千时还能忍，数据量上万就开始明显卡顿，这就是 O(n²) 增长的一个直观体感。顺便提一句，有些三重循环就是 O(n³)，理论上是这样，但实际工程里三重循环往往意味着设计问题，你可以先停下来想想有没有办法把其中一层用哈希表或者排序替代掉。这就是算法优化的入门思路：用空间换时间。3.3 二分查找：为什么每次减半就成了 log npublic int binarySearch(int[] sortedArr, int target) { int left = 0; int right = sortedArr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (sortedArr[mid] == target) { return mid; } else if (sortedArr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }这里的关键是：每执行一次循环，搜索区间就从 n 缩到 n/2。连续执行 k 次循环后，区间长度是 n / 2^k。当区间缩到 1 时循环停止，所以 n / 2^k = 1，也就是 k = log₂(n)。时间复杂度是 O(log n)。注意一个细节：如果数组一开始就是乱序的，你得先排序。排序本身是 O(n log n)，所以"先排序再二分查找"的完整流程是 O(n log n)，这依然比"每次直接线性查找"的 O(n × m) 好得多——前提是你有很多次查找需求，排序成本被摊薄了。实际工程里经常这样做：一次性建索引/排序，然后反复用 O(log n) 或 O(1) 的方式查询。3.4 递归复杂度：以斐波那契数列为例看爆炸式增长public int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); }这段代码看似简单，复杂度却最容易被低估。要分析它，我们得看递归树：fib(n)会调用fib(n-1)和fib(n-2)，这两个又分别调用各自的子问题，形成一棵二叉树。树的第 k 层有大约 2^k 个节点，整棵树的总节点数接近 2ⁿ。所以fib(n)的时间复杂度是 O(2ⁿ)（准确说是 O(φⁿ)，φ 是黄金比例，但大O层面写 2ⁿ 已经足够表达指数级的恐怖）。这就是为什么 n=40 时程序开始明显变慢，n=50 时很多机器已经要等好几秒，n=100 时宇宙毁灭也算不完。空间复杂度则是 O(n)，因为递归调用栈的最大深度是 n，不是 2ⁿ。初学者经常搞错这一点——时间看的是"总共有多少个调用"，空间看的是"最深的时候栈里叠了多少层"。如果换成带备忘录的写法：public int fibMemo(int n, int[] memo) { if (n <= 1) return n; if (memo[n] != 0) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; }每个子问题最多被计算一次，子问题个数是 n，所以时间复杂度降到 O(n)。这是"用空间换时间"最经典的例子之一，也是为什么我说复杂度分析能直接指导你的代码设计——没有分析，你可能根本说不出来这两版斐波那契差异到底有多大。4. 空间复杂度：第二维度的优化往往更值钱很多入门文章把空间复杂度放在最后轻描淡写，但实际工程里，时间不够用你还能加机器加缓存，内存不够用有时候是架构级别的难题。我觉得从学习阶段就该把空间复杂度这个习惯养成。4.1 原地操作和额外空间的差异空间复杂度分析时，我们通常不把保存输入数据本身的空间算进去，只看"额外分配"的部分。比如：冒泡排序、插入排序：只用了常数个临时变量（一个temp、几个循环变量），额外空间 O(1)，是原地排序。归并排序：合并时需要额外开一个临时数组来存放合并结果，额外空间 O(n)。上面斐波那契的备忘录写法：开了一个长度 n 的 memo 数组，额外空间 O(n)；递归版虽然没开数组，但调用栈深度也是 O(n)。有一个微妙的点：有时候时间复杂度和空间复杂度是可以互相交换的。HashMap 查找是 O(1)，但它本身就要占 O(n) 的空间；如果你不用 HashMap、裸着去遍历查找，时间是 O(n)、空间是 O(1)。没有绝对的好坏，只有你当前场景更缺什么。4.2 递归栈空间：初学者最容易忽略的内存消费者看下面这个打印链表的递归方法：public void printList(ListNode head) { if (head == null) return; System.out.println(head.val); printList(head.next); }这个方法的递归深度等于链表长度 n，所以空间复杂度是 O(n)。如果链表长度是100万，这段代码在递归时就会消耗掉大量栈内存，甚至可能抛 StackOverflowError。而如果你用 while 循环来写同样功能，空间复杂度是 O(1)。这就是为什么有些治国级的代码烂在某一个"看着很优雅的递归"上。递归优雅，但在深度不确定时，先想想栈够不够用。5. 实战里我怎么判断一段代码到底行不行前面讲的都是分析现有代码，但实际开发里我们还会遇到一个更常见的问题：功能还没写，怎么在方案设计阶段就预估一段代码将来会不会扛不住。这需要一点估算能力和一张常见的操作成本表。5.1 常用数据结构和操作的复杂度速查我整理了一份自己工作中反复用到的速查表，按读、写、查找、删除几个维度列出Java常用集合操作的复杂度。你没必要背下来，但最好看到就能想起来。数据结构按下标/Key访问按值查找插入删除备注数组O(1)O(n)O(n)（需移动）O(n)连续内存ArrayListO(1)O(n)末尾O(1)，中间O(n)末尾O(1)，中间O(n)动态扩容均摊O(1)LinkedListO(n)O(n)已知位置O(1)已知位置O(1)节点间跳转慢HashMapO(1)均摊O(1)均摊O(1)均摊O(1)均摊最坏O(n)当哈希冲突严重TreeMapO(log n)O(log n)O(log n)O(log n)基于红黑树，保序HashSet无O(1)均摊O(1)均摊O(1)均摊底层就是HashMapPriorityQueue堆顶O(1)O(n)O(log n)O(log n)默认最小堆这张表特别适合回答"这个业务该用List还是Map""这里该用Set去重还是用List遍历去重"这类问题。比如说，一个功能要频繁按某个唯一标识查找对象，你如果用的是ArrayList，那么每次查找都是O(n)，数据量到十万级别就开始忽快忽慢；改成HashMap后查找是O(1)，体感几乎是瞬间完成。这是我在很多业务代码里看到的最常见、也最容易改的优化点。5.2 用数据规模反推可接受的复杂度我在设计一个功能时，通常会先问自己一个问题：这个操作的数据规模上限大概是多少？然后根据规模倒推复杂度要求。n ≤ 10：什么算法都行，暴力枚举也无所谓。n ≤ 1000：O(n²) 大概率可以接受。n ≤ 100000：O(n log n) 普遍没问题，O(n²) 就很危险。n ≥ 10^7：必须 O(n) 或者更优，O(n log n) 要看常数和运行环境。n ≥ 10^9：通常只能 O(log n) 或者 O(1) 风格的解法，或者根本不能一次跑完，要考虑分布式/流式处理。这套经验值来自大量实际运行环境的积累，你不需要精确，因为现代机器在不同配置下差异很大，但它给你一个很好的早期预警信号：如果预估数据规模会在十万级，而我的方案是双层循环嵌套比较，那我在写代码之前就知道要换思路了。5.3 渐进复杂度之外的"常数优化"陷阱最后我想谈一个复杂度分析说不清楚、但真实存在的重要问题：常数优化和渐进优化的区别。把 O(n²) 改成 O(n log n)，这叫渐进优化，效果随数据规模增长越来越明显，值得投入。把 O(n) 的循环里每次调用都封装成方法，或者把List.contains换成Set.contains——如果 List 的长度是固定很小的几个元素（比如少于10），这种"优化"其实是在增加代码复杂度，收益微乎其微。复杂度分析的价值在于识别"数量级层面"的问题，而不是帮你抠每个循环里的那几个纳秒。我见过太多人为了把一个本来已经 O(n) 的遍历改成"看起来并行度更高"的结构，引入了线程安全和同步开销，结果跑得比原来更慢。复杂度没变，常数翻了几倍。分析复杂度之前，先看清楚自己优化的到底是数量级还是常数，这一点想明白，你在性能优化上就不会走弯路。6. 从"不复杂"到"习惯成自然"写这篇文章前我重新回顾了自己入门算法时的过程，最大的感慨是：复杂度这个东西真的不难，它就是一套"数操作次数、看增长趋势"的思维方法。真正难的是把它内化成一种写代码时的下意识反应。我现在的习惯是：每写完一个循环嵌套，先想一下它是什么复杂度；每次要在循环里用 contains 或者 indexOf 查找，先想一下这个查找本身是什么复杂度；每次写递归，先想一下递归深度会不会是 O(n)。养成这个习惯之后，很多性能问题在动手前就能被拦下来。反过来说，如果等到测试环境数据一大再去用性能分析工具抓慢查询、抓CPU热点，那代价就高得多了。文末给你留一个小练习：找一段你自己项目中稍微复杂一点的方法，按照我上面第3小节的方式，画出循环层级，数出核心操作次数，写出它的时间复杂度和空间复杂度。做完这一步再回头看这篇文章，你应该会认同我说的——复杂度，确实不复杂。
先提个问题：你写一段Java代码，输入规模从100条变成100万条，程序会不会从"秒出"变成"等到地老天荒"？如果你没法在写代码之前就回答这个问题，那你在写的是"能跑的代码"，还不是"能扛的代码"。这个从"能跑"到"能扛"之间最短的那座桥，正好就是复杂度分析。很多初学者一听到"时间复杂度""空间复杂度"就头皮发麻，觉得这是算法竞赛选手或者大厂面试才需要关心的事。我在这篇"Java学习苦旅"系列第八篇里想讲的恰恰相反：复杂度这个概念本身就两件事——数一数你的代码执行了多少步操作，再看一看它额外占了多少内存。把它说成"不复杂"，不是标题党，是因为这里面的核心思路确实简单直接，难的是你在学习过程中给自己加戏。如果你正在学Java的基础语法、刚接触数据结构，或者写了一段能跑但不知道性能会怎么变化的代码，这篇文章就是给你准备的。我会用最容易理解的方式讲清楚复杂度的核心思想，然后用真实的Java代码一步步演示怎么分析一段代码的时间复杂度和空间复杂度，最后再聊聊实际写代码时该怎么判断什么值得优化、什么不值得优化。1. 复杂度到底在衡量什么：不是时间，是操作次数先澄清一个最常见的误解：我们说一个算法是 O(n) 还是 O(n²)，并不是用秒表去测一段代码跑了多少毫秒。时间复杂度描述的是"当输入规模变大时，这段代码的核心操作次数会以什么样的速度增长"。举个例子。你用手机给100个人发消息和给200个人发消息，时间差不了太多；但如果你给100个人每人单独建一个群，再把另外100个人也拉进来，那创建群的操作次数就会暴涨。复杂度的本质，就是在回答"你的操作次数和输入规模之间的关系到底是什么形状"。1.1 用"数豆子"来理解函数的增长假设有两个任务：任务A是"数一下盒子里有多少颗豆子"，任务B是"数一下盒子里每一颗豆子跟其他所有豆子的重量差"。豆子数量用 n 表示。任务A：你每数一颗豆子做一次计数，总共数了 n 次，操作次数是 n。任务B：你拿起第一颗豆子，跟剩下 n-1 颗逐个比较，然后拿起第二颗，再跟剩下 n-1 颗比较……总次数大概是 n × (n-1)，约等于 n²。当 n=10 时，任务A是10次操作，任务B是90次操作，还能接受。当 n=10000 时，任务A是10000次操作，任务B是约1亿次操作。计算机再快也扛不住这种差距。这就是为什么我们看复杂度而不是看某一次运行时间——运行时间会受机器性能影响，操作次数是算法本身的属性，换个电脑它也不会变。1.2 空间复杂度衡量的又是什么空间复杂度就更直接了：你的算法除了存原始数据本身，还额外开辟了多少内存。一个排序算法是原地操作的（只用了O(1)额外空间），还是在排序过程中又复制了一份整个数组（那额外空间就是O(n)），这直接决定了它能不能在一个内存紧张的环境里跑起来。初学者最容易忽略的是递归的空间成本：递归每次调用都会在调用栈上占一层空间，所以一个深度为 n 的递归，空间复杂度就是 O(n)。这一点在分析后面斐波那契数列的例子时会体现得非常明显。2. 大O记号：大幅度化简才是它的精髓复杂度分析的第一步不是写出精确公式，而是做化简。大O记号（Big O notation）干的事情就是"丢掉不重要的东西，只留下决定命运的部分"。化简规则就两条：只保留增长最快的那一项。比如 T(n) = 3n² + 5n + 100，只留下 n²。丢掉所有常数系数。比如 T(n) = 5n，直接写成 n。为什么可以这么简化？因为大O关心的是 "n 很大时" 的趋势。n 足够大之后，5n 里的 5，n²+100n 里的 100n，都只是小得可怜的噪声。这就好比你评估一个人二十年后的职业发展，不会把他今天早饭吃了一个还是两个鸡蛋当重要变量。2.1 最常用的几个复杂度级别，以及它们对应的直觉我把几乎百分之九十的代码都会遇到的复杂度级别列出来，并配上一个生活化的直觉，你对照着看很容易建立感觉。复杂度名称生活直觉典型代码O(1)常数级无论盒子多大，你只需要打开盖子看一眼数组按下标取值O(log n)对数级一本有 n 页的书，你从中间翻，不断缩小查找范围二分查找O(n)线性级一本有 n 页的书，你从第一页逐页看到最后一页单层for循环O(n log n)线性对数级先把一堆乱序扑克牌拆成单张，再按大小两两合并归并排序、快速排序O(n²)平方级班里 n 个人，每两个人之间都要互相打一次招呼双层嵌套for循环O(2ⁿ)指数级你想列举 n 个元素的每一种可能组合暴力递归这里我想特别强调对数级 O(log n)。很多初学者搞不懂 log n 是怎么来的，因为在 Java 代码里你几乎看不到一个真实的"log"。它的来源是这样的：如果你每执行一步操作，把问题的规模缩小一半，那么从 n 缩小到 1，你需要执行的步数就是 log₂(n) 次。二分查找就是这样——每比较一次，搜索范围减半，所以它的复杂度是 O(log n)。同样的道理，一个有序数组里找一个数，用遍历是 O(n)，用二分查找是 O(log n)，当 n 是一亿时，前者上亿次操作，后者大约27次操作。2.2 千万别被"大O优化"骗了有一点要提前说清楚：O(1) 并不永远比 O(n) 快。大O描述的是"增长趋势"，不是"绝对速度"。数组按下标取值是 O(1)，但这一步操作本身很快；哈希表插入均摊也是 O(1)，可常数因子并不小。反过来，一个 O(n) 算法如果每一步操作极其简单，在小规模数据上很有可能反而比 O(1) 哈希表更快。我见过不少人一看见复杂度分析就陷入"只要 O(1) 就好，只要 O(n log n) 就好"的思维定式，然后为了把一个本来就很快的 O(n) 遍历改成"看起来更高级"的结构，引入大量复杂度和bug，得不偿失。复杂度分析是帮你判断"当数据规模增长时会发生什么"的工具，不是让你做无意义的常数级优化的借口。3. 手把手把Java代码翻译成复杂度下面进入这篇文章最实际的部分——怎么从一段Java代码里准确地推出复杂度。我打算用几个典型的例子，从简单到复杂，一步步做完整个分析过程。3.1 单层循环：先找"核心操作"再数次数public long sumArray(int[] arr) { long sum = 0; for (int num : arr) { sum += num; } return sum; }这段代码的核心操作是sum += num——它可以代表整个循环体的成本。这个操作执行了 n 次（n 是数组长度），所以时间复杂度是 O(n)。注意这里我们没有把long sum = 0和return sum算进去，因为它们的执行次数是常数，对增长趋势没影响。大多数单层循环，不管循环体里有几句代码，只要没有在循环内部引发额外的循环或递归，就都是 O(n)。你在分析时只需要问自己一个问题：循环每走一遍，我处理掉了多少个"待处理单元"？如果每个待处理单元都恰好被处理一次，就是 O(n)。3.2 嵌套循环：乘起来的操作次数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=0时走 n-1 次，在i=1时走 n-2 次，一直递减。总的打印次数是 (n-1) + (n-2) + ... + 1 = n(n-1)/2。去掉系数和低阶项，得到 O(n²)。理解这种"二重循环天然是 O(n²)"特别重要。很多实际代码的性能瓶颈都藏在两个看似无辜的嵌套循环里。比如你在一层业务逻辑里对数组做双循环比较，数据量上千时还能忍，数据量上万就开始明显卡顿，这就是 O(n²) 增长的一个直观体感。顺便提一句，有些三重循环就是 O(n³)，理论上是这样，但实际工程里三重循环往往意味着设计问题，你可以先停下来想想有没有办法把其中一层用哈希表或者排序替代掉。这就是算法优化的入门思路：用空间换时间。3.3 二分查找：为什么每次减半就成了 log npublic int binarySearch(int[] sortedArr, int target) { int left = 0; int right = sortedArr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (sortedArr[mid] == target) { return mid; } else if (sortedArr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }这里的关键是：每执行一次循环，搜索区间就从 n 缩到 n/2。连续执行 k 次循环后，区间长度是 n / 2^k。当区间缩到 1 时循环停止，所以 n / 2^k = 1，也就是 k = log₂(n)。时间复杂度是 O(log n)。注意一个细节：如果数组一开始就是乱序的，你得先排序。排序本身是 O(n log n)，所以"先排序再二分查找"的完整流程是 O(n log n)，这依然比"每次直接线性查找"的 O(n × m) 好得多——前提是你有很多次查找需求，排序成本被摊薄了。实际工程里经常这样做：一次性建索引/排序，然后反复用 O(log n) 或 O(1) 的方式查询。3.4 递归复杂度：以斐波那契数列为例看爆炸式增长public int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); }这段代码看似简单，复杂度却最容易被低估。要分析它，我们得看递归树：fib(n)会调用fib(n-1)和fib(n-2)，这两个又分别调用各自的子问题，形成一棵二叉树。树的第 k 层有大约 2^k 个节点，整棵树的总节点数接近 2ⁿ。所以fib(n)的时间复杂度是 O(2ⁿ)（准确说是 O(φⁿ)，φ 是黄金比例，但大O层面写 2ⁿ 已经足够表达指数级的恐怖）。这就是为什么 n=40 时程序开始明显变慢，n=50 时很多机器已经要等好几秒，n=100 时宇宙毁灭也算不完。空间复杂度则是 O(n)，因为递归调用栈的最大深度是 n，不是 2ⁿ。初学者经常搞错这一点——时间看的是"总共有多少个调用"，空间看的是"最深的时候栈里叠了多少层"。如果换成带备忘录的写法：public int fibMemo(int n, int[] memo) { if (n <= 1) return n; if (memo[n] != 0) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; }每个子问题最多被计算一次，子问题个数是 n，所以时间复杂度降到 O(n)。这是"用空间换时间"最经典的例子之一，也是为什么我说复杂度分析能直接指导你的代码设计——没有分析，你可能根本说不出来这两版斐波那契差异到底有多大。4. 空间复杂度：第二维度的优化往往更值钱很多入门文章把空间复杂度放在最后轻描淡写，但实际工程里，时间不够用你还能加机器加缓存，内存不够用有时候是架构级别的难题。我觉得从学习阶段就该把空间复杂度这个习惯养成。4.1 原地操作和额外空间的差异空间复杂度分析时，我们通常不把保存输入数据本身的空间算进去，只看"额外分配"的部分。比如：冒泡排序、插入排序：只用了常数个临时变量（一个temp、几个循环变量），额外空间 O(1)，是原地排序。归并排序：合并时需要额外开一个临时数组来存放合并结果，额外空间 O(n)。上面斐波那契的备忘录写法：开了一个长度 n 的 memo 数组，额外空间 O(n)；递归版虽然没开数组，但调用栈深度也是 O(n)。有一个微妙的点：有时候时间复杂度和空间复杂度是可以互相交换的。HashMap 查找是 O(1)，但它本身就要占 O(n) 的空间；如果你不用 HashMap、裸着去遍历查找，时间是 O(n)、空间是 O(1)。没有绝对的好坏，只有你当前场景更缺什么。4.2 递归栈空间：初学者最容易忽略的内存消费者看下面这个打印链表的递归方法：public void printList(ListNode head) { if (head == null) return; System.out.println(head.val); printList(head.next); }这个方法的递归深度等于链表长度 n，所以空间复杂度是 O(n)。如果链表长度是100万，这段代码在递归时就会消耗掉大量栈内存，甚至可能抛 StackOverflowError。而如果你用 while 循环来写同样功能，空间复杂度是 O(1)。这就是为什么有些治国级的代码烂在某一个"看着很优雅的递归"上。递归优雅，但在深度不确定时，先想想栈够不够用。5. 实战里我怎么判断一段代码到底行不行前面讲的都是分析现有代码，但实际开发里我们还会遇到一个更常见的问题：功能还没写，怎么在方案设计阶段就预估一段代码将来会不会扛不住。这需要一点估算能力和一张常见的操作成本表。5.1 常用数据结构和操作的复杂度速查我整理了一份自己工作中反复用到的速查表，按读、写、查找、删除几个维度列出Java常用集合操作的复杂度。你没必要背下来，但最好看到就能想起来。数据结构按下标/Key访问按值查找插入删除备注数组O(1)O(n)O(n)（需移动）O(n)连续内存ArrayListO(1)O(n)末尾O(1)，中间O(n)末尾O(1)，中间O(n)动态扩容均摊O(1)LinkedListO(n)O(n)已知位置O(1)已知位置O(1)节点间跳转慢HashMapO(1)均摊O(1)均摊O(1)均摊O(1)均摊最坏O(n)当哈希冲突严重TreeMapO(log n)O(log n)O(log n)O(log n)基于红黑树，保序HashSet无O(1)均摊O(1)均摊O(1)均摊底层就是HashMapPriorityQueue堆顶O(1)O(n)O(log n)O(log n)默认最小堆这张表特别适合回答"这个业务该用List还是Map""这里该用Set去重还是用List遍历去重"这类问题。比如说，一个功能要频繁按某个唯一标识查找对象，你如果用的是ArrayList，那么每次查找都是O(n)，数据量到十万级别就开始忽快忽慢；改成HashMap后查找是O(1)，体感几乎是瞬间完成。这是我在很多业务代码里看到的最常见、也最容易改的优化点。5.2 用数据规模反推可接受的复杂度我在设计一个功能时，通常会先问自己一个问题：这个操作的数据规模上限大概是多少？然后根据规模倒推复杂度要求。n ≤ 10：什么算法都行，暴力枚举也无所谓。n ≤ 1000：O(n²) 大概率可以接受。n ≤ 100000：O(n log n) 普遍没问题，O(n²) 就很危险。n ≥ 10^7：必须 O(n) 或者更优，O(n log n) 要看常数和运行环境。n ≥ 10^9：通常只能 O(log n) 或者 O(1) 风格的解法，或者根本不能一次跑完，要考虑分布式/流式处理。这套经验值来自大量实际运行环境的积累，你不需要精确，因为现代机器在不同配置下差异很大，但它给你一个很好的早期预警信号：如果预估数据规模会在十万级，而我的方案是双层循环嵌套比较，那我在写代码之前就知道要换思路了。5.3 渐进复杂度之外的"常数优化"陷阱最后我想谈一个复杂度分析说不清楚、但真实存在的重要问题：常数优化和渐进优化的区别。把 O(n²) 改成 O(n log n)，这叫渐进优化，效果随数据规模增长越来越明显，值得投入。把 O(n) 的循环里每次调用都封装成方法，或者把List.contains换成Set.contains——如果 List 的长度是固定很小的几个元素（比如少于10），这种"优化"其实是在增加代码复杂度，收益微乎其微。复杂度分析的价值在于识别"数量级层面"的问题，而不是帮你抠每个循环里的那几个纳秒。我见过太多人为了把一个本来已经 O(n) 的遍历改成"看起来并行度更高"的结构，引入了线程安全和同步开销，结果跑得比原来更慢。复杂度没变，常数翻了几倍。分析复杂度之前，先看清楚自己优化的到底是数量级还是常数，这一点想明白，你在性能优化上就不会走弯路。6. 从"不复杂"到"习惯成自然"写这篇文章前我重新回顾了自己入门算法时的过程，最大的感慨是：复杂度这个东西真的不难，它就是一套"数操作次数、看增长趋势"的思维方法。真正难的是把它内化成一种写代码时的下意识反应。我现在的习惯是：每写完一个循环嵌套，先想一下它是什么复杂度；每次要在循环里用 contains 或者 indexOf 查找，先想一下这个查找本身是什么复杂度；每次写递归，先想一下递归深度会不会是 O(n)。养成这个习惯之后，很多性能问题在动手前就能被拦下来。反过来说，如果等到测试环境数据一大再去用性能分析工具抓慢查询、抓CPU热点，那代价就高得多了。文末给你留一个小练习：找一段你自己项目中稍微复杂一点的方法，按照我上面第3小节的方式，画出循环层级，数出核心操作次数，写出它的时间复杂度和空间复杂度。做完这一步再回头看这篇文章，你应该会认同我说的——复杂度，确实不复杂。