时间复杂度



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

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

• 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次旋转）， 保持红黑树满足定义

跳表

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

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



常用算法



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

穷举法

递归法

贪心算法

动态规划



•