数据结构与算法 / 知识点

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

查找与排序

在有序且可随机访问的数据上,每轮缩小约一半搜索区间,时间复杂度为 O(log n);边界定义错误是实现中最常见的风险。

二分查找

需要在已排序且支持高效随机访问的数据中定位目标值时查这一项。二分查找每轮排除约一半候选区间,典型时间复杂度为 O(log n);判断能否使用时,先确认有序性,再检查区间边界和返回条件是否一致。

怎么判读

线索 含义 建议动作
数据已按比较规则排序 满足二分查找的核心前提 可继续检查访问方式和边界定义
数组、切片等可随机访问结构 读取中间位置通常为 O(1) 二分查找通常能保持 O(log n) 时间
每轮根据中点排除约一半区间 搜索范围指数级缩小 预计最多进行对数级比较
数据无序 无法根据一次比较安全排除半边 不应直接使用二分查找
链式结构需要逐节点走到中点 找中点本身可能不是 O(1) 不应只根据比较次数宣称整体为 O(log n)

复杂度范围

在长度为 n 的有序随机访问序列中,每轮将候选元素数量从 n 缩小到约 n/2。经过 k 轮后剩余规模约为 n/2^k,因此找到目标或确认不存在所需轮数为对数级,最坏时间复杂度为 O(log n)。

迭代实现通常只维护左右边界和中点,额外空间为 O(1)。如果使用递归实现,调用栈深度随搜索轮数增长,额外空间通常为 O(log n)。

边界检查

实现出错往往不是复杂度判断错误,而是区间约定前后不一致。闭区间 [left, right] 常配合 left <= right;左闭右开区间 [left, right) 常配合 left < right。更新边界时也必须遵循同一约定,否则可能漏掉端点、重复检查中点或出现死循环。

快速判断

看到“有序数组中查找目标值、边界位置、首个满足条件的位置”一类问题时,可以优先考虑二分思路。若输入无序且只查询一次,先排序再二分未必划算,因为排序通常还需要 O(n log n) 时间。

树与图

算法范式

算法选择

目录与阅读设置

记录一个想法

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

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

登录哪都通