第 8 周 996 日记

数据结构与算法

时间复杂度与空间复杂度

NP 问题

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

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

NP ?= P

NP-hard 问题：比 NP 问题更难的问题（NP 问题的解法可以规约到 NP-hard 问题的解法）

NP 完全问题：是一个 NP-hard 问题，也是一个 NP 问题。

常见数据结构

• 数组

• 链表

• Hash 表

• 栈

• 队列

• 树

• 二叉排序树

• 不平衡的二叉排序树

• 平衡二叉（排序）树

• 红黑（排序）树

• 跳表

常见算法

• 穷举算法

• 递归算法

• 贪心算法

• 改进贪心算法 - 迪杰斯特拉算法（最快路径）

• 动态规划算法

• 遗传算法

网络通信协议

Web 请求的一次网络通信历程

OSI 七层模型和 TCP/IP 四层模型