做技术这些年不管是带新人还是出去评审代码我几乎每次都会被问到同一个问题这段代码性能怎么样 新手通常直接打开计时器跑个几万条数据看秒数。有经验的人则会反问你数据量再翻十倍它还能保持这个速度吗这就是时间复杂度要回答的事。时间复杂度不是这段代码跑多久而是代码运行时间如何随输入规模的增大而增长。它是算法分析的基石也是从能跑走向跑得好的分水岭。这篇上篇我先带你彻底搞清楚什么叫时间复杂度、大O记号的底层逻辑以及从代码到复杂度表达式的完整推导方法。至于递归、摊还分析这些进阶内容我们放在下篇来拆解。1. 先从为什么不是计时器说起时间复杂度的真正含义1.1 一个让新手困惑的问题为什么不算实际运行时间我带过不少实习生最常遇到的场景是这样的写完一个排序函数他们很兴奋地告诉我我测过了排十万个数只要0.3秒性能很好。 然后我让他把数据量改成二十万时间变成了1.4秒。再改成四十万直接5秒多。他一脸茫然——数据量才翻两倍为什么时间翻了接近四倍这就是直接计时带来的困惑。你测出来的那个0.3秒只是某台机器、某个语言版本、某个数据分布下的一个瞬时值。换个CPU、换个运行环境、或者后台有别的程序在抢资源数字立刻就不一样了。同一个算法在张三的电脑上可能跑0.2秒在李四的电脑上可能跑0.8秒——但你没法因此说李四的代码慢四倍。更关键的是直接计时没法回答一个真正重要的问题当输入规模继续变大时运行时间会以什么样的速度增长是线性增长数据翻倍时间也翻倍还是平方增长数据翻倍时间翻四倍还是指数增长数据稍微变大时间就直接爆炸这个增长速度才是算法分析真正关心的东西。因为它决定了你的程序在未来能不能扛得住更大的数据量。今天你的用户只有一万个明天可能有一百万个今天你的文件只有几兆明年可能是几个G。如果代码的时间增长趋势不好那么随着业务规模扩大你的系统迟早会卡死在某一天。1.2 基本操作计数法把时间转化为操作次数既然不能直接计时那怎么衡量换个思路一台机器执行一条基本指令加法、比较、赋值、访问数组元素所需的时间大致是固定的。那么一个算法运行多久基本就取决于它总共执行了多少条基本指令。于是我们把运行时间翻译成了执行基本操作的次数。这个次数通常记为 T(n)其中 n 代表输入规模。输入规模是什么在实际问题里它可能是数组的长度、字符串的字符数、图的节点数、矩阵的边长——就是你算法要处理的那个数据总量。举个例子。看这段求数组元素和的代码def sum_array(arr): total 0 # 1次赋值 for i in range(len(arr)): # 循环执行 n 次 total total arr[i] # 每次执行1次读取 1次加法 1次赋值 3次操作 return total # 1次返回假设数组长度是 n那么整个函数执行的操作次数大约是T(n) 1 3n 1 3n 2第一次赋值算1次循环体里的加法操作执行 n 次每次算3步最后的 return 再算1次。所以总次数就是 3n 2。你看这就是计数法。我们不关心这台机器一秒能跑多少亿次只关心操作次数和 n 之间的关系。如果 n 变成原来的两倍T(n) 也大约变成原来的两倍——这就是线性增长。1.3 性能评判的核心当输入规模趋近无穷时有了 T(n) 之后我们面临下一个问题怎么拿 T(n) 来比较两个算法的好坏假设算法A的 T(n) 3n 2算法B的 T(n) 100n 50。在 n 1 的时候B 明显比 A 慢得多150 对 5。但 n 10000 的时候呢A 是 30002B 是 1000050——还是差很多。好像线性系数的差别也挺大先别急着下结论我们再看一个更极端的例子算法CT(n) n² 10n 5算法DT(n) 100n 50在 n 10 时C 205D 1050D 更慢。但在 n 200 时C 42005D 20050C 反超了。在 n 1000 时C 1010005D 100050C 已经是 D 的十倍。当 n 继续增大到一万、十万n² 和 100n 的差距会以惊人的速度拉开。这说明一个关键事实当 n 足够大时决定算法性能的不是那些常数系数比如3、100也不是那些低阶项比如10n、50而是 T(n) 中增长最快的那个主导项。这个主导项的增长速度等级就是大O记号要表达的东西。这也解释了为什么我们分析复杂度时总是说n 趋于无穷大——因为在真实业务场景中n 往往就是那个足够大的量级。一万条数据可能不算多但百万、千万、上亿条数据主导项的威力就完全显现了。2. 大O记号给算法算增长率的一套语言2.1 大O到底忽略了什么又保留了什么大O记号的正式定义是用数学极限来描述的但作为工程实践者你只需要记住它的本质大O描述的是 T(n) 的上界增长率它忽略常数系数忽略低阶项只保留最高阶的主导项。根据这个规则前面例子里的 T(n) 3n 2它的主导项是 3n忽略常数系数3记作 O(n)。T(n) 100n 50 也是 O(n)。T(n) n² 10n 5 则是 O(n²)。那为什么可以这么粗鲁地丢弃常数前面已经看到了——因为当 n 足够大的时候常数系数的影响会被主导项的增长率碾压。而且系数大小往往取决于具体的机器、编译器、语言这些外部因素今天我们写 O(100n)明天换个编译器可能就是 O(50n)这个系数本身就不稳定。但线性增长这个本质是不变的。所以大O放弃了对常数的精确追踪换取了一个跨平台、跨机器的稳定比较标准。你可能会问那算法A3n2和算法B100n50都是 O(n)难道就认为它们一样好不是的。大O只告诉你增长趋势不告诉你常数因子。在工程中当一个 O(n) 算法的常数因子大到离谱时它可能实际跑得比一个 O(n²) 算法还慢——特别是在 n 还不算特别大的时候。所以大O是一个理论和框架层面的工具它告诉你的是最坏情况下的增长天花板具体选型时还要结合常数因子实测。这个我们后面会在验证部分细讲。2.2 常见复杂度从低到高一个必须烂熟于心的刻度表把常见的复杂度增长率排个序从小到大大概是这样的大O表达式通俗称呼典型特征增长感受n翻倍时O(1)常数时间与数据量无关固定几步操作时间不变O(log n)对数时间每次把问题规模砍半时间只增加一点点O(n)线性时间遍历一遍所有数据时间翻倍O(n log n)线性对数时间排序类算法的主战场时间略快于翻倍O(n²)平方时间双层循环遍历所有组合时间变为4倍O(n³)立方时间三层循环时间变为8倍O(2ⁿ)指数时间状态爆炸n稍微大一点就完了时间急剧爆炸这个表建议你直接刻在脑子里。以后的日常交流中说这段代码是 O(n log n)老手立刻就明白它是排序级别的效率说这是 O(2ⁿ)所有人都知道这只能在小规模数据上跑。为了让你对这些增长率有体感我用一个生活类比。假设你有一本一千页的电话簿要找一个名字O(1) 相当于你直接知道名字在第500页第3行翻过去就能看到。O(log n) 相当于二分查找每次都把范围砍半一千页大概只需翻10次。O(n) 相当于从第一页开始一页页翻最多翻一千页。O(n²) 相当于每翻一页都要把整本书从头到尾再看一遍这操作很离谱但类比复杂度。数据量变成一万页时O(1) 还是那一下O(log n) 从10次变成14次O(n) 从1000次变10000次O(n²) 直接翻了一亿倍的计算量。这就是增长率的力量。2.3 一套行之有效的三步法任何代码都能套用的复杂度分析流程面对一段代码怎么快速确定它的时间复杂度我总结了一个三步法新手直接照做基本不会翻车第一步找出输入规模 n。通常就是数组的长度、循环的边界、递归的入参。先搞清楚谁是 n。第二步找到循环或递归结构数执行次数。重点是看每层循环的迭代次数而不是循环体里写了多少行代码。循环体里就算有十行代码只要它们是顺序执行的没有嵌套循环整体还是 O(1) 的重复操作真正决定复杂度的是这个循环体一共被执行了多少次。第三步写出 T(n) 或直接套用典型公式。单循环一般是 O(n)双层嵌套一般是 O(n²)但要小心内层循环的边界后面会讲每次规模砍半的循环是 O(log n)递归的话要看递推式我们放到下篇讲。我们来拿一个经典例子练手。求一个二维 n×n 矩阵的所有元素之和def sum_matrix(mat): total 0 n len(mat) for i in range(n): # 外层循环 n 次 for j in range(n): # 内层循环 n 次 total mat[i][j] return total外层执行 n 次每次内层又执行 n 次所以最内层的 total mat[i][j] 一共执行了 n × n n² 次。其他语句都是 O(1)。因此 T(n) n² O(n)大O记作 O(n²)。这就是数嵌套层数的直觉来源。但请注意这只是最朴素的场景。现实中循环的变量不一定都是沿 1 递增的内层边界也不一定都是 n很多新手就是在这里开始踩坑的。3. 核心实战从循环结构推导复杂度的完整过程3.1 线性循环最简单的起步案例先从一个单层循环入手把基本功打扎实。def find_max(arr): max_val arr[0] # 1次读取 for num in arr: # 循环 n 次 if num max_val: # 每次1次比较 max_val num # 有可能执行但最多也是1次赋值 return max_val这个函数里最坏情况下每次都要赋值所以循环体内大约是2次操作总操作数 T(n) 1 2n 1 2n 2。主导项是 2n去掉系数O(n)。注意一个细节无论循环体里是 if 分支还是多行顺序语句只要没有嵌套循环单层循环的复杂度永远是 O(n)。循环体里的语句再多也只是 O(1) 的常数倍不会改变增长级别。这一点想通之后分析很多代码都会快很多。另一个值得说的是顺序结构一段代码里先有一个 O(n) 的循环后面又有一个 O(n) 的循环总复杂度是多少是 O(n) O(n) O(2n)去掉系数还是 O(n)。两个独立的单层循环不会因为写了两个就变成 O(n²)很多人在这里有误解。O(n²) 必须来自嵌套不是并列。for i in range(n): print(arr[i]) for j in range(n): print(arr[j])这段代码两个循环并列总执行次数是 2n大O是 O(n)。但如果把第二个循环写进第一个循环体内部那才是 n×n n²。3.2 嵌套循环别急着说O(n²)先看内层干什么双循环是最容易产生错觉的地方。很多人一看到两层循环条件反射就写 O(n²)但这是不对的。准确的判断方法是算出内层循环体在给定的外层迭代下到底会执行多少次然后把所有外层迭代的执行次数累加起来。我们来看一个经典例子cnt 0 for i in range(n): # i 从 0 到 n-1 for j in range(i): # j 从 0 到 i-1注意上限是 i不是 n cnt 1内层执行次数和外层的 i 有关i0时执行0次i1时执行1次i2时执行2次……in-1时执行 n-1 次。总执行次数是T(n) 0 1 2 ... (n-1) n(n-1)/2展开是 (n² - n)/2 0.5n² - 0.5n。大O只留最高阶主导项结果还是 O(n²)。所以这个例子的复杂度确实是 O(n²)但理由不是两层循环就是平方而是内层循环总次数是 123...n 这种等差数列求和结果落在 n² 级别。再看一个更隐蔽的例子内层循环变量不是逐个加1cnt 0 for i in range(1, n): # i 从 1 到 n-1 for j in range(i, n): # j 从 i 到 n-1 cnt 1内层执行次数是 n-i 次。把所有 i 累加起来i1时 n-1 次i2时 n-2 次……in-1时1次。总和也是 (n-1) (n-2) ... 1 n(n-1)/2大O同样是 O(n²)。虽然内层循环的起点往外挪了但总的半三角规模仍然是平方级。还有一种常见的套路循环变量按倍数变化这里预告一下后面避坑里细讲cnt 0 for i in range(1, n): for j in range(i, n, 2): # j 每次增加2 cnt 1内层执行次数大约为 (n-i)/2累加起来大约是 n²/4仍然是 O(n²)。只有在循环变量呈指数增长时复杂度才会落到对数级。这是区别分析的重点。所以我的建议是不要背几层循环 几次方而是养成求和的思维习惯。每次遇到嵌套循环就老老实实把最内层执行次数写成关于外层变量的式子然后求总和看总和落在哪个增长级别。这个习惯能帮你躲过绝大多数双循环的坑。3.3 对半分割二分查找的对数复杂度推导对数级复杂度是初学者的第二个坎。很多人知道 O(log n) 这个记号但不知道它到底是怎么从代码里长出来的。我们来完整推导一遍二分查找。def binary_search(arr, target): left 0 right len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1关键看 while 循环的规模变化。每次循环要么直接返回要么把搜索区间 [left, right] 砍掉一半——注意这里不是每轮循环处理一个元素然后往前走而是每轮循环都把剩余数据量减半。假设初始区间长度是 n。经过第一轮之后区间长度变成 n/2第二轮之后变成 n/4第三轮之后变成 n/8…… 我们要问的是区间长度一直砍半砍到小于1之前最多能砍多少次设砍了 k 次之后区间长度为 n/(2^k)。当这个值小于1时循环结束所以n / (2^k) 1即 n 2^k两边取以2为底的对数得到k log₂(n)所以循环最多执行 log₂(n) 次实际场景会取整。这就是二分查找复杂度 O(log n) 的完整推导过程。大部分教材会直接告诉你答案但如果你自己动手推导过上面这个不等式你就会真正理解为什么每次规模减半对应对数复杂度。以后你再遇到每次除以10每次去掉一半这类结构都可以快速反应出对数级别的复杂度。顺便给一个直观的体感数据如果 n 1000000线性查找最多需要100万次比较而二分查找最多只需要20次因为 2²⁰ ≈ 1048576。这个差距在数据量大的时候是毁灭性的。更好的理解方式是把对数想象成反向指数。指数是每走一步规模翻一倍对数则是每走一步规模砍一半。二分查找之所以常见是因为它充分利用了有序这个前提让每次比较都能排除掉一半的错误答案。4. 那些年大家经常算错的场景复杂度分析避坑指南4.1 循环变量是 i i * 2不是 i最经典的一个坑看到一层循环就写 O(n)但这只在循环变量以常数步长递增时成立。如果循环变量是翻倍增长的复杂度就完全变了。i 1 while i n: i i * 2很多人第一反应是这是个 while 循环而且 i 从1变到 n所以是 O(n)。错。我们来实际模拟一下 i 的取值i 1, 2, 4, 8, 16, 32, ...这个序列是 2⁰, 2¹, 2², 2³, 2⁴, ...。循环要执行到 i n 才停止。假设执行了 k 次那么第 k 次时 i 2^k需要满足 2^k n即 k log₂(n)。所以循环至多执行 log₂(n) 1 次复杂度是 O(log n)。这类循环的核心特征是循环变量的增长方式不是每次加常数而是每次乘以常数。同理如果写的是 i i * 3那么执行次数是 log₃(n)大O记作 O(log n)不同底数的对数只差一个常数系数大O统一写 O(log n)不需要纠结底数。再对比一下让你对数量级差距产生体感n 1000000循环变量 i执行100万次循环变量 i * 2执行约20次这就是 O(n) 和 O(log n) 的差距。在算法题里很多超时问题就是因为把乘2错看成了加1级别。4.2 提前退出与最坏情况别拿平均当复杂度第二个常见误区是拿平均情况或运气好的情况来计算复杂度。比如def find_first(arr, target): for i in range(len(arr)): if arr[i] target: return i # 提前返回 return -1如果运气好第一个元素就是要找的 target那么循环执行 1 次就结束了——但这不代表这个函数是 O(1)。因为当 target 不在数组里或者出现在最后一个位置时整个循环要完整跑完 n 次。复杂度分析通常关注的是最坏情况worst case也就是输入让算法做最多操作的那种情况。所以上面这个函数的复杂度是 O(n)。你可能会说那平均情况呢平均情况下如果 target 均匀分布期望比较次数是 n/2去掉常数系数还是 O(n)。所以无论从最坏还是平均角度结论都是 O(n)。判断原则是遇到 break、return 提前退出先分析最坏情况。只有在最坏情况也是常数次时比如有哈希表辅助才能说复杂度低于 O(n)。更严谨地说如果某个优化逻辑能让最坏情况真正降级那就必须体现在算法的整体设计上而不是靠有可能会提前命中来碰运气。4.3 两个输入规模O(n m) 还是 O(n * m)第三个高频翻车点出现在有两个独立输入规模的场景。很多人看到两个循环就笼统地写 O(n²)实际上要先判断这两个 n 是同一个数据源还是两个不同的数据源。def merge_info(list_a, list_b): for a in list_a: # 假设 list_a 长度是 n print(a) for b in list_b: # 假设 list_b 长度是 m print(b)两个循环并列各跑各的总执行次数是 n m复杂度记作O(n m)。这里只要 n 和 m 相互独立就不能合并成 O(n²)——因为 m 可能只有10n 可能有一百万实际工作量就是一百万的线性级别。但如果是嵌套的呢def compare_lists(list_a, list_b): for a in list_a: # n 次 for b in list_b: # m 次 if a b: print(a)外层 n 次内层 m 次总执行次数是 n × m复杂度记作O(n × m)。如果 n 和 m 恰好都等于 N比如两个数组长度相同这时才可以写成 O(n²)。我见过很多人在写双数组比较时直接套用双循环O(n²)导致复杂度分析失真。正确的做法是先看循环的嵌套关系再分别确认每个循环的规模各自是什么然后用求和或者求积的方式组合。并列循环用加法嵌套循环用乘法这是最基本的规则。还有一种混合情况是遍历一个 n×m 的矩阵for i in range(n): for j in range(m): process(mat[i][j])矩阵有 n 行 m 列总共 n×m 个元素所以复杂度是 O(n×m)。如果矩阵是方阵m n就是 O(n²)。4.4 一个容易被忽略的细节循环条件里的函数调用最后提醒一个实战中特别容易踩的暗坑循环条件里如果调用了函数这个函数本身的复杂度也必须算进去。while is_valid(arr, i, n): # 假设 is_valid 是 O(k) i 1如果 is_valid 每次调用复杂度是 O(n)循环本身执行了 n 次那么总复杂度是 O(n × n) O(n²)而不是 O(n)。很多性能问题就是藏在这种看着像单循环、实则每次循环都做了一次线性扫描的代码里。分析的时候一定要把循环条件、循环体里所有函数调用的复杂度都展开再做叠加或累乘。5. 实用工具与自检方法如何验证你的复杂度判断5.1 通过增长实验来验证用数据反推复杂度理论分析做完之后我强烈建议你做一个简单的增长实验来验证判断。这个方法不需要任何工具只需要一段带计时功能的代码。思路是这样准备一组不同的输入规模比如 n 1000, 2000, 4000, 8000, 16000分别跑同样的算法记录运行时间。然后观察时间随 n 翻倍的变化倍数如果 n 翻倍时间也翻倍 → 这是 O(n) 的特征。如果 n 翻倍时间约为原来的4倍 → 这是 O(n²) 的特征。如果 n 翻倍时间几乎不变或只增加一点点 → 这很可能是 O(log n)。如果 n 翻倍时间约为原来的2倍多一点 → 这可能是 O(n log n)。因为 log n 那一项让时间比翻倍略高。我拿前面的 find_max 函数举个例子。你在 n10000 时跑出0.0001秒假设环境稳定n20000时大概0.0002秒n40000时0.0004秒——时间稳定地和 n 成正比那就是标准的 O(n)。如果你写一个双层循环的矩阵遍历n1000时0.01秒n2000时0.04秒n4000时0.16秒——每次翻倍时间变成4倍毫无疑问 O(n²)。这个方法有个前提n 必须足够大大到主导项已经压过低阶项和常数开销。n 太小时系统调度、函数调用开销、Python解释器本身的固定成本会干扰判断。所以实验时建议把 n 从几千起步逐步加大看趋势是否稳定。5.2 复杂度分析的边界意识什么时候该较真什么时候可以估算掌握了这么多规则之后我想说一个实战中很重要、但教材很少提的点复杂度分析不是每行代码都要做到精确你需要的只是数量级正确。在实际写业务代码时我一般这样操作先按上面的三步法快速估计每个主要函数的时间复杂度记在注释里或心里。重点关注那些被高频调用的函数比如每个请求都会执行的核心逻辑、嵌套在循环里的辅助函数。这些是性能瓶颈的集中地必须精确分析。对于只执行一次、或者数据量固定的初始化逻辑哪怕它是 O(n³)只要 n 永远是一个小常数比如固定32个配置项也不值得花心思优化。这里有一个经典的场景你在写一个配置文件解析器配置项永远不超过100个就算你写了个 O(n²) 的冒泡排序去处理它们它对整体性能的影响也是零。所以复杂度分析要结合实际的数据规模而不是机械地追求所有代码都最优。5.3 一个顺手可用的自检清单文章快结尾了我把这些年带新人总结出来的自检清单分享出来每次写完代码对照着过一遍你是否清楚地指出了输入规模 n 是什么有没有多个输入规模需要分别标记每个循环的迭代次数表达式是否写清楚了内层边界和循环变量变化是否考虑到了i还是i*2是否有嵌套循环嵌套的执行次数是用加法合并还是用乘法合并循环内部和循环条件里是否有额外的函数调用它们的复杂度是否已经计入遇到 break、return 提前退出时是否分析的是最坏情况代码里的常数系数和低阶项是否在最后阶段被正确丢弃这套清单覆盖了我上面讲的绝大多数坑。新手上路时每道题、每段核心代码都按这个流程走一遍练上一个月你看到任何代码都能在几秒钟内写出准确的复杂度不需要再猜。我在实际评审代码时最看重的其实不是一个人能写出多巧妙的算法而是他能否快速判断这段代码在不同数据规模下的表现。只要这个意识到位了很多性能问题在设计阶段就能被发现并避免。这也是我为什么坚持先从复杂度分析讲起的原因——它是后续一切性能调优、算法设计、系统架构的地基。