从上一篇数据结构笔记走到今天已经完成了线性表、树、图、散列这些“数据容器”的学习。可很多人会有同样的困惑数据结构学完接下来到底学什么为什么一定要有算法这一说其实答案很直接数据结构负责把数据存下来、组织好但数据本身不会自己动起来让它被查询、被排序、被转换的就是算法。这是整个数据结构学习笔记系列里承上启下的一篇所以我会把算法的定义、核心特性、评价标准以及时间复杂度和空间复杂度这两把“度量尺子”从头捋一遍。这篇笔记面向两类人一类是正在学数据结构与算法的初学者手头有代码基础但还没建立“如何分析算法好坏”的思维框架另一类是准备面试、需要把复杂度分析讲清楚的同学。我会尽量用生活化的类比把概念说透再配上可以直接复现的代码示例最后分享一些实际学习过程中的经验与教训。看完你会发现算法不是玄学本质就是一套有规矩、讲效率的解题步骤。1. 拿“查找电话号”开场理解数据结构与算法的真实关系1.1 数据结构是骨架算法才是让数据“动起来”的使用说明先想一个特别常见的场景手机通讯录里存着几千个联系人现在你要找一个叫“张三”的人的电话。如果通讯录是按姓名拼音排序的你可以翻到“Z”开头的那一页然后顺着找——这个过程的底层数据结构就是有序数组或跳表。如果通讯录没有排序只是按添加顺序排你恐怕只能从头滑到尾这个时候用的可能就是一个链表或者无序数组。同一个需求因为底层数据结构不同查找方式完全不同效率也差了好几个量级。可见数据结构决定了数据“怎么放”而算法决定了数据“怎么用”。只学数据结构不学算法就像买了一整套工具箱却不知道每个工具该怎么使。数据结构学习笔记系列的第一篇讲了存储和组织这一篇则要回答一个问题怎么优雅地把数据里面的答案取出来。1.2 为什么不能只靠“跑一下看看快不快”来评价算法很多人判断代码好坏的方式很原始输入一组数据跑一下感觉挺快那就行了。但这样会踩坑。同一份代码在一台高性能机器上运行只要 0.1 秒换到低配机器上可能要 1 秒输入 100 条数据很快换成 100 万条数据就可能卡死。你观察到的“快”和“慢”是硬件、语言、编译器、数据规模综合作用的结果并不能真正反映算法本身的优劣。所以计算机科学给出了一套更稳定的评价方法不看绝对时间而看“当数据规模 n 变大时操作次数怎么变”。这个思想就是时间复杂度的来源。同样地除了时间还要看内存占用这就是空间复杂度。这一篇的核心目标就是把这两把尺子的使用方法练熟让“评价算法”这件事不再靠感觉而是有一套可以推理和运算的逻辑。2. 算法的定义与五大特性不是所有步骤都能叫算法2.1 算法的官方定义与通俗翻译教材里的定义通常很严谨算法是对特定问题求解步骤的一种描述是指令的有限序列。每一条指令表示一个或多个操作。听起来很绕其实用大白话说就是你为了解决一个问题把操作步骤一步一步写清楚每一步都能被计算机机器理解并执行而且步骤不能无限多必须有个头。我把“算法”类比成菜谱。菜谱规定了食材输入、规定了步骤加工流程、最后必须产出菜品输出。你不能写“把鱼煎到差不多熟”这种模糊步骤因为每个人理解不一样你也不能写“等海枯石烂再出锅”因为那根本没有穷尽的时候。算法也是这样每一步都要精确到计算机能照着做必须在有限步内结束。2.2 五大特性逐条拆解附带故障案例第一个特性是有穷性。算法必须在执行有限步之后终止。写while(1)这种死循环确实是程序但不是算法。这里有个微妙之处操作系统和服务器程序理论上可以永远运行它们通常被称为“程序”而不是“算法”因为不满足有穷性要求。考试里如果问“算法和程序的区别”这是最常出现的答案。第二个特性是确定性。算法的每一步必须有明确的定义不能有歧义。比如“把 count 设成一个较大的数”这句话计算机没法执行因为“较大的数”没有边界。再比如“如果数据很多就执行 A 方案否则执行 B 方案”这里“很多”也是模糊的必须写成“如果 n 大于 1000 执行 A否则执行 B”。在实际代码里这个特性提醒我们要写清楚判断条件避免用模棱两可的自然语言替代精确逻辑。第三个特性是可行性。算法中每一条运算都必须是已经实现的基本操作在有限时间内可以完成。比如“对数组进行排序”是一个可行的操作因为排序已经被证明可以分解成基本的比较和交换但“求出所有整数中最大的一个”就不可行因为整数没有边界这本身就不是一个有限步骤能解决的问题。可行性保证了算法不只是纸上谈兵而是真的能在计算机上落地。第四个特性是输入。一个算法可以有零个或多个输入。零输入很常见比如一个算法专门生成某个随机数序列不需要外部输入多数算法则有明确输入比如排序算法的输入是待排序数组。输入的数值和规模会直接决定算法的行为后续复杂度分析也都围绕输入规模 n 展开。第五个特性是输出。算法必须有至少一个输出。输出的形式和内容由问题定义可能是计算结果可能是判断结论也可能是一组操作指令。没有输出的算法没有意义因为你说不清它到底解决了什么。五个特性合在一起其实是一道“质检门”只有同时满足有穷、确定、可行、有输入、有输出的步骤序列才有资格被称为算法。3. 评价算法的尺子正确性、可读性、健壮性、效率与存储3.1 正确性能答对但别只答对“标准答案”正确性是算法的底线。一个算法如果在合法输入下给出错误结果那它一切免谈。但要注意正确性不是说“常见输入下结果对”就完了还要考虑边界空数组能不能处理只含一个元素的数组对不对所有元素都相等的数组排序后是否稳定这些边界情况正是初学阶段最容易翻车的地方。以排序为例拿一个数组[5, 2, 9, 1]测一下结果排序正确很多人就放心了。可一旦换成空数组[]有些实现会越界崩溃换成已经排好序的数组[1, 2, 3, 4]某些快速排序写法反而会退化到 O(n^2)。所以说正确性验证需要系统性地覆盖普通输入、边界输入、非法输入三类情况而不是跑通一两个示例就收工。3.2 可读性与健壮性写给机器运行更是写给人类维护很多初学者为了追求代码行数少写出很难读的算法。但现实项目里一段代码被读的次数远比被写的次数多。可读性差的算法哪怕性能很好也很难上线维护。一个常见的原则是变量名要有意义循环边界写清楚关键思路配上注释。算法本质是思想的表达如果代码跟天书一样那思想再好也传不出去。健壮性衡量的是算法在面对非法输入时的表现。用户可能传入负数、可能传入超长数据、可能传入格式错误的内容。一个健壮的算法应当能做出合理反应——返回错误码、抛出明确异常或者用默认值兜底而不是直接让整个程序崩溃。专栏里我常提一个比喻一个健壮的算法像火车站闸机有人刷了无效卡闸机礼貌地提示错误而不是直接把整站系统卡死。3.3 时间效率与存储开销算法评价的两条硬指标可读性、健壮性和正确性解决的是“对不对”和“好不好维护”的问题接下来“效率”和“存储”则直接回答“值不值得用”。时间效率指的是算法运行所需的时间随输入规模增长的趋势存储开销指的是算法运行过程中占用的内存空间随输入规模增长的趋势。这两个维度往往彼此冲突。比如把大量已经计算过的结果缓存起来时间会快很多但内存占用会上升反过来完全不用额外空间可能就要重复计算时间就会变长。工程上常说“以空间换时间”或者“以时间换空间”本质上就是在两把尺子之间找平衡。接下来的两个大章节分别把时间复杂度和空间复杂度讲清楚因为这两件事是评价算法效率最核心、也是考试和面试里最常考的部分。4. 时间复杂度详解从“秒表计时”到“增长趋势”4.1 为什么用大O记号而不是直接测量运行秒数直接计时不靠谱前面已经解释过原因机器性能、编程语言、编译器优化都会干扰测量结果。所以算法分析采用了一个很聪明的思路抛开机器的绝对速度用数学函数去描述“操作次数 T(n) 与输入规模 n 之间的关系”再用大O记号把这个关系的增长趋势简化出来。大O记号的实际意思是“渐近时间复杂度”它只关心 n 趋向无穷大时T(n) 的增长上界。举个例子某个算法一共执行3n^2 5n 8次基本操作当 n 越来越大时5n 8的影响会越来越小3n^2成为主导。大O记号把这串表达式压缩成 O(n^2)代表它的核心特征是按平方量级增长。4.2 常见复杂度排序与典型代码形状从低到高常见的复杂度依次是O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2^n)。我根据日常写代码的习惯把它们和具体代码形状对应起来。O(1) 最常见的是数组按下标取值一次内存访问时间恒定O(log n) 的经典案例是二分查找每轮把搜索区间减半O(n) 是单层遍历比如求数组最大值O(n log n) 是高效排序的上限比如快速排序和归并排序的平均情况O(n^2) 常见于两层嵌套循环比如冒泡排序、选择排序的朴素写法O(2^n) 则是指数级增长常见于暴力枚举子集比如递归求斐波那契数列的朴素实现。为了方便查阅我把典型复杂度、直观含义和常见例子整理成一张对照表大O记号通俗含义典型场景O(1)常数时间与数据量无关数组按下标访问O(log n)对数时间数据量翻倍只增加一步二分查找O(n)线性时间与数据量成正比单层循环求最大值O(n log n)线性对数时间快速排序、归并排序平均情况O(n^2)平方时间不适合大规模数据冒泡排序、两层嵌套循环O(2^n)指数时间数据稍大就跑不动朴素递归求斐波那契4.3 大O的推导规则不用算精确次数抓住最高阶项面对一段代码我不建议一行一行去数操作次数太容易数错了。更实用的方法是记下三条规则。规则一忽略常数系数。比如 2n、3n、10n在大O记号下统统写成 O(n)因为常数不会改变增长趋势。规则二只保留最高阶项。比如n^2 n 100直接写成 O(n^2)低阶项和常数项在大 n 面前都不起作用。规则三顺序代码求和嵌套代码相乘。两个并列的循环各自是 O(n)整体还是 O(n)两层嵌套循环外层跑 n 次、内层也跑 n 次整体就是 O(n^2)。我用一段求数组与标量乘积的代码演示这个推导过程。def scale_array(arr, factor): result [] for value in arr: # O(n) result.append(value * factor) # 常数时间操作 return result单层循环遍历了 n 个元素每个元素做一次乘法再入列表这都属于 O(1) 的操作所以整体是 O(n)。再看一个嵌套循环的例子。def bubble_sort(arr): n len(arr) for i in range(n): # 外层跑 n 次 for j in range(n - i - 1): # 内层平均约 n/2 次 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j]外层 O(n)内层 O(n)嵌套相乘得到 O(n^2)。这里不必纠结内层次数累积到底是多少次反正它的增长上界是 n 的数量级。4.4 二分查找的复杂度为什么是 O(log n)一个反直觉但必须吃透的例子单独拿出二分查找来说是因为初学者很容易怀疑这个循环明明也是嵌套结构为什么复杂度不是 O(n^2)核心在于内层循环的迭代次数不是 n而是每次都砍半。def binary_search(arr, target): left, right 0, 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每次循环都把查找区间缩小一半n 变成 n/2再变成 n/4直到区间长度为 1。查找次数 k 满足 n / 2^k 1所以 k log2(n)复杂度就是 O(log n)。这个例子的价值在于提醒我们看到“循环”不要急着断定 O(n)要关注循环变量的变化方式是真的一次步进 1还是每次都指数级收缩。4.5 最好情况、最坏情况与平均情况只报“平均”容易误事同样的算法不同输入下表现可能天差地别。以快速排序为例数组本来就有序时如果选第一个元素做基准复杂度会退化到 O(n^2)但平均情况下它能在 O(n log n) 内完成。所以讨论复杂度时要说清楚讨论的是最好、最坏还是平均。工程实践中最坏情况是我们最应该关注的因为它决定了算法是否可能出现灾难性崩溃。比如在实时系统里一个请求平均响应 5 毫秒并不够必须保证最坏情况也在可接受范围内。写分析时我习惯同时标注三段例如“平均 O(n log n)最坏 O(n^2)”这样信息更完整也更严谨。5. 空间复杂度详解内存账本与递归栈的隐形开销5.1 空间复杂度衡量的是什么空间复杂度描述的是算法运行时需要的额外内存空间随输入规模 n 变化的趋势。注意“额外”两个字输入数据本身在内存里占用的空间一般不计入算法的额外开销因为那是给定的算法无法改变。真正要关注的是算法为了完成任务临时开辟了多少辅助空间。举个直观的例子给数组求和如果只用一个变量累积结果除了输入数组本身之外没有额外内存空间复杂度为 O(1)如果先把所有元素复制到新数组再求和额外空间就是 O(n)因为复制出来的数组长度随 n 线性增长。5.2 原地算法与常数空间最省内存的方案不依赖额外数据结构的算法常被称为原地算法比如冒泡排序、选择排序。它们通过不断地交换原数组中的元素来完成排序除了默认的几个临时变量外没有申请长度为 n 的新数组因此空间复杂度是 O(1)。一个典型的反例是归并排序。归并过程需要额外的临时数组来存放两个有序子序列合并后的结果这个临时数组的长度和原数组相同所以归并排序的空间复杂度是 O(n)。不少人在分析时只关注时间把归并排序写进简历又答不上来空间开销这是一个值得注意的细节。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result这里每一层递归都生成若干临时切片虽然实际运行时切片会被回收但在做理论分析时整体额外空间是 O(n)因为合并的那一层需要一条与原数组等长的临时序列。写这一个例子是为了说明代码中的arr[:mid]看起来是切片操作但它实实在在创建出了新的列表这就是空间占用。5.3 递归栈空间最容易被忽略的空间开销递归算法的空间复杂度与递归调用深度直接相关。每调用一次递归函数系统都会在调用栈上压入一块栈帧保存当前函数的局部变量、参数和返回地址。递归深度是 k栈空间就是 O(k)。以朴素递归计算斐波那契数列为例def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)它的时间复杂度和空间复杂度完全是两回事。时间复杂度是指数级 O(2^n)因为同一个子问题被反复计算了好几遍但空间复杂度只有 O(n)因为在任意时刻调用栈上最多同时存在 n 层递归。很多人只记住“斐波那契递归很慢”却说不上来为什么内存没有爆其实就是没分清“调用总次数”和“最大递归深度”的区别。画一个递归调用树的草图就能看清fib(5) 会调用 fib(4) 和 fib(3)fib(4) 又会调用 fib(3) 和 fib(2)。虽然总共调用了很多次但调用树深度最深的路径只是从 fib(5) 一路走到 fib(0)深度为 n。空间复杂度只看同一时刻栈上有多少帧所以是 O(n)。这个区分非常重要——时间看累计工作量空间看同时占用深度。5.4 空间与时间的权衡没有“绝对最优”只有“当前最合适”工程里经常不得不在空间和时间之间做取舍。一个很常见的例子是缓存把反复查询的结果提前计算好随取随用能让时间从 O(n) 降到 O(1)但代价是额外内存。另一个例子是动态规划很多入门教程会把二维 DP 表存下来空间 O(n^2)但某些问题可以用滚动数组把空间压到 O(n)代价是丢掉历史状态后续回溯可能不方便。所以做题和项目选型时我会把两个维度分开写出来再结合场景拍板。如果内存稀缺优先考虑时间换空间如果响应速度是生命线空间贵一点也值得。复杂度分析真正的价值不是算出两个数字而是让你在做这种取舍时有依据。6. 实操心得学习复杂度的常见误区与避坑建议6.1 不要被常数和低阶项迷惑但也不要彻底无视它们初学大O时很多人会陷入“复杂度越低一定越好”的误区。这个判断大部分时候成立但也有例外。O(n^2) 和 O(n log n) 的差距在 n 很大时非常明显可如果 n 只有几百O(n^2) 带上很小的常数因子完全可能跑得比一个常数因子巨大的 O(n log n) 更快。分析算法可以看渐近复杂度实际选型还得结合数据规模和常数因子。记得我之前处理过一个数据量只有几千行的小任务。理论上应该用堆排序达到 O(n log n)但因为数据规模太小直接在数组上做插入排序 O(n^2) 反而更快——因为没有额外堆结构也没有频繁的指针移动。这说明复杂度描述的是增长速度不是绝对速度小规模时实测一下往往比脑补更靠谱。6.2 遇到嵌套循环先看循环变量怎么变很多同学拿到嵌套循环直接写 O(n^2)在 90% 的场合没问题但二分查找、分层遍历之类的场景会翻车。正确的分析习惯是观察循环变量的变化方式如果循环变量每次加 1跑满 n 次这一层的量级是 n。如果循环变量每次减半跑 log2(n) 次这一层的量级是 log n。如果循环变量每次乘以 2同样是 log n 量级。如果外层 n 次且内层每次也到 n才是 O(n^2)。还有一个经典陷阱是两层循环但内层是固定次数比如外层跑 n 次、内层固定跑 5 次那总复杂度其实是 O(n)不是 O(n^2)。展开来看固定次数的循环相当于常数忽略常数后只剩下外层的一层 n。6.3 分析空间复杂度时把“调用总次数”和“递归深度”分开算前面提过空间复杂度取决于递归深度时间取决于总调用次数。这组概念特别容易混。每次递归调用都会产生栈帧但同一时刻栈上只会保留当前调用链上的帧已经返回的调用会弹出。所以哪怕某个递归算法总共调用了一万次只要最大深度是 50栈空间就是 O(50)不会因为一万次而爆。实操中判断递归深度可以先画出调用链。比如二分查找的递归实现每次只递归一侧深度是 O(log n)归并排序每次分成两个子问题但需要等左半递归完成再开始右半栈上深度是 O(log n)朴素斐波那契递归虽然调用树巨大但最深路径是 n所以栈深度是 O(n)。分清楚这两个概念不仅能应对考试也能帮助你判断生产环境里递归会不会压爆栈。6.4 做练习时把复杂度分析写成注释形成肌肉记忆最后分享一个我自己一直在用的练习方法每写完一段算法代码在方法签名下方用注释写出时间和空间复杂度并简单写下推导过程。比如这个注释模板# 时间O(n)单层循环遍历整个数组 # 空间O(1)只用了常数个变量 def max_value(arr): if not arr: return None result arr[0] for value in arr[1:]: if value result: result value return result这个习惯很朴素但对训练算法思维非常有效。坚持一段时间后你会在读别人代码时自动估算复杂度写新算法时提前评估性能风险面试里被问到复杂度时也能脱口而出。复杂度分析是数据结构学习中最容易被低估的基础能力它不会直接帮你写出花哨的代码却决定了你写的代码能不能扛住真实的数据规模。这篇笔记到这儿已经足够完整——从定义和特性入手再分别解释了时间与空间复杂度最后补充了学完之后的落地练习方法。你只要能亲手分析几个经典算法的复杂度再对照这个笔记里的推导过程检查一遍算法入门这一步就算真正踩实了。下一篇开始可以安心地往查找和排序算法的具体实现里钻了。