第 8 周 - 数据结构与算法

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

时间复杂度



  • 描述算法执行语句的次数,而非具体的运行时间

  • 常见时间复杂度表示方法有:

  • O(1) O(n) O(n2) O(logn) O(nlogn) O(n3) O(2n)

空间复杂度



  • 描述算法在运行过程中占用存储空间大小的量度(空间换时间)

  • O(n) 表示需要临时占用n个数据

NP问题

  • P:能在多项式时间复杂度内解决的问题

  • NP:能在多项式时间复杂度内验证答案正确与否的问题

BALABALA

数组

  • 随机访问时间复杂度为O(1),写入时间复杂度为O(n),插入数据时,后续数据需要向后移

  • 当数据长度不够时,需要重新申请一段更多在连续空间,复制扩容

Hash表

  • 余数Hash+队列的数据结构,读写时间复杂度都是O(1)

  • Hash 表 Key 相同的元素被存在一个键表中

  • 读写时,先根据Key的Hash余数从数组中找到键表的地址,再从键表写入数据或逐一与Key运行比较,找到Entity

  • 在线性表的基础上加了操作限制条件,后进先出

  • 线程调用栈,用于调用上下文数据的存储

链表



  • 有序列表,可以使用零散的内存空间存储数据,由指针将相邻空间头尾接连越来

  • 写入时间复杂度为O(1), 读取数据需要从表头逐一查找,所以时间复杂度为O(n)

队列

  • 一种操作受限,先进先出的线性表

  • 生产者来不及消费的数据可以放入队列,当队列为空,消费者无法消费,或队列已满,生产者无法添加数据时,可以通过阻塞使线程处理等待。

  • 最短路径算法应用场景

二叉树

  • 二分法快速存储数据

  • 当二叉树失去平衡,将失去二分法寻址特性

  • 旋转二叉树恢复平衡

红黑(排序)树

  • 每个节点只有两种颜色:红与黑

  • 根节点是黑色的

  • 每个叶子节点都是黑色的空节点

  • 从根节点到叶子节点,不会出现两个连续的红色节点

  • 从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点。

  • 增删节点的时候,红黑树通过染色和旋转(最多只需3次旋转), 保持红黑树满足定义

跳表

  • 链表增加指针,指向不连续节点,实现大跨度的跳转

  • 空间复杂度换取时间复杂度



常用算法



此处是一个跳表的三级跳板,请跳到页尾

穷举法

递归法

贪心算法

动态规划



  • 



用户头像

Dawn

关注

还未添加个人签名 2018.07.04 加入

还未添加个人简介

评论

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