数据结构和各自的复杂度

一、动态数组

情景：在n个动态的整数中搜索某个整数
1、从0个位置开始遍历搜索，平均时间复杂度O(n)
2、如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)；但是添加、删除的平均时间复杂度是O(n)
3、set和get在index位置的元素时，复杂度为O(1)
明显的缺点：可能会造成内存空间的大量浪费，能否用到多少就申请多少内存？

二、链表

链表可以解决：数组的内存空间浪费的问题。
add、remove：复杂度都是O(n)
set(int index, E element)、get(int index, E element)：复杂度也是O(n)
双向链表比单向链表的优势：以删除操作为例，几乎节省了一半的操作

数组和链表的复杂度比较

三、二叉搜索树BST

复杂度O(h)跟树的高度(h)有关，
最好的情况是：搜索、添加、删除都是O(h)==O(logn)
最坏的情况是：退化成链表，复杂度都是O(n)。

四、AVL树

添加：

• 可能会导致所有祖先节点都失衡
• 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需O(1)次调整】。

删除：

• 只可能导致父节点失衡
• 让父节点恢复平衡后，可能导致更高层的祖先节点失衡【最多需O(logn)次调整】

平均时间复杂度：

• 搜索：O(logn)
• 添加：O(logn)，仅需O(1)次旋转操作
• 删除：O(logn)，最多需要O(logn)次旋转操作

与BST树对比，AVL树的性能从O(n)降到了O(logn)级别，大大提高了效率

五、红黑树

平均时间复杂度：

• 搜索：O(logn)
• 添加：O(logn)，仅需O(1)次旋转操作
• 删除：O(logn)，仅需O(1)次旋转操作

与AVL树对比，红黑树的性能主要体现在删除上，删除后旋转次数是O(1)级别的