时间复杂度

表示算法执行语句的次数

多项式复杂度：O(1), O(n), O(n^a)

非多项式复杂度：O(a^n), O(n!)

空间复杂度

表示临时占用的存储空间大小

O(n)

NP 问题

非确定性多项式问题 Non-deterministic polynomial，指其解的正确性能够被存在一个多项式检查算法的问题

常见数据结构

线性表

数组 - 连续内存空间

链表 - 长于增删，短于查找

Hash 表

通常是数组和链表的结合体。

栈

先进后出 - 线程调用栈

队列

先进先出 - 生产者消费者队列

二叉排序树

便于二叉查找

存在不平衡性

平衡二叉树

左右子树的深度差不超过 1 的二叉排序树

通过旋转来确保插入和删除平衡

插入时最多只需要 2 次旋转

删除时次数不确定，时间复杂度 O(logN)

红黑树

最多只需要 3 次旋转就可以重新恢复平衡，时间复杂度 O(1)

大量增删的情况下，红黑树 效率比 平衡二叉树更高

平衡性不如平衡二叉树，查找效率要差一些

跳表

通过 多层 排序来实现增删查找效率的提升

通过 空间 换 时间，需要额外的存储空间

常用算法

递归算法

注意一定要有退出条件

贪心算法

不一定是最优解

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

递进遍历所有邻居节点，记录所有到该节点的最短路径；直到最终节点

动态规划

通过减小目标值，拆解大问题为小问题，通过归并小问题的最优解，寻找大问题的最优解

遗传算法

TODO - 待研究

不一定是最优解