对于同一个数据结构来说，底层实现的不同往往会呈现出不同的时间复杂度。以数组为例：
| . |
普通数组实现 |
顺序数组实现 |
二分搜索树（平衡） |
| 插入 |
O(1) |
O(n) |
O(logn) |
| 查找 |
O(n) |
O(logn) |
O(logn) |
| 删除 |
O(n) |
O(n) |
O(logn) |
1. 动态数组
对于一个基于Java E[]实现的动态数组Array来说，它的时间复杂度如下：
- 增：O(n)
- 删：O(n)
- 改：已知索引 O(1)；未知索引 O(n)
- 查：已知索引 O(1)；未知索引 O(n)
- resize：通过均摊复杂度分析得 O(1)
2. 数组栈
对于一个基于动态数组Array实现的数组栈ArrayStack来说，它的时间复杂度如下：
- void push(E): O(1) 均摊
- E pop(): O(1) 均摊
- E peek(): O(1)
- int getSize(): O(1)
- boolean isEmpty(): O(1)
3. 数组队列
对于一个基于动态数组Array实现的数组队列ArrayQueue来说，它的时间复杂度如下：
- void enqueue(E): O(1) 均摊
- E dequeue(): O(n)
- E front(): O(1)
- int getSize(): O(1)
- boolean isEmpty(): O(1)
4. 循环数组队列
对于一个基于Java E[]实现的循环队列LoopQueue来说，它的时间复杂度如下：
- void enqueue(E): O(1) 均摊
- E dequeue(): O(1) 均摊
- E front(): O(1)
- int getSize(): O(1)
- boolean isEmpty(): O(1)
数组和链表
数组最大的优点：支持随机访问、快速查询。
数组最好用于索引有语义的情况。
链表最大的优点：动态。
链表不适合用于索引有语义的情况。
5. 链表
- 增：O(n)
- 删：O(n)
- 改：O(n)
- 查：O(n)
链表不适合修改操作；
如果只对链表头进行增删查操作：O(1)
6. 链表栈
- 与数组栈各操作的时间复杂度上是同一量级 O(1)。
- 时间上的差异可能在于：数组栈在分配空间方面；链表栈在new寻找内存空间方面。
7. 链表队列
- 与数组队列各操作的时间复杂度上是同一量级 O(1)。
- 特别的，链表的head容易做增、删操作，而tail只容易做增操作，故tail端入队，head端出队。
链表是天然的递归结构。递归调用是有代价的：函数调用+系统栈空间。
递归函数的调试：添加一个递归深度变量depth作为函数参数。
8. 双链表
9. 循环链表
10. 数组链表
11. 集合
| . |
LinkedListSet |
BSTreeSet |
BSTreeSet最优 |
BSTreeSet最差 |
| 增add |
O(n) |
O(h) |
O(logn) |
O(n) |
| 删remove |
O(n) |
O(h) |
O(logn) |
O(n) |
| 查contains |
O(n) |
O(h) |
O(logn) |
O(n) |
基于搜索树的实现：有序集合
基于哈希表的实现：无序集合
多重集合：集合中的元素可以重复
12. 映射
| . |
LinkedListMap |
BSTreeMap |
BSTreeMap最优 |
BSTreeMap最差 |
| 增add |
O(n) |
O(h) |
O(logn) |
O(n) |
| 删remove |
O(n) |
O(h) |
O(logn) |
O(n) |
| 改set |
O(n) |
O(h) |
O(logn) |
O(n) |
| 查contains |
O(n) |
O(h) |
O(logn) |
O(n) |
| 查get |
O(n) |
O(h) |
O(logn) |
O(n) |
基于搜索树的实现：有序映射
基于哈希表的实现：无序映射
多重映射：映射中的键可以重复
13. 优先队列
| . |
入队 |
出队（拿出最大元素） |
| 普通线性结构 |
O(1) |
O(n) |
| 顺序线性结构 |
O(n) |
O(1) |
| 堆 |
O(logn) |
O(logn) |
14. 最大堆
| 操作 |
时间复杂度 |
| add, Sift Up |
O(logn) |
| extractMax, Sift Down |
O(logn) |
实现1：先extractMax，再add，两次O(logn)
实现2：先将堆顶元素替换，再Sift Down，一次O(logn)
实现1：将n个元素逐个插入到一个空堆中，O(nlogn)
实现2：从最后一个非叶子节点往堆顶遍历，不断进行Sift Down，O(n)：证明略。
15. 线段树
| 操作 |
使用数组实现 |
使用线段树 |
| 更新 |
O(n) |
O(logn) |
| 查询 |
O(n) |
O(logn) |
16. Trie前缀树
应用：查询一个字符串字典，例如通讯录。
| 操作 |
使用树状字典 |
使用Trie |
| 查询 |
O(logn) |
O(w) |
如果有100万个条目（2^20），logn约为20；
Trie中w为查询单词的长度，大多数单词的长度小于10。
17. 并查集
数组实现，数组结构的Quick Find版：
查看元素p和元素q是否所属一个集合，时间复杂度是O(1)
合并元素p和元素q所属的集合，时间复杂度是O(n)
数组实现，树状结构的Quick Union版（由孩子指向父亲的特殊树结构）：
查看元素p和元素q是否所属一个集合，时间复杂度是O(h)
合并元素p和元素q所属的集合，时间复杂度是O(h)
路径压缩有的并查集：时间复杂度为O(log*n) -> iterated logarithm
比O(logn)要快，略慢于O(1)
18. AVL树
名称来源：发明者的名字开头字母。
1962年提出，最早的自平衡二分搜索树结构。
平衡二叉树：对于任意一个节点，左子树和右子树的高度差不能超过1（平衡因子绝对值不超过1）
真正的O(logn)
19. 2-3树
是一种绝对平衡的搜索树。即根节点到任意一个叶子节点所经过的节点数量一定相同。
20. 红黑树
是一种保持“黑平衡”的二叉树。
不是平衡二叉树，最大高度为2logn，时间复杂度都是O(logn)
与AVL树的对比：
增删操作：红黑树更快，因为维持平衡的时间消耗少
查询操作：AVL更快
21. 哈希表
链地址法解决哈希冲突时，总共有M个地址，如果放入哈希表的元素为N：
（1）每个地址用链表实现，则时间复杂度：O(N/M)
（2）每个地址用平衡树实现，则时间复杂度：O(log(N/M))
动态空间的哈希表：均摊复杂度是O(1)
