数据结构与算法 / 知识点
数据结构与算法复杂度速查
复杂度等级
操作次数与输入规模基本无关,适合数组随机访问、哈希表均摊查找等场景;重点关注单次操作是否真的不随数据量增长。
O(1) 常数复杂度
看到某个操作被标为 时,先确认它执行的关键步骤是否不随输入规模 增长。查清这一点后,可以快速判断数组按下标访问、固定字段读取等操作是否属于常数复杂度,并避免把“执行很快”误当成 。
怎么判读
| 线索 | 含义 | 建议动作 |
|---|---|---|
| 无论 多大都只做固定次数操作 | 典型 | 可按常数复杂度估算 |
| 直接使用数组下标定位元素 | 地址计算不需要遍历元素 | 单次随机访问通常按 处理 |
| 哈希表一次键查找 | 在正常散列和负载控制下通常接近固定成本 | 明确写成平均或期望 ,不要省略条件 |
| 操作内部存在循环且循环次数随 增长 | 不是常数复杂度 | 根据循环规模重新判断复杂度 |
常见例子
数组按已知下标读取元素通常是 ,因为定位第几个元素不需要先访问前面的元素。读取对象的固定字段、交换两个变量、比较两个数,也通常属于这一类。
哈希表需要额外注明边界:在散列分布合理且装载因子受控时,查找、插入和删除通常按平均或期望 描述;发生严重碰撞时,最坏复杂度可能高于 。因此看到“哈希查找 ”时,应继续确认它说的是平均情况还是最坏情况。
容易误判的情况
描述的是增长趋势,不代表实际耗时一定更短。一个固定执行数千条指令的 操作,在小规模输入上完全可能比一个只执行几步的 操作更慢。
数组随机访问是 ,但在数组开头插入元素通常需要搬移后续元素,因此可能是 。同一种数据结构的不同操作不能共用一个复杂度结论。
适用范围
这里的 是渐进复杂度记号,关注输入规模增大时操作次数的增长阶,而不是 CPU 周期、缓存命中、磁盘访问或网络延迟等具体常数成本。速查时优先问一句:输入扩大十倍后,这个操作本身是否仍只需要固定数量的关键步骤? 如果答案是肯定的,才适合按 判断。
每轮通常把问题规模按固定比例缩小,典型于二分查找和平衡树查找;输入扩大时增长缓慢,常用于大规模有序数据。
O(log n) 对数复杂度
看到 时,重点检查算法是否每一轮都把剩余问题按固定比例缩小,例如减半。确认后,就能快速识别二分查找、平衡搜索树查找等典型操作,并判断某个看似有循环的过程为什么仍然只增长得很慢。
怎么判读
| 线索 | 含义 | 建议动作 |
|---|---|---|
| 每轮把候选范围减半 | 典型 | 统计最多需要多少次折半 |
| 每轮按固定比例缩小问题 | 比例不一定是 | 通常仍归为对数复杂度 |
| 在平衡搜索树中沿一条根到叶路径查找 | 树高通常为 | 先确认树确实维持平衡 |
| 每轮只减少一个元素 | 规模是线性缩小 | 通常应判断为 ,不是 |
最小判断方法
二分查找从 个候选元素开始,每轮只保留大约一半。进行 轮后,剩余规模约为 ;当候选范围缩小到常数量级时,轮数随 增长,因此时间复杂度记为 。
例如从约 1024 个元素中二分定位目标,最多只需要约 10 次范围缩小;即使扩大到约 100 万个元素,也只需要约 20 次。这种“输入增长很多,而循环轮数只增加少量”的特征,是识别对数复杂度最实用的线索。
前提与边界
二分查找的 有明确前提:搜索范围必须能依据比较结果排除固定比例的候选项。对普通数组而言,这通常意味着数据已经按对应规则有序,并且能够高效访问中间位置。
平衡二叉搜索树中的查找通常是 ,原因是树高受到约束。普通二叉搜索树如果退化成近似链表,查找最坏会变成 ,因此不能只看到“树查找”就直接写成 。
对数底数怎么看
在渐进复杂度中,、 等固定底数之间只相差常数倍,所以通常统一写作 。分析时真正重要的是“每轮按固定比例缩小”,而不是记住具体底数。
速查时可以直接检查:一次迭代后,剩余工作量是不是原来的固定比例? 如果是,且每轮工作本身为常数级,通常可以优先考虑 ;如果只是每次减去固定数量,则应重新按线性增长判断。
工作量通常与元素数量成正比,常见于完整扫描、统计和单次遍历;面对超大输入时,应优先确认是否还能减少不必要的数据访问。
O(n) 线性复杂度
当代码需要把输入元素基本完整地检查一次时,可用这一项快速判断规模增长带来的成本。确认主导操作次数与元素数量近似成正比后,就可以优先从减少扫描次数、提前结束或缩小输入范围入手优化。
值与含义
工程分析中,O(n) 通常表示输入规模从 n 增大到 2n 时,主导工作量也大致增加到原来的 2 倍;常数时间的初始化、收尾和固定次数判断不会改变复杂度等级。
| 典型形态 | 判读 | 首要动作 |
|---|---|---|
顺序访问全部 n 个元素一次 |
典型 O(n) |
检查是否必须读取全部元素 |
| 一次遍历中做固定数量操作 | 仍为 O(n) |
优化单次操作的常数开销 |
| 最坏情况扫描全部元素,但可能提前返回 | 最坏时间通常为 O(n) |
同时注明最好或平均情况是否不同 |
| 连续执行两个独立的线性遍历 | O(n)+O(n),合并后仍为 O(n) |
判断两次遍历能否合并 |
出现条件
常见线索是只有一层随输入规模增长的完整循环,或者递归过程总共只访问每个元素、节点或边固定次数。例如数组求和、寻找最大值、链表遍历以及一次性的过滤统计,都经常落在这一等级。
看到循环并不能直接判定为 O(n)。如果每次迭代内部还执行与 n 有关的查找、复制或嵌套遍历,就要把内部成本一起计算;反过来,循环每次把问题规模减半时通常不是线性复杂度。
判读线索
可以先数“随 n 增长的核心操作”而不是代码行数。若主导成本可近似写成 ,其中 a、b 不随 n 增长,则工程速查时可归入线性级别。
例如 n=1,000 时读取约 1,000 个元素,n=10,000 时读取约 10,000 个元素,是明显的线性增长信号。实际耗时不会严格增长 10 倍,因为缓存、分支预测、I/O 和运行时开销可能改变常数项。
建议动作
面对超大输入,先确认算法是否必须观察每个元素。若任务本身要求计算全部数据的精确聚合结果,至少读取一次通常无法避免,此时重点应转向减少重复扫描、降低每个元素的处理成本以及改善内存访问局部性。
如果目标只需要找到一个满足条件的元素,可以利用提前返回降低典型运行时间,但最坏情况仍可能扫描全部输入。若查询会被重复执行,则可以评估是否值得预先建立索引、哈希结构或其他辅助数据,以用额外空间和预处理换取后续查询速度。
常见于高效排序、分治和堆操作组合,通常能处理较大的输入规模;比较算法时应同时关注常数开销与额外空间需求。
O(n log n) 线性对数复杂度
当算法既要处理接近全部 n 个元素,又存在约 log n 层的分治、树高或重复调整过程时,可用这一项快速判断成本。确认属于这一等级后,应继续比较常数开销、额外空间和数据特征,而不是只凭复杂度符号选择实现。
值与含义
O(n log n) 的增长速度高于线性 O(n),但明显低于平方级 O(n²)。常见直觉是:每一层总共处理约 n 份工作,同时层数随问题规模按对数增长,因此总成本接近 。
| 典型形态 | 判读 | 首要动作 |
|---|---|---|
分成若干子问题,每层总工作量约为 n,层数约为 log n |
常见 O(n log n) |
检查分割是否保持足够均衡 |
对 n 个元素各执行一次 O(log n) 的树或堆操作 |
总计 O(n log n) |
检查单次操作的最坏复杂度 |
| 比较排序保持良好分割或树形归并 | 常见 O(n log n) |
同时比较稳定性与额外空间 |
循环 n 次,内部每次把搜索范围减半 |
通常为 O(n log n) |
确认内部操作确实是对数级 |
出现条件
归并排序的典型分析是约有 log n 层归并,每层处理全部 n 个元素,因此整体为 O(n log n)。堆排序则可以理解为对大量元素反复执行对数级堆调整,最终也形成这一数量级。
快速排序不能仅凭“分治”直接写成固定的 O(n log n):在分割较均衡时,其平均或典型成本常处于这一等级,但持续出现极不均衡分割时,最坏时间可以退化到 O(n²)。判读时必须区分平均、期望与最坏复杂度。
判读线索
最实用的检查方法是分别确认“每层做多少工作”和“共有多少层”。若递归树深度约为 log n,并且每层跨所有子问题合计处理约 n 个元素,就能快速得到 O(n log n)。
不要因为代码中出现两层循环就直接判断为 O(n²)。如果内层循环的总执行次数受分治层数、树高或不断减半的范围控制,真实成本可能是 O(n log n);反之,如果所谓分治长期无法缩小问题,也可能失去这一界限。
建议动作
在排序等必须进行大量比较的任务中,O(n log n) 通常已经属于可处理较大输入规模的常见等级。继续选型时应检查实现是否原地执行、是否稳定、最坏情况是否退化,以及额外内存分配是否会成为实际瓶颈。
例如两个算法都标为 O(n log n),其中一个可能拥有更好的缓存局部性,另一个可能需要额外的 O(n) 空间;在真实数据规模下,两者耗时和内存峰值仍可能明显不同。因此复杂度等级适合做第一轮筛选,不能替代基准测试和资源约束分析。
常由双重遍历或两两比较产生,输入扩大后成本快速上升;适合较小规模数据或需要完整检查所有元素对的场景。
O(n²) 平方复杂度
当代码需要对输入中的大量元素进行两两组合、比较或重复扫描时,可用本条快速判断是否接近平方复杂度,并决定是否需要减少重复工作。关键不是看到两层循环就直接判定,而是确认总执行次数是否随输入规模按平方级增长。
怎么判读
| 线索 | 含义 | 建议动作 |
|---|---|---|
两层循环都遍历约 n 个元素 |
操作次数约为 | 数据规模较大时检查是否能减少一层扫描 |
| 对所有无序元素对各处理一次 | 次数约为 ,仍属于 | 若业务确实要求检查所有元素对,通常难以单纯靠改写循环降阶 |
外层遍历 n 次,内层只执行固定次数 |
总次数与 n 成正比 |
不应误判为 |
| 内层范围随外层缩短 | 需要求和后再判断 | 若总次数仍约为平方量级,则记为 |
例如,两两比较 n 个元素时,共有 对。忽略常数和低阶项后,该数量随 n 的平方增长,因此渐进复杂度是 。
出现条件
典型来源包括朴素的两两比较、重复从头扫描数组,以及某些使用嵌套循环实现的排序或查重过程。判断时应关注循环边界和实际执行次数,而不是只数代码里出现了几层 for。
当 n 翻倍且主要工作量约变为原来的 4 倍时,也符合平方增长的直觉。这个观察只适合辅助判断,真实运行时间还会受到常数开销、缓存、语言实现和数据分布影响。
建议动作
如果平方级工作来自可以消除的重复查找,可检查哈希表、排序后二分、双指针、索引或预处理是否能换取更低的时间复杂度。若问题本身要求枚举所有元素对,则输出规模或问题定义可能已经决定了平方级下界,此时重点应转向减少常数开销和控制输入规模。
适用范围
这里的 表示输入规模趋大时的渐进增长上界,不直接等于某次运行耗时。具体分析应先明确 n 代表什么,并区分最坏、平均或摊还复杂度;不同算法实现和输入分布可能得到不同结论。
每增加一个输入元素都可能成倍增加搜索空间,常见于未剪枝的子集枚举和朴素状态搜索;通常需要剪枝、记忆化或改换模型。
O(2ⁿ) 指数复杂度
当搜索过程对每个输入元素都可能产生两个独立选择,或递归树在每一层近似翻倍时,可用本条判断是否出现 级增长。确认后应优先检查重复状态、无效分支和是否存在可复用的子问题,因为指数规模通常只适合较小的 n。
怎么判读
| 线索 | 含义 | 建议动作 |
|---|---|---|
| 每个元素都有“选或不选”两种独立选择 | 完整组合数为 | 只在必须枚举全部子集时接受该成本 |
递归每层产生约 2 个子调用,深度约为 n |
递归树节点数可能达到指数级 | 检查两个分支之间是否存在重复状态 |
| 相同参数组合被反复计算 | 指数增长可能来自重复子问题 | 考虑记忆化或动态规划 |
| 很多分支能够提前确定无解 | 搜索空间可以缩小 | 增加剪枝,并保证剪枝条件不会漏掉合法解 |
一个包含 n 个元素的集合共有 个子集,因此任何必须逐个访问全部子集的算法,仅枚举结果本身就需要指数级工作量。例如 n 从 20 增加到 30 时,候选子集数量会从约一百万增长到约十亿,输入只增加 10,搜索空间却扩大约 1024 倍。
出现条件
指数复杂度常见于朴素子集枚举、组合决策和没有缓存的递归状态搜索。并非所有递归都是指数级:只有当多个分支持续展开且大量节点都实际被访问时,才会形成这种增长。
同样,也不能因为代码存在“二选一”就立即写成 。如果分支很快终止、状态数量受到更小上界限制,或记忆化使每种状态只求解一次,最终复杂度可能明显低于指数级。
建议动作
先判断是否真的需要枚举所有 个结果。若只需要最优值、可行性或计数,检查问题是否具有重复子问题和可压缩状态;具备这些条件时,记忆化或动态规划可能把大量重复搜索合并。若搜索仍不可避免,可根据约束使用剪枝、分支顺序优化、折半搜索或问题特定的状态压缩方法。
适用范围
描述的是随输入规模增加的渐进上界,不表示每个指数算法都会恰好访问 个状态。复杂度还取决于状态定义、剪枝效果、缓存策略以及分析的是最坏情况还是实际输入;具体实现应按真实递归树或可达状态数重新核对。
常见于枚举全部排列等问题,输入规模稍大就难以承受;判断代码时应优先寻找状态压缩、剪枝、动态规划或组合数学等替代方法。
O(n!) 阶乘复杂度
看到“枚举所有排列”“依次选择尚未使用的元素”这类代码时,应检查是否产生约 个候选状态。确认是阶乘复杂度后,首要动作不是微调常数,而是判断能否避免完整排列枚举。
怎么判读
| 线索 | 含义 | 建议动作 |
|---|---|---|
| 每一层从所有未使用元素中继续选择 | 搜索树分支数依次约为 | 检查是否实际遍历全部排列 |
| 叶子对应一种完整排列 | 候选数量可达到 | 评估是否只需要最优值、计数或部分候选 |
| 输入规模稍增,运行时间急剧上升 | 阶乘增长很快 | 优先寻找剪枝、动态规划或组合数学替代 |
增长规模
典型的全排列枚举会访问数量级为 的完整排列。即使每个排列上的额外工作很少,候选数量本身也会迅速成为主要成本。
| 5 | 120 |
| 8 | 40320 |
| 10 | 3628800 |
| 12 | 479001600 |
这些数值只反映候选排列数量;若每个候选还需要 检查,总成本可能进一步变为 。
出现条件
阶乘复杂度最常见于显式生成全部排列,或回溯过程中没有有效约束、最终仍访问几乎所有排列。若剪枝能大量排除分支,实际运行量可能远小于 ,但不能仅凭测试数据就把最坏复杂度改写成更低等级。
建议动作
如果任务只要求最优值或可行性,先检查状态压缩动态规划能否把“已选择哪些元素”表示为子集状态;如果存在强约束,使用剪枝减少无效分支;如果只要求排列数量或某类组合计数,优先寻找组合数学公式,而不是实际生成全部结果。
适用范围:这里描述的是算法分析中的渐进时间复杂度。具体可承受的 还取决于每个状态的工作量、实现语言、硬件和剪枝效果。
单次操作偶尔可能较慢,但连续执行后的平均成本保持常数级;典型例子是动态数组扩容后的追加,不应把最坏单次成本当作均摊复杂度。
摊销 O(1)
看到某个操作“多数时候很快、偶尔一次很贵”时,应检查一串连续操作的总成本,而不是只看最坏单次成本。若执行 次操作的总成本为 ,则每次操作的摊销成本为 。
怎么判读
| 线索 | 含义 | 建议动作 |
|---|---|---|
| 大多数操作直接完成 | 常见单次成本是常数级 | 继续检查昂贵操作出现频率 |
| 偶尔触发扩容、重建或批量搬移 | 某一次可能达到 | 不要直接把它当成每次操作的成本 |
| 昂贵操作之间的间隔随规模增长 | 高成本被许多低成本操作分摊 | 计算连续操作的总成本 |
典型例子
动态数组按固定倍数扩容时,普通追加只需写入一个元素;容量耗尽后的一次追加需要申请更大的存储空间并搬移已有元素。该次操作可能是 ,但扩容不会在每一次追加时发生。
若容量按 1、2、4、8 等规模增长,连续追加 个元素时,搬移元素的总次数形成几何级数,其总量仍为 。因此整段追加的总成本是 ,单次追加的摊销复杂度为 。
与其他复杂度区分
| 表述 | 回答的问题 |
|---|---|
| 最坏单次 | 某一次操作最多可能花多少成本 |
| 通常单次 | 常见情况下某一次操作多快 |
| 摊销 | 一串操作的总成本平均到每次后是多少 |
摊销分析不是概率分析,也不表示某次操作“平均随机地”需要常数时间。它描述的是一个确定的操作序列中,偶发高成本如何被其他低成本操作分担。
使用边界
只有在昂贵操作的频率和总代价能够被严格约束时,才能声称摊销 。如果动态数组每次只增加一个容量,连续追加会反复搬移越来越多的元素,总成本可达到 ,此时不能得到摊销 。
同一算法在不同输入分布下可能有不同运行成本;面试与工程评估通常优先确认最坏界,同时说明平均情况成立所依赖的输入假设。
最坏、平均与最好情况
当同一算法会因输入排列、取值或随机选择产生不同成本时,先确认讨论的是最坏、平均还是最好情况。工程评估通常先看最坏情况控制风险;引用平均复杂度时,还要说明采用了什么输入分布或随机化假设。
怎么判读
| 分析维度 | 含义 | 适合回答的问题 | 建议动作 |
|---|---|---|---|
| 最坏情况 | 在规模为 n 的允许输入中取成本最大值 |
单次请求最多可能消耗多少时间或资源 | 优先用于延迟上界、容量和风险评估 |
| 平均情况 | 按指定输入分布或算法随机性计算期望成本 | 常见输入下通常需要多少工作 | 明确概率模型后再引用结果 |
| 最好情况 | 在规模为 n 的允许输入中取成本最小值 |
最有利输入能多快结束 | 用于理解提前结束条件,不代替常规性能判断 |
平均情况的前提
“平均”不是把最好和最坏简单相加再除以二。它需要一个概率模型,例如假定输入排列等概率出现,或分析随机化算法自身产生的随机选择。输入分布改变后,平均复杂度也可能改变。
如果资料只写“平均 O(n log n)”却没有交代平均针对什么随机变量,应继续确认:随机性来自输入、算法内部,还是实际采样数据。
常见判读线索
看到“无论输入怎样都不超过”时,通常是在讨论最坏情况上界;看到“期望”“随机选择”“均匀分布”等词时,应检查平均情况的概率假设;看到“已经有序时立即结束”之类条件,则是在描述某类最好情况。
使用顺序
面试或设计评审中,可以先给出最坏情况,说明它是否会影响延迟或资源上限;如果平均情况明显更有代表性,再补充其成立条件。最好情况主要用于解释优化路径或提前终止,不应单独作为算法性能结论。
这些定义适用于常见的时间和空间成本分析;具体平均结果依赖算法、输入模型和随机化方式,应以对应算法的证明或可靠资料为准。
统计算法随输入规模增长而额外占用的存储,通常区分输入本身与辅助空间;递归深度、哈希表、缓存和临时数组都应计入分析。
空间复杂度怎么算
计算空间复杂度时,先约定统计总空间还是辅助空间,再找出所有会随输入规模 n 增长的存储。算法题通常更关注辅助空间,也就是除输入数据本身之外,算法额外需要的内存。
怎么判读
| 存储来源 | 是否通常计入辅助空间 | 判读方法 | 常见结果 |
|---|---|---|---|
| 固定数量的局部变量 | 是 | 数量不随 n 增长 |
O(1) |
| 长度随输入增长的临时数组 | 是 | 看数组最大同时存活长度 | 常见为 O(n) |
| 哈希表、集合、队列、栈 | 是 | 看最多同时保存多少元素 | 按峰值元素数计算 |
| 递归调用栈 | 是 | 看最大递归深度,而不是总调用次数 | 深度为 d 时通常为 O(d) |
| 输入数组或输入对象 | 视口径而定 | 区分总空间与辅助空间 | 分析时应明确是否排除 |
| 输出结果 | 视题目口径而定 | 判断输出是否是问题本身要求的必需空间 | 明确说明是否计入 |
计算顺序
先列出执行期间可能存在的存储,再确定每一项的最大同时占用量。顺序执行且生命周期不重叠的两个 O(n) 缓冲区,峰值仍是 O(n),不是 O(2n) 后得到新的复杂度等级;若一个 O(n) 数组和一个 O(n²) 表同时存在,则主导项为 O(n²)。
空间复杂度关注峰值占用,而不是程序累计申请过多少内存。临时对象创建后已经释放,通常不会与后续对象的空间简单相加。
递归最容易漏算
递归函数即使没有显式创建数组,也会为每层调用保存返回地址、参数和局部状态,因此要统计最大调用深度。例如处理 n 个元素时若递归深度线性增长,辅助空间通常为 O(n);若递归深度保持为对数级,则调用栈通常为 O(log n)。
尾递归也不能自动按 O(1) 处理。是否复用栈帧取决于具体语言、编译器和运行时是否保证尾调用优化,分析时应以实际执行模型为准。
原地算法怎么判断
“原地”通常表示只使用常数级或非常有限的额外存储,但不同教材和算法定义可能存在口径差异。判断时不要只看函数是否修改了输入,还要检查递归栈、隐藏缓冲区以及库函数内部是否额外分配与 n 相关的空间。
空间复杂度最终应描述最大同时占用量随输入规模的增长趋势;对运行库、垃圾回收器或容器的隐藏开销没有可靠信息时,不要自行假设其具体常数,只分析能够确定的渐近规模。
数据结构操作
已知下标时可直接计算元素地址并访问,时间复杂度为 O(1);适合频繁按位置读取,但中间插入或删除通常需要移动后续元素。
数组随机访问
判断“按下标读取数组元素”的复杂度时查这一项:只要下标已知且有效,典型数组模型可以直接定位目标元素,因此单次访问记为 O(1)。这个结论描述的是按位置读取,不等于查找某个未知值也是常数时间。
怎么判读
| 场景 | 复杂度或结果 | 建议动作 |
|---|---|---|
| 已知合法下标并读取元素 | O(1) |
可直接按随机访问处理 |
| 已知合法下标并覆盖元素 | 通常为 O(1) |
适合频繁按位置更新 |
| 不知道下标,只知道目标值 | 通常需遍历,最坏 O(n) |
不要误写成随机访问 O(1) |
| 在中间插入或删除元素 | 通常为 O(n) |
需要考虑后续元素移动成本 |
| 下标越界 | 不属于复杂度优势 | 按语言或容器规则处理错误或边界值 |
成立条件
典型复杂度分析把数组视为连续、等宽元素组成的顺序结构。已知下标 i 后,可以由首地址、元素宽度和 i 直接确定目标位置,不需要从第一个元素逐个走到第 i 个元素,因此访问时间不随数组长度 n 增长。
这里的 O(1) 是渐进复杂度结论,不表示访问耗时绝对相同。缓存命中、元素大小、边界检查以及具体语言运行时都会影响常数开销,但不会改变典型数组随机访问的复杂度分类。
容易混淆的情况
数组的“随机访问”与“搜索”是两个操作。表达式类似 a[i] 时,位置已经给定;若问题是“数组中是否存在值 x”,在没有额外索引或排序条件时通常仍要逐项检查。
链表也能表示有序元素集合,但普通链表无法根据整数下标直接计算节点位置,访问第 i 个节点通常需要沿指针前进,因此为 O(n)。这正是数组适合频繁按位置读取的重要原因。
适用范围
该结论适用于算法分析中的普通数组以及提供典型数组语义的顺序容器。某些语言中名为“数组”的高级对象可能采用特殊存储策略,实际常数成本由实现决定;进行面试、算法题或数据结构比较时,若题目没有另行说明,通常按标准随机访问数组模型记为 O(1)。
容量足够时追加元素只需写入尾部,通常为均摊 O(1);发生扩容时单次可能达到 O(n),因此应区分均摊与最坏情况。
数组尾部追加
判断动态数组连续执行尾部追加时的复杂度查这一项:容量足够时单次追加是 O(1),扩容时某一次可能达到 O(n);把一长串追加操作的扩容成本平均分摊后,通常记为均摊 O(1)。
怎么判读
| 场景 | 复杂度 | 建议动作 |
|---|---|---|
| 当前容量仍有空位 | O(1) |
直接写入尾部并更新长度 |
| 本次追加触发扩容 | 通常为 O(n) |
需要申请更大空间并搬移已有元素 |
| 连续执行大量尾部追加 | 通常均摊 O(1) |
用均摊复杂度描述整体追加成本 |
| 每次都要求严格的单次上界 | 最坏可为 O(n) |
不要把均摊 O(1) 当作最坏 O(1) |
| 已知最终规模较大 | 取决于容器能力 | 可预留容量以减少扩容次数 |
为什么是均摊 O(1)
动态数组通常维护“已使用长度”和“已分配容量”。容量未满时,新元素只需写到当前末尾,所以成本与元素总数无关。容量耗尽后,容器需要申请更大的连续存储区域,并复制或移动已有的 n 个元素,这一次追加因此可能花费 O(n)。
关键在于扩容不会在每次追加时发生。常见实现按一定增长比例扩大容量,使昂贵的搬移操作间隔越来越长。于是把若干次扩容的总成本分摊到整段追加序列上,每次追加的平均渐进成本仍可控制在常数级,因此称为均摊 O(1)。
容易混淆的情况
“均摊 O(1)”不表示任意一次追加都保证常数时间。如果系统对单次延迟非常敏感,例如实时处理路径,那么偶发的扩容搬移仍可能造成明显停顿,此时需要关注最坏情况或提前预留容量。
尾部追加也不同于数组中间插入。中间插入即使容量足够,通常仍要移动插入点之后的元素,所以最坏为 O(n);尾部追加没有这段搬移,只在扩容时承担整体迁移成本。
适用范围
这一结论主要针对采用增长容量策略的动态数组,例如常见语言标准库中的可变长顺序容器。具体扩容比例、是否复制或移动元素以及预留容量接口由实现决定,因此不要把某一种增长倍数当成通用标准。算法题或通用复杂度速查中,未特别说明实现时可将动态数组尾部追加标为均摊 O(1)、单次最坏 O(n)。
插入位置之后的元素通常需要整体后移,时间复杂度为 O(n);频繁在中间修改时应考虑链表或其他更适合更新模式的结构。
数组中间插入
评估数组、动态数组或顺序表在非末尾位置插入元素的成本时查这一项。关键结论是:即使已经知道插入下标,插入点之后的元素通常仍要整体后移,因此最坏和平均意义下通常按 O(n) 判断。
怎么判读
| 情况 | 主要成本 | 复杂度判断 |
|---|---|---|
| 在开头插入 | 原有元素几乎全部后移 | O(n) |
| 在中间插入 | 插入点之后的元素后移 | O(n) |
| 在末尾且容量充足 | 不需要搬移已有元素 | 通常 O(1) |
| 动态数组末尾触发扩容 | 分配更大空间并复制元素 | 单次可能 O(n) |
若数组长度为 n,在下标 k 处插入时,通常需要移动约 n-k 个已有元素。即使寻找 k 本身是 O(1),元素搬移仍决定了中间插入的整体复杂度。
出现条件
这个结论适用于需要保持元素连续存储并维持原有顺序的数组类结构,例如常见动态数组和顺序表。若实现允许覆盖元素、使用空洞、延迟整理,或根本不要求保持顺序,实际操作模型可能不同,不能直接套用这一结论。
动态数组还要区分“元素搬移”和“容量扩张”。中间插入通常本来就需要搬移元素;如果同时容量不足,还可能额外发生重新分配与复制,但渐进复杂度仍通常记作 O(n)。
选择结构时怎么看
连续数组适合大量按下标读取、顺序扫描,以及主要发生在尾部的追加。如果工作负载包含大量中间插入和删除,应进一步比较链表、树结构、分块结构或业务层批量重建方案,而不是只看单次读取性能。
适用范围
这里的 O(n) 描述的是保持顺序的典型连续数组结构,不代表所有名为“数组”的容器实现都具有完全相同的常数成本。具体语言运行库可能采用不同扩容策略,但中间插入需要移动线性数量元素这一判读原则通常不变。
链表缺少连续地址,按下标访问需要从头或尾逐节点移动,通常为 O(n);它适合顺序遍历,不适合大量随机位置读取。
链表按位置访问
判断链表能否像数组一样高效执行“读取第 k 个元素”时查这一项。普通链表没有可直接计算目标节点地址的连续下标映射,必须沿链接逐节点移动,因此按位置访问通常记作 O(n)。
怎么判读
| 操作条件 | 访问方式 | 复杂度判断 |
|---|---|---|
| 单链表访问第 k 个节点 | 从头节点依次前进 | O(n) |
| 双链表访问第 k 个节点 | 可从头或尾选择较近方向 | O(n) |
| 已持有目标节点引用 | 直接读取该节点 | O(1) |
| 顺序遍历下一个节点 | 沿当前节点的链接前进一次 | O(1) 每步 |
“按位置访问”和“已知节点访问”必须分开判断。链表慢的是从下标寻找节点的过程;一旦已经取得目标节点引用,读取节点内容或访问相邻链接通常不需要再次线性搜索。
为什么仍是 O(n)
对于长度为 n 的单链表,访问靠后的节点可能需要经过接近 n 个链接。双链表虽然可以根据位置从头部或尾部开始,减少实际经过的节点数,但最坏情况下移动步数仍与 n 成比例,因此渐进复杂度仍为 O(n)。
这也是链表与数组的重要边界:数组通常可以根据基地址和下标直接定位元素,而链表节点在内存中不要求连续,位置 k 本身不足以直接得到第 k 个节点的地址。
使用时的判读线索
如果代码频繁出现“根据整数下标取得链表元素”,应注意每次访问都可能重新遍历链表。把这种访问放进另一个线性循环中,还可能把整体成本扩大到 O(n²)。若任务本质上需要大量随机位置读取,数组或其他支持高效索引的数据结构通常更匹配。
如果处理过程本来就是从头到尾顺序扫描,则保存当前节点并沿链接继续前进即可,不需要为每个位置重新从头查找。
适用范围
这里指普通单链表和双链表。带额外索引、跳表层级、树形索引或其他加速结构的容器可能具有不同的按位置访问成本,不能仅凭名称中含有“链表”就套用 O(n)。
已经持有目标节点及必要前驱指针时,只需修改有限个链接即可完成插入;真正的成本可能来自寻找位置,因此需区分定位与修改两步。
链表已知节点插入
判断链表插入复杂度时,先确认插入位置是否已经定位。若已经持有完成修改所需的节点引用或前驱指针,插入本身只改动固定数量的链接,因此为 O(1);不要把寻找位置的成本混入这一步。
怎么判读
| 条件 | 插入本身 | 应如何理解 |
|---|---|---|
| 已持有单链表插入位置的前驱节点 | O(1) |
修改前驱的 next 等有限个链接即可 |
| 双向链表已持有目标位置节点 | O(1) |
可通过已有前后链接完成局部修改 |
| 只有索引或待查找的值 | 插入修改仍可为 O(1),但定位通常不是 |
先单独计算找到目标位置的成本 |
出现条件
O(1) 描述的是已经定位后的结构修改。以常见单链表为例,在某节点之后插入新节点,只需要让新节点连接原后继,再让当前节点连接新节点,操作次数不会随链表长度增长。
如果任务描述是“在第 k 个位置插入”或“在值为 x 的节点前插入”,而调用方没有现成的位置引用,就通常需要先从链表头遍历。此时总耗时应写成“定位成本 + O(1) 修改成本”,常见线性定位会使整体达到 O(n)。
快速区分
遇到复杂度题时先问两个问题:是否已经拿到目标节点,以及单链表场景下是否已经拿到必要的前驱节点。仅知道目标节点并不总能在单链表中完成“在其前面插入”,因为还可能需要寻找前驱。
散列函数把键映射到桶中,在负载因子与冲突控制正常时,查找、插入和删除通常为平均 O(1);最坏情况可能退化。
哈希表平均查找
查复杂度时,平均 O(1) 表示在散列分布、负载因子和冲突处理处于正常范围时,可以通过键快速定位到很小的候选范围;它不是所有输入下都保证常数时间。
怎么判读
| 线索 | 含义 | 建议判断 |
|---|---|---|
| 散列分布较均匀 | 键被分散到不同桶 | 查找通常按平均 O(1) 处理 |
| 负载因子受控 | 单个桶不会持续聚集过多元素 | 平均查找成本保持较低 |
| 大量键发生冲突 | 多个键落入相同桶或探测序列 | 查找需要检查更多候选项 |
| 出现极端冲突分布 | 候选范围随元素数增长 | 不能再把最坏情况视为 O(1) |
平均复杂度成立条件
哈希表先对键计算散列值,再根据结果定位桶或探测起点。只要散列函数能让实际键较均匀地分布,并且实现通过扩容等策略控制装载程度,每次操作通常只需检查常数级数量的候选位置,因此查找、插入和删除常按平均 O(1) 记录。
这里的“平均”依赖具体实现和输入分布。开放寻址、链地址法以及不同语言运行库可能采用不同的冲突控制和退化保护策略,因此不能把某个实现的最坏情况机制推广为所有哈希表的统一保证。
什么时候不能直接写 O(1)
如果题目明确要求最坏时间复杂度,应继续检查冲突处理方式。严重冲突可能让一次操作检查多个甚至大量元素,经典分析中的最坏情况可达到 O(n);部分具体实现可能采用额外结构缓解退化,但应以该实现或题目条件为准。
栈只在一端进行插入和删除,标准数组栈或链式栈的入栈、出栈通常为 O(1);适合括号匹配、DFS 和撤销操作。
栈入栈与出栈
判断栈操作复杂度时,先确认元素是否始终只在栈顶插入和删除。数组栈、链式栈在正常实现下,入栈和出栈都可按 判断;动态数组偶发扩容是需要单独留意的边界。
复杂度对照
| 操作或实现 | 时间复杂度 | 判读与动作 |
|---|---|---|
| 数组栈在尾部入栈 | 通常 | 直接在末尾写入元素并移动栈顶位置 |
| 数组栈从尾部出栈 | 直接读取并移除末尾元素,不搬移其余元素 | |
| 链式栈在头部入栈 | 新节点连接原栈顶,再更新栈顶指针 | |
| 链式栈从头部出栈 | 读取栈顶节点,再把栈顶指针移向下一节点 | |
| 动态数组扩容时入栈 | 单次可能 | 扩容需要复制已有元素;连续操作通常按摊还 分析 |
出现条件
的关键不是“使用了栈”这个名称,而是实现只修改栈顶附近的固定数量状态。数组实现应从尾部增删,链表实现通常从头部增删;如果每次操作都需要移动大量已有元素,就不再满足这一条件。
动态数组容量不足时可能申请更大的存储区域并复制已有元素,因此某一次入栈可能达到 。在常见按倍数扩容的实现中,这类复制不会每次发生,所以大量连续入栈通常记作摊还 。
判读线索
看到括号匹配、DFS、表达式求值、撤销记录等后进先出场景,可以优先检查是否只存在栈顶的 push 和 pop。若题目要求分析最坏单次操作,则需要确认动态数组是否可能扩容;若分析一系列操作的平均代价,则通常关注摊还复杂度。
速查结论
标准链式栈的入栈、出栈都是 ;以数组尾部作为栈顶的数组栈,出栈通常为 ,入栈通常按摊还 计算。具体容器是否自动缩容、扩容策略如何,应以对应语言或库的实现说明为准。
使用头尾指针管理时,队列入队和出队通常都是 O(1);适合 BFS、任务排队和流式处理,避免用数组频繁整体搬移元素。
队列入队与出队
判断队列操作复杂度时,重点看实现是否分别维护队头和队尾位置。循环数组、双端队列或带头尾指针的链式队列通常能让入队和出队保持 ;直接删除普通数组首元素并搬移剩余数据则会退化为 。
复杂度对照
| 操作或实现 | 时间复杂度 | 判读与动作 |
|---|---|---|
| 循环数组从队尾入队 | 通常 | 写入尾部位置并更新尾指针 |
| 循环数组从队头出队 | 读取头部位置并更新头指针,不搬移其余元素 | |
| 链式队列从尾部入队 | 通过尾指针连接新节点并更新队尾 | |
| 链式队列从头部出队 | 删除队头节点并更新头指针 | |
| 普通数组删除首元素并整体左移 | 需要搬移后续元素,应改用头索引、循环数组或合适的队列容器 | |
| 动态数组扩容时入队 | 单次可能 | 扩容复制元素;采用常见增长策略时通常按摊还 分析 |
出现条件
队列的先进先出语义本身并不能保证 。要达到常数时间,入队必须能直接定位队尾,出队也必须能直接定位队头,并且操作过程中不能随着队列长度增加而搬移全部已有元素。
循环数组通过头、尾索引复用已经释放的槽位,因此出队后不需要把后续元素整体向前移动。链式队列则通常同时保存头指针和尾指针,使两端操作都只修改固定数量的指针。
判读线索
在 BFS、任务调度、生产者消费者缓冲区和流式处理场景中,如果复杂度分析写为每次入队、出队 ,应确认底层使用的是循环队列、双端队列或带头尾指针的链式结构。若实现只是普通数组并在每次出队时删除第一个元素,需要检查该语言或容器是否会移动后续元素。
速查结论
维护队头和队尾位置时,标准队列的入队、出队通常都是 ;动态数组实现可能因扩容出现单次 ,但常见增长策略下通常按摊还 计算。具体数组删除、扩容和缩容行为应以所用语言或容器实现为准。
二叉堆查看最小或最大元素通常为 O(1),删除堆顶并恢复堆序通常为 O(log n);常用于优先队列与 Top K 问题。
堆顶查看与删除
需要判断优先队列取最高优先级元素的代价时,先区分“只查看堆顶”和“删除堆顶”。标准数组二叉堆中,前者通常是 O(1),后者需要恢复堆序,通常是 O(log n)。
值与含义
| 操作 | 典型复杂度 | 原因 | 常见动作 |
|---|---|---|---|
| 查看堆顶 | O(1) | 最小堆或最大堆的目标元素固定在根节点 | 直接读取根节点 |
| 删除堆顶 | O(log n) | 删除后通常把末尾元素移到根,再沿树高向下调整 | 执行下沉或等价的恢复堆序操作 |
| 插入元素 | O(log n) | 新元素加入末尾后可能沿父节点方向上浮 | 执行上浮 |
这里的 n 是操作发生前后同量级的堆中元素数量。二叉堆高度为 O(log n),因此上浮或下沉最多经过与树高同量级的节点。
出现条件
这个结论适用于常见的数组实现二叉最小堆或最大堆。仅读取根节点时不修改结构,所以是常数时间;删除根节点后若仍要求保持堆序,就必须完成重新调整。
优先队列、任务调度、Dijkstra 中的候选节点管理,以及维护固定容量 Top K 集合时,通常都需要区分这两种操作。如果只是重复查看当前最优元素,不应把它误算成每次 O(log n)。
快速确认
Python 标准库 heapq 提供最小堆,可以直接观察查看堆顶与删除堆顶的行为。
import heapq
heap = [5, 1, 8, 3]
heapq.heapify(heap)
print(heap[0])
print(heapq.heappop(heap))
print(heap[0])预期输出:
1
1
3heap[0] 只是读取根节点;heappop 删除原堆顶并恢复堆序。内部数组的其余排列不应作为复杂度判断依据。
判读与动作
看到“peek、top、minimum、maximum”一类只读操作时,优先判断实现是否直接保存目标根节点;标准二叉堆通常按 O(1) 处理。看到“pop、extract-min、extract-max”时,只要删除后还需维持堆性质,通常按 O(log n) 处理。
适用范围
这里讨论的是标准二叉堆的单次操作复杂度,不代表所有称为“优先队列”的实现都相同。斐波那契堆、二项堆、配对堆或带额外索引的数据结构具有不同复杂度边界;具体实现应以其数据结构定义和库文档为准。
AVL、红黑树等通过维护树高,使查找、插入和删除保持 O(log n);适合既要有序遍历又需要动态更新的数据集合。
平衡搜索树查找
需要判断动态有序集合的查找代价时,如果底层是 AVL、红黑树等保持高度受控的平衡搜索树,查找通常按 O(log n) 计算;插入和删除也会通过旋转或重新着色等机制维持同一数量级的高度上界。
值与含义
| 操作 | 典型复杂度 | 判读依据 | 建议动作 |
|---|---|---|---|
| 按键查找 | O(log n) | 每次比较后进入一个子树,路径长度受树高约束 | 沿搜索路径继续比较 |
| 插入 | O(log n) | 先定位位置,再执行有限范围的平衡修复 | 插入后维护平衡条件 |
| 删除 | O(log n) | 定位节点并处理替换节点后还可能需要重新平衡 | 删除后恢复平衡条件 |
| 有序遍历全部元素 | O(n) | 每个节点需要访问一次 | 使用中序遍历或迭代器 |
关键不是“二叉搜索树”这个名称本身,而是树高是否被平衡规则限制。普通二叉搜索树在极端输入下可能退化为链表,此时单次查找会达到 O(n)。
出现条件
AVL 树通过更严格的高度平衡约束控制树高;红黑树允许更宽松的局部不平衡,但同样保证树高为 O(log n)。因此二者都适合频繁查找、插入和删除,同时还需要按键排序、范围查询或前驱后继操作的场景。
如果题目只写“BST”而没有说明自平衡机制,就不能直接把最坏情况写成 O(log n)。只有明确是平衡搜索树,或实现文档给出了对数级保证,才能据此判断。
快速确认
Java 的 TreeMap 是基于红黑树的有序映射,可用下面的完整示例观察查找、删除和有序键行为。
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(20, "twenty");
map.put(10, "ten");
map.put(30, "thirty");
System.out.println(map.get(20));
map.remove(10);
System.out.println(map.firstKey());
}
}预期输出:
twenty
20示例验证的是接口行为;O(log n) 的复杂度依据来自平衡树对高度的约束,而不是这几次输出本身。
判读与动作
看到 AVL、Red-Black Tree、TreeMap 或其他明确声明为平衡搜索树的实现时,单次按键查找通常按 O(log n) 判断。若需求同时包含动态更新和有序遍历,这类结构往往比无序哈希结构提供更多顺序能力。
适用范围
上述复杂度描述针对维护平衡约束的搜索树。不同实现对重复键、比较器、并发访问和节点增强信息的处理可能不同;判断具体库时,应以其公开的数据结构说明和复杂度保证为准。