数据结构与算法 / 知识点

数据结构与算法复杂度速查

复杂度等级

操作次数与输入规模基本无关,适合数组随机访问、哈希表均摊查找等场景;重点关注单次操作是否真的不随数据量增长。

O(1) 常数复杂度

看到某个操作被标为 O(1)O(1) 时,先确认它执行的关键步骤是否不随输入规模 nn 增长。查清这一点后,可以快速判断数组按下标访问、固定字段读取等操作是否属于常数复杂度,并避免把“执行很快”误当成 O(1)O(1)。

怎么判读

线索 含义 建议动作
无论 nn 多大都只做固定次数操作 典型 O(1)O(1) 可按常数复杂度估算
直接使用数组下标定位元素 地址计算不需要遍历元素 单次随机访问通常按 O(1)O(1) 处理
哈希表一次键查找 在正常散列和负载控制下通常接近固定成本 明确写成平均或期望 O(1)O(1),不要省略条件
操作内部存在循环且循环次数随 nn 增长 不是常数复杂度 根据循环规模重新判断复杂度

常见例子

数组按已知下标读取元素通常是 O(1)O(1),因为定位第几个元素不需要先访问前面的元素。读取对象的固定字段、交换两个变量、比较两个数,也通常属于这一类。

哈希表需要额外注明边界:在散列分布合理且装载因子受控时,查找、插入和删除通常按平均或期望 O(1)O(1) 描述;发生严重碰撞时,最坏复杂度可能高于 O(1)O(1)。因此看到“哈希查找 O(1)O(1)”时,应继续确认它说的是平均情况还是最坏情况。

容易误判的情况

O(1)O(1) 描述的是增长趋势,不代表实际耗时一定更短。一个固定执行数千条指令的 O(1)O(1) 操作,在小规模输入上完全可能比一个只执行几步的 O(log⁡n)O(\log n) 操作更慢。

数组随机访问是 O(1)O(1),但在数组开头插入元素通常需要搬移后续元素,因此可能是 O(n)O(n)。同一种数据结构的不同操作不能共用一个复杂度结论。

适用范围

这里的 O(1)O(1) 是渐进复杂度记号,关注输入规模增大时操作次数的增长阶,而不是 CPU 周期、缓存命中、磁盘访问或网络延迟等具体常数成本。速查时优先问一句:输入扩大十倍后,这个操作本身是否仍只需要固定数量的关键步骤? 如果答案是肯定的,才适合按 O(1)O(1) 判断。

数据结构操作

目录与阅读设置

记录一个想法

数据结构与算法复杂度速查

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通