复杂度
算法复杂度
在数据结构与算法的学习中，我们最常见的就是用大 O 符号来描述算法的复杂度。
以下是一些最常用的大 O 标记法列表以及它们与不同大小输入数据的性能比较。
| 大 O 标记法 | 计算 10 个元素 | 计算 100 个元素 | 计算 1000 个元素 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log N) | 3 | 6 | 9 |
| O(N) | 10 | 100 | 1000 |
| O(N log N) | 30 | 600 | 9000 |
| O(N^2) | 100 | 10000 | 1000000 |
| O(2^N) | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
数据结构操作的复杂性
| 数据结构 | 连接 | 查找 | 插入 | 删除 | 备注 |
|---|---|---|---|---|---|
| 数组 | 1 | n | n | n | |
| 栈 | n | n | 1 | 1 | |
| 队列 | n | n | 1 | 1 | |
| 链表 | n | n | 1 | 1 | |
| 哈希表 | - | n | n | n | 在完全哈希函数情况下，复杂度是 O(1） |
| 二分查找树 | n | n | n | n | 在平衡树情况下，复杂度是 O(log(n)) |
| B 树 | log(n) | log(n) | log(n) | log(n) | |
| 红黑树 | log(n) | log(n) | log(n) | log(n) | |
| AVL 树 | log(n) | log(n) | log(n) | log(n) | |
| 布隆过滤器 | - | 1 | 1 | - | 存在一定概率的判断错误（误判成存在） |
数组排序算法的复杂性
| 名称 | 最优 | 平均 | 最坏 | 内存 | 稳定 | 备注 |
|---|---|---|---|---|---|---|
| 冒泡排序 | n | n^2 | n^2 | 1 | Yes | |
| 插入排序 | n | n^2 | n^2 | 1 | Yes | |
| 选择排序 | n^2 | n^2 | n^2 | 1 | No | |
| 堆排序 | n log(n) | n log(n) | n log(n) | 1 | No | |
| 归并排序 | n log(n) | n log(n) | n log(n) | n | Yes | |
| 快速排序 | n log(n) | n log(n) | n^2 | log(n) | No | 在 in-place 版本下，内存复杂度通常是 O(log(n)) |
| 希尔排序 | n log(n) | 取决于差距序列 | n (log(n))^2 | 1 | No | |
| 计数排序 | n + r | n + r | n + r | n + r | Yes | r - 数组里最大的数 |
| 基数排序 | n * k |
n * k |
n * k |
n + k | Yes | k - 最长 key 的升序 |
图操作
堆操作
