数据结构与算法 - 第八周总结

基本数据结构

1、数组

• 存储于一块连续的内存空间中

• 必须是相同的数据类型

• 指定下标读取的时间复杂度为O(1)

• 插入、删除的时间复杂度为O(n)



2、链表

• 数据存储可以存储在不连续的空间中

• 每个元素必须包含一个指向下一个元素的内存地址

• 查找复杂度为O(n)

• 修改、删除复杂度为O(1)



3、hash表

存储



key冲突



4、栈

后进先出



5、队列

先进先出

案例：搜索关系最近的好友、搜索最短路径



6、树

• 二叉排序树

• 平衡二叉排序树

• 选择二叉树恢复平衡

• 红黑（排序）树



7、红黑树VS平衡二叉树

• 红黑树最多3次旋转就会重新达成红黑平衡，时间复杂度O(1)

• 在大量增删的情况下，红黑树的效率更高

• 红黑树的平衡性不如平衡二叉树，查找效率要差一些



8、常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划