学数据结构绕不开算法算法入门这一篇我拖了很久才写因为这块内容看似简单实际上很容易让人觉得“看书全会做题全废”。定义背得滚瓜烂熟一到手写代码就不知道复杂度怎么算了。这篇笔记我尽量用大白话把算法的定义、特性、评判标准、时间复杂度和空间复杂度一次讲透适合正在学数据结构的学生、准备面试的开发者以及想补基础的自学者。先放个结论算法不是公式不是某种高深的数学技巧它本质上是“解决问题的一套明确步骤”。你在食堂排队打饭有步骤你收拾行李出远门有步骤你让程序把一组数字从小到大排好也需要步骤这套步骤就是算法。真正难的不是理解这句话而是后面几个概念有穷性、确定性、可行性、输入输出以及复杂度怎么算。我当初学的时候总觉得这些是废话直到自己在项目里写出一个死循环导致程序卡死才意识到算法的这些基础约束每一条都在解决实际工程问题。1. 算法到底是个什么东西从“菜谱”聊到五个特性1.1 算法不是公式是解决问题的完整步骤很多人把算法跟“公式”划等号比如看到“二分查找”“快速排序”就觉得是一堆数学推导其实不是。算法更像一份菜谱。菜谱告诉你第一步洗菜切菜第二步热锅倒油第三步下锅翻炒第四步调味出锅每一步都有明确的操作对象和操作方式。算法也一样它告诉你第一步处理什么数据第二步做什么判断第三步怎么循环第四步返回什么结果。区别在于菜谱的读者是人人的脑子会自动补全模糊信息。比如菜谱写“盐适量”你能理解是凭口味判断。算法没有这个待遇执行它的计算机是一个没有常识的“铁憨憨”你少说一个边界条件它就不知道怎么办。所以算法的定义里藏着一条核心要求步骤必须精确到指令级。举个例子。你要写一个“判断一个数是不是偶数”的算法。步骤可以是第一步拿到一个整数n第二步计算n除以2的余数第三步如果余数为0返回“是偶数”第四步否则返回“不是偶数”这四步就是一个完整的算法。不涉及任何高深数学但它的逻辑是闭环的。学算法入门最该建立的认知就是算法是“步骤的集合”代码只是步骤的表达形式。同一个算法可以用C写用Java写用Python写甚至用自然语言写核心步骤不变。1.2 五个特性少一个都不行教科书里对算法的定义通常包含五个特性我当年觉得这是在凑字数实际踩坑之后才明白每一条都对应一种真实故障。有穷性算法必须在有限的步骤内结束。这是最容易被忽略、后果最严重的一条。我实习的时候写过一个数据同步程序里面有个while循环判断条件写反了程序运行起来不报错也不退出CPU直接飙满最后还是靠运维强制重启才救回来。这就是典型的违反有穷性。注意有穷性不是指程序运行时间必须很短而是指必须“能停得下来”。哪怕算一个超大数的分解需要跑一个月只要逻辑上能在有限步骤内完成就算满足反之逻辑上根本没有终止条件的死循环就是算法级故障。确定性算法的每一步都要有明确的含义不能有歧义。比如“把数组里的数字处理好再返回”这句话就不是确定性描述什么叫“处理好”是排序、去重、还是归一化机器无法执行有歧义的指令。写算法的时候每个分支都要明确每个操作对象都要指名道姓。可行性算法中的每一步都能通过有限次运算实现。有些算法从数学上很漂亮但实现不了比如“在有限时间内穷举所有可能的密码组合”理论上可行实际上因为计算资源根本不够不具备可行性。设计算法不能只考虑“对不对”还要考虑“做不做得到”。输入一个算法可以有零个或多个输入。零输入的情况也存在比如“生成一个固定图案”不需要外部数据直接输出就行。但大多数算法需要输入输入的规模和类型决定了算法的边界。输出算法必须有至少一个输出。没有输出的算法没有意义因为你不知道它到底干了什么。用数学语言说算法是一个从输入到输出的映射输出就是映射的结果。比如排序算法的输出是排好序的序列查找算法的输出是目标位置或“未找到”的标记。这五个特性不需要死记可以把它当成“算法体检清单”写出来的步骤能不能停每一步有没有歧义每一步能不能执行有输入吗有输出吗五个都通过才是一个合格的算法。2. 怎么判断一个算法是不是好算法评判标准选型2.1 正确性、可读性、健壮性、高效性怎么权衡符合五个特性的算法只能说“能用”不能说“好用”。评价一个算法好不好业界标准很明确四个维度正确性、可读性、健壮性、高效性。正确性是底线。算法必须能解决它该解决的问题得到正确的结果。但“正确”本身有等级对所有合法输入都正确是最强等级对大部分常见输入正确、边界情况出错是较弱等级。我自己写代码的习惯是先用几个普通测试用例再专门测试空数组、只有一个元素、全是重复元素这些边界边界通过才算正确性过关。可读性是给程序员看的。同样的功能有的人写出来的代码一眼就懂有的人写出来像加密文件。可读性差的算法自己三天后回来看都要猜半天更别说团队协作。一个典型例子用位运算交换两个变量的值a ^ b; b ^ a; a ^ b;这在某些大牛眼里很优雅但在团队项目里直接写temp a; a b; b temp;才是正常人能理解的方式。算法的目标首先是沟通其次才是炫技。健壮性处理的是非法输入。用户传了空指针、负数、超大数组算法能不能给出合理反馈而不是直接崩溃我写过一个模拟项目X的导入模块没处理空文件输入结果测试同事传了个0字节文件进来程序直接数组越界。加了一行if (data.length 0) return就解决了这就是健壮性的价值。高效性包括时间效率和空间效率也就是下文要重点讲的时间复杂度和空间复杂度。四个维度里正确性是及格线可读性和健壮性是工程线高效性是竞赛和面试的追求线。学生时期我容易走极端要么死磕效率写出天书代码要么只顾实现简单写出O(n^3)的暴力解后来才明白合理的算法设计是在这四者之间找平衡点。2.2 数据结构与算法的伴生关系选对结构算法就成功一半既然这一系列笔记主题是数据结构这里必须先明确一个关系数据结构是算法的载体算法是数据结构的灵魂。没有数据结构算法无处施展没有算法数据结构只是静态的存储。举一个最典型的例子“给一组数字找出其中是否有重复元素”。第一种方案把数字放进一个数组用两层循环两两比较每比较一对就判断是否相等。这个方法代码简单但效率低数据量一大就变慢。第二种方案把数字放进哈希表边遍历边查如果某个数字已经存在就说明有重复。这个方案代码稍微复杂一点但速度快得多。同样的问题只是换了一个存储方式整体算法的效率就天差地别。所以学算法不能脱离数据结构这也是为什么这一系列把算法入门放在数据结构笔记的第二篇——先讲清楚“怎么衡量算法的好坏”后面学各种数据结构的时候才有标尺去对比它们的实际表现。我在给某跨平台系统做用户登录模块时也有类似的体会。刚开始用数组存储在线用户列表判断用户是否在线需要遍历整个数组在线人数上千之后接口响应肉眼可见地变慢。后来换成哈希表查找时间从线性降到常数级问题立刻解决。这不是算法多玄妙就是数据结构选对了。3. 时间复杂度程序跑得快不快的数学账3.1 大O到底在说什么别被符号吓到时间复杂度是最劝退初学者的概念上来就是O(1)、O(n)、O(nlogn)每个符号看着都像天书实际上理解起来非常朴素。时间复杂度的核心不是“这段代码跑了多少毫秒”而是“运行时间随输入规模增长的变化趋势”。你不需要精确计数只需要回答一个问题数据量从100变成10000运行时间大概会怎么变是几乎不变还是翻倍还是爆炸式增长大O记号就是描述这种趋势的工具。它的数学定义涉及极限但在工程实践里只需要记住一个简化版只保留最高阶项忽略系数忽略低阶项。举个例子。一段代码的执行次数是3n 5意思是输入规模为n时大约执行3n加5次操作。当n很大的时候5和系数3都影响不了大局真正决定增长速度的是n所以时间复杂度就是O(n)。同理执行次数是2n^2 3n 1最高阶是2n^2只保留n^2结果是O(n^2)。这个“忽略”不是不负责任而是因为复杂度分析关心的是量级不是精确次数。1秒和2秒的差异不重要1秒和1小时的差异才重要量级对比正好能体现后者。3.2 从代码到复杂度的三步推导法很多同学看书上的复杂度推导能看懂自己拿到一段代码就懵了。我总结了一个直白的三步流程第一步找到代码里的循环确定每个循环的执行次数第二步分析循环嵌套关系嵌套层数是几层次数就大致是几层相乘第三步套用大O简化规则去掉常数和低阶项比如这段代码for i in range(n): print(i)循环执行n次每次循环做一次打印总执行次数约n次复杂度O(n)。嵌套两层for i in range(n): for j in range(n): print(i, j)外层循环n次内层循环n次总次数n*n复杂度O(n^2)。再看一个稍微隐蔽一点的i 1 while i n: i i * 2循环变量不是每次加1而是每次翻倍。i的取值序列是1、2、4、8、16……直到超过n。循环次数约等于log2(n)所以复杂度是O(logn)。这里最容易出错的地方是误以为循环只是简单乘法没意识到翻倍增长会极快逼近边界。3.3 常见复杂度图谱从O(1)到O(2^n)把常见的复杂度按增长速度排个序从低到高大概是时间复杂度通俗解释典型例子O(1)常数时间与数据量无关数组按下标访问O(log n)对数时间增长极慢二分查找O(n)线性时间数据量翻倍时间也翻倍单层循环遍历O(n log n)线性对数时间常见于高效排序归并排序、堆排序O(n^2)平方时间数据量翻倍时间变四倍两层嵌套循环O(2^n)指数时间数据稍微一多就爆炸暴力递归求斐波那契这个顺序值得反复默写因为面试中很多题目考的就是“这段代码大概是什么复杂度”心里有这个谱就成功了一半。O(1)和O(logn)是大家最喜欢的复杂度。O(n)通常是可接受的。O(nlogn)基本是优秀排序算法的天花板。O(n^2)只在数据量小的时候能用。O(2^n)基本是反面教材除了数据规模极小的情况几乎不可接受。我私底下给这些复杂度起外号O(1)是“瞬间完成”O(logn)是“眨个眼”O(n)是“按部就班”O(nlogn)是“分而治之”O(n^2)是“有点吃力”O(2^n)是“直接放弃”。3.4 手动算几个实例循环嵌套与递归的复杂度理论讲多了容易飘来几个实打实的代码片段练手。实例1把一个数组倒序输出for i in range(n - 1, -1, -1): print(arr[i])单层循环执行n次时间复杂度O(n)。就这么简单。实例2打印一个n阶乘法表for i in range(1, n 1): for j in range(1, n 1): print(i * j)两层循环每层都是n次总次数n^2时间复杂度O(n^2)。如果只打印下三角内层循环范围改成range(1, i 1)总次数变成n(n1)/2去系数去低阶之后仍然是O(n^2)别被“看起来少了一半”迷惑量级没变。实例3递归求阶乘def factorial(n): if n 1: return 1 return n * factorial(n - 1)递归不是靠循环来算次数而是看“递归调用了多少次”。n的阶乘会调用n次所以时间复杂度O(n)。注意递归的空间复杂度比较特殊后面会专门说。实例4暴力递归斐波那契def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个函数的调用次数不是n次而是接近2^n。因为fib(n)会调用fib(n-1)和fib(n-2)每一个又继续分裂。画一下调用树第一层1个第二层2个第三层4个……简直是指数爆炸。所以暴力递归斐波那契的时间复杂度是O(2^n)n到40就明显卡顿n到50基本等不出来了。这就是为什么面试几乎必考“斐波那契别用暴力递归”用带备忘录的递归或者迭代可以把复杂度降到O(n)。实际工作中写代码不需要每次都是精确的复杂度分析但要有能力快速判断一段代码的量级尤其是那种隐藏着嵌套循环的代码。我见过一个数据清洗脚本里面有一个for循环每次循环内部都调用了一次简单查找外层数组1000万条记录内层查找又是个遍历结果脚本跑了几个小时没跑完。这就是典型的没做复杂度评估就上线的代价。4. 空间复杂度内存这东西也不能随便霍霍4.1 空间复杂度的定义和两个误区时间复杂度讨论的是时间增长趋势空间复杂度讨论的是“额外使用的内存空间”随输入规模增长的趋势。注意“额外”两个字输入数据本身占用的空间不算在内算的是算法执行过程中新开辟的存储空间比如临时变量、辅助数组、递归调用栈。空间复杂度也有两个常见的初学者误区。第一个误区是觉得空间复杂度不重要。在个人电脑上确实无所谓但嵌入式设备、服务端高并发场景、大数据处理框架里内存是比CPU更稀缺的资源。我在给某图像处理Demo调优时发现一个简单操作因为申请了跟原图等大的临时数组内存占用直接翻倍多张图片并发处理时直接内存不足。空间复杂度不是理论概念是实打实的生产事故来源。第二个误区是把空间复杂度和“代码长短”挂钩。有人觉得算法代码短就省内存代码长就更费内存这完全不对。空间复杂度看的是运行时分配的内存大小跟代码行数没关系。一个只有三行的递归函数如果递归深度很大也能吃掉大量栈空间一个一百行但只用几个变量的函数反而可能是O(1)。4.2 从代码看空间开销几个经典量级O(1)空间def sum_list(arr): total 0 for x in arr: total x return total这个函数只申请了一个total变量无论传入的数组有多大额外内存都不会增加空间复杂度O(1)。O(n)空间def double_list(arr): result [] for x in arr: result.append(x * 2) return result这个函数把输入数组的每个元素翻倍后存到一个新列表里新列表的大小跟输入数组一样大额外空间随n线性增长空间复杂度O(n)。O(n^2)空间def matrix(n): return [[0] * n for _ in range(n)]创建一个n乘n的二维数组总共n^2个元素空间复杂度O(n^2)。O(logn)空间二分查找的非递归版本是O(1)空间但递归版二分查找因为每次递归都会压栈递归深度logn空间复杂度就是O(logn)。递归的空间复杂度等于递归深度这是一个非常实用的结论。4.3 空间换时间的实战思路查重、缓存、双指针时间和空间往往不能兼得很多算法优化本质上是拿空间换时间。最经典的例子就是“数组去重”。如果你限制不能用额外数据结构只能用数组本身常规做法是两层循环每个元素跟后面所有元素比较把重复的标记掉。时间复杂度O(n^2)空间复杂度O(1)。数据量小还好数据量过万就开始痛苦。如果允许用一个哈希表做法变成遍历数组把每个元素塞进哈希表表格中已经存在的说明是重复。这个做法的时间复杂度降到O(n)代价是哈希表额外占用O(n)空间。我在某公司做数据清洗时经常处理百万级ID列表用前者完全没法跑用后者几秒钟出结果这就是典型的空间换时间。类似的还有缓存思想把已经算过的结果存起来避免重复计算。带备忘录的斐波那契本质就是空间换时间把递归里的海量重复计算用一张表消除。LeetCode上很多动态规划题目暴力递归O(2^n)加了dp数组之后变成O(n)或O(n^2)也是同一个道理。当然空间换时间不是无脑换要评估空间成本是否可接受。有时候可以用双指针技巧把空间复杂度压到O(1)。比如判断一个数组里是否有两个数加起来等于目标值用哈希表的做法空间复杂度O(n)如果把数组排序后用双指针从两端往中间移动空间复杂度降到O(1)代价是排序本身耗时。面试中如果能说出这几种方案的取舍会比背答案亮眼很多。5. 新手最容易踩的复杂度大坑问题排查与经验实录5.1 复杂度计算翻车现场三个真实教训翻车一看到嵌套循环就当成O(n^2)有些循环虽然是嵌套的但内层循环次数会提前结束。比如从一个已排序数组里找目标值外层遍历数组内层做二分查找总复杂度不是O(n^2)而是O(n logn)。计算复杂度不能只看代码形态要看循环的实际次数。我在一个内部工具里就写过这类代码第一版脑测复杂度是O(n^2)后来仔细一算是O(n logn)性能完全没问题差点白优化一场。翻车二把常数时间操作当成O(n)Python里访问列表元素、字典按键取值、直接赋值都是O(1)的常数操作。但有些初学者在循环里用list.index()找元素这个操作本身是O(n)放在循环里就变成O(n^2)了。这就是隐藏的复杂度。类似的情况还有在循环里用字符串拼接有些语言的字符串拼接会重新创建对象导致整体复杂度比想象的高很多。翻车三递归复杂度指数爆炸却没意识到递归函数看着简洁但它可能同时存在“多个子调用”复杂度会指数增长。经典的斐波那契暴力递归就是如此。我见过有人用递归去计算组合数n稍微大一点就卡死原因就是没有意识到递归调用的分裂效应。排查方法很简单画出递归调用树数一数节点数级别的增长规律。5.2 有穷性问题死循环是算法最大的敌人前面讲算法特性时提过有穷性但死循环的坑太常见了必须单独说。我整理一下最常见的死循环成因while循环的条件判断错误比如应该i n写成i n有时候不是死循环但会多算一次真正危险的是循环变量更新写错循环变量在循环体内被意外重置比如在某个分支里重新赋值为初始值递归的终止条件不完整导致某些输入永远不满足终止条件浮点数比较误判用x ! 1.0做循环条件计算机里的浮点数很难精确等于某个值排查死循环的经验是先看循环变量在循环体内部有没有被更新再看终止条件是否覆盖所有输入情况最后用小数据量跑一遍并打印循环变量。如果一个循环跑了预期迭代次数之外还没有结束基本可以断定有穷性被破坏了。在面试或者考试中有穷性相关的问题通常不会直接问“什么是死循环”而是给一段代码让你找bug。我在某次面试模拟中遇到过一道题给定一个链表的反转算法结果在链表存在环时陷入死循环。这就是有穷性的实际应用——算法设计时必须考虑输入数据的特殊性比如链路中是否存在环路。应对思路是给遍历增加一个“已访问节点”的记录超出记录就终止。5.3 复杂度估算速查表与排查工具箱为了方便快速判断我整理了一个速查表。实际分析代码的时候先定位最耗时的部分然后对照下表观察到的模式可能的时间复杂度典型场景单层循环循环变量i每次加1O(n)遍历数组、求总和、找最大值循环变量i每次乘以固定的数O(log n)二分查找、倍增遍历两层循环内外层都从0到nO(n^2)两两比较、冒泡排序一个循环调用另一个O(logn)操作O(n log n)遍历时做二分查找递归分成子问题每个子问题规模减半O(log n)或O(n log n)归并排序递归同时分两个子问题且无记忆化O(2^n)暴力斐波那契排查“代码为什么这么慢”的时候我习惯用“数据规模翻倍法”。取一组中等规模的数据跑一次记录耗时再把数据规模翻倍跑一次观察耗时增长。如果耗时基本不变说明接近O(1)如果耗时翻倍说明是O(n)如果耗时变成四倍大概率O(n^2)。这个方法虽然粗糙但能在几分钟内对一个未知代码段的复杂度有个直观判断比对着代码干瞪眼有效得多。另外推荐一个笨但有效的技巧在关键循环里加一个计数器记录循环实际执行次数跟理论复杂度对比。我调试某跨平台系统的排序模块时就靠这个技巧发现了一个“理论上O(n logn)、实际偶尔变成O(n^2)”的边界问题——因为某种特殊输入让划分极度不平衡。这类问题靠肉眼很难发现计数器是最朴实也最可靠的工具。5.4 学习和面试中怎么应用这些概念算法入门的知识点放到实际场景中怎么用这是不少人困惑的地方。对于学习者我不建议死记定义建议把每个概念都落到代码里验证。学时间复杂度就写两段实现相同功能的代码一个O(n^2)一个O(n)用不同规模的数据跑一遍亲眼看时间差距。学空间复杂度就多观察一下自己写的代码里有没有创建了新的大数组、深拷贝了数据。对于准备面试的人复杂度分析往往是手撕代码之后的“必问题”。面试官通常会问“这个解法的时间复杂度是多少空间复杂度呢能不能优化”这时候能说出“这里是O(n)时间O(1)空间因为只用了一个临时变量”之类的话比闷头写完代码不说理由要强得多。我见过不少代码写得好的人就是因为讲不清楚复杂度分析在面试中栽了跟头。面试中还有一类常见问题是对比不同算法。比如“数组查找和哈希表查找有什么区别”回答的框架就是数组按下标访问是O(1)按值查找是O(n)哈希表按值查找平均是O(1)但哈希冲突严重时退化到O(n)。这些对比的背后全是复杂度分析的基本功。写在后面的体会这篇笔记写到这我突然回想起自己初学时候的状态盯着“有穷性、确定性、可行性”几个词发懵觉得这些跟写代码有什么关系。等真正在项目里遇到死循环、遇到数据一多就卡死、遇到内存莫名其妙飙升才明白这些概念不是考试用的是保命用的。如果让我给刚入门的同学一个最可行的建议不要只背时间复杂度表一定要亲手把一段代码的执行次数算一遍再拿真实数据跑一遍。哪怕是最简单的“双层循环打印九九乘法表”手动推一遍执行次数再对比程序实际运行效果你对大O记号的直觉就建立起来了。理解了这几个基础概念后面学栈、队列、树、图的时候你才能在各种数据结构的操作复杂度对比中看到规律而不是被一堆表格淹没。下一期我打算写顺序表相关的笔记那是数据结构里第一个真正的“结构”到时候会用到这篇的复杂度分析方法。复习算法入门的内容时可以拿“数组按下标访问是O(1)”“线性查找是O(n)”“二分查找是O(logn)”这几个例子当锚点先把时间复杂度体系立住再来碰复杂结构会轻松很多。
