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

用户头像
孙志平
关注
发布于: 2020 年 07 月 29 日

基本数据结构

1、数组

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

  • 必须是相同的数据类型

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

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



2、链表

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

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

  • 查找复杂度为O(n)

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



3、hash表

存储



key冲突



4、栈

后进先出



5、队列

先进先出

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



6、树

  • 二叉排序树

  • 平衡二叉排序树

  • 选择二叉树恢复平衡

  • 红黑(排序)树



7、红黑树VS平衡二叉树

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

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

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



8、常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划



用户头像

孙志平

关注

还未添加个人签名 2018.05.08 加入

还未添加个人简介

评论

发布
暂无评论
数据结构与算法 - 第八周总结