数据结构与算法
算法复杂度
大O记法
| 数据结构 | 查找 平均/最坏 | 插入 平均/最坏 | 删除 平均/最坏 | 遍历 |
|---|---|---|---|---|
| 数组 | O(N)/O(N) | O(N)/O(N) | O(N)/O(N) | ~~ |
| 有序数组 | O(logN)/O(N) | O(N)/O(N) | O(N)/O(N) | O(N) |
| 链表 | O(N)/O(N) | O(1)/O(1) | O(1)/O(1) | ~~ |
| 有序链表 | O(N)/O(N) | O(N)/O(N) | O(1)/O(1) | O(N) |
| 二叉查找树 | O(logN)/O(N) | O(logN)/O(N) | O(logN)/O(N) | O(N) |
| 红黑树 | O(logN)/O(logN) | O(logN)/O(logN) | O(logN)/O(logN) | O(N) |
| 平衡树 | O(logN)/O(logN) | O(logN)/O(logN) | O(logN)/O(logN) | O(N) |
| 二叉堆/优先队列 | O(1)/O(1) | O(logN)/O(logN) | O(logN)/O(logN) | O(N) |
| 哈希表 | O(1)/O(1) | O(1)/O(1) | O(1)/O(1) | O(N) |
