架构师训练营第八章总结

1.数据结构与算法

时间复杂度



空间复杂度

NP 问题

数组

数组是最常用的数据结构，创建数组必须要内存中一块连续的空间，并且数组中必须存放相同的数据类型。

随机快速读写是数组的一个重要特性，但是要随机访问数据，必须知道数据在数组中的下标。如果我们只是知道数据的值，想要在数组中找到这个值，那么就只能遍历整个数组，时间复杂度为 O(N)。



链表

不同于数组必须要连续的内存空间，链表可以使用零散的内存空间存储数据。不过，因为链表在内存中的数据不是连续的，所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

相比在链表中轻易插入、删除一个元素这种简单的操作，如果我们要想在数组中插入、删除一个数据，就会改变数组连续内存空间的大小，需要重新分配内存空间，这样要复杂得多。



Hash表

Hash 表中数据以 Key、Value 的方式存储。存储的时候将 Key、Value 写入 Hash 表，读取的时候，只需要提供 Key，就可以快速查找到 Value。

Hash 表的物理存储其实是一个数组，如果我们能够根据 Key 计算出数组下标，那么就可以快速在数组中查找到需要的 Key 和 Value。

事实上，(“abc”,“hello”) 这样的 Key、Value 数据并不会直接存储在 Hash 表的数组中，因为数组要求存储固定数据类型，主要目的是每个数组元素中要存放固定长度的数据。所以，数组中存储的是 Key、Value 数据元素的地址指针。一旦发生 Hash 冲突，只需要将相同下标，不同 Key 的数据元素添加到这个链表就可以了。查找的时候再遍历这个链表，匹配正确的 Key。



栈

栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。我们可以把栈可以想象成一个大桶，往桶里面放食物，一层一层放进去，如果要吃的时候，必须从最上面一层吃，吃了几层后，再往里放食物，还是从当前的最上面一层放起。

队列

队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

在软件运行期，经常会遇到资源不足的情况：提交任务请求线程池执行，但是线程已经用完了，任务需要放入队列，先进先出排队执行；线程在运行中需要访问数据库，数据库连接有限，已经用完了，线程进入阻塞队列，当有数据库连接释放的时候，从阻塞队列头部唤醒一个线程，出队列获得连接访问数据库。

常用算法

穷举算法

递归算法

贪心算法

动态规划

网络通讯协议

非阻塞网络IO

select poll epoll