时间复杂度
描述算法执行时间随输入规模增长的渐近趋势，是评估算法效率的核心指标之一，常用大O表示法。
核心定义
- 时间复杂度：算法执行时间随输入规模 $n$ 增长的渐近上界，记为 $O(f(n))$，忽略常数项和低阶项
- 均摊时间复杂度：对多次操作的整体时间复杂度分析，适用于单次操作开销大但出现频率极低的场景（如动态数组扩容）
大O表示法特性
本文补充的两个关键特性：
-
只保留增长速率最快的项：O(2N + 100) = O(N)，O(N³ + 999N²) = O(N³)
- 注意：指数中的常数不能消，O(2^(2N)) = O(4^N)
-
大O表示法表示上界：O(N) 算法也可说成 O(N²)，只是上界不够"紧"
- 实际分析时数量级正确（线性/指数/对数级）即可
常见复杂度层级
| 复杂度 | 层级 | 说明 |
|---|---|---|
| O(1) | 常数级 | 哈希表查询 |
| O(logN) | 对数级 | 二分查找、平衡树 |
| O(N) | 线性级 | 单次遍历 |
| O(NlogN) | 对数线性 | 高效排序 |
| O(N²) | 平方级 | 嵌套循环 |
| O(K^N) | 指数级 | 递归穷举（K 为分支数） |
数组相关操作复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查/改（给定索引） | $O(1)$ | 随机访问，首地址+偏移量计算 |
| 末尾增/删 | $O(1)$ | 直接索引赋值/标记删除 |
| 中间增/删 | $O(N)$ | 需要数据搬移 |
| 扩容 | $O(N)$ | 新数组开辟+数据复制，均摊后仍为 $O(1)$ |