一、时间复杂度与空间复杂度

1.时间复杂度:算法执行语句的次数

(1) O(2^n)表示对n数据处理需要进行2^n次计算

(2) O(1)、O(log(n))、O(n a)多项式时间复杂度

(3) O(a n)、O(n!)非多项式时间复杂度

2.空间复杂度

(1) 一个算法在运行过程中临时占用存储空间大小的亮度

(2) O(n)表示需要临时存储N个数据



二、NP问题

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

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

NP-hard: 比NP问题更难得问题

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



三、数组

创建数组必须要内存中一块儿连续的空间。且必须存放相同的数据类型。随机快速读写是数组的一个重要特性，使用数组的下表访问数据，时间复杂度是O(1)



四、链表

1.链表可以使用零散的内存空间存储数据。要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是O(N)

2.链表中增删数据要比数组性能好得多。

3.数组链表结合，可以实现快速查找和快速增删。



五、Hash表

1.使用value的hashcode求余的方式，实现快速定位。

2.当余数出现冲突时，使用hash链表解决。



六、栈

1.数组和链表都被成为线性表

2.栈就是在线性表的基础上加了限制条件：后进先出

3.栈帧：JVM 执行 Java 程序时需要装载各种数据到内存中，不同的数据存放在不同的内存区中（逻辑上），这些数据内存区称作运行时数据区（Run-Time Data Areas）。其中 JVM Stack（Stack 或虚拟机栈、线程栈、栈）中存放的就是 Stack Frame（Frame 或栈帧、方法栈）。



七、队列

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

典型场景：应用生产者消费者。



八、二叉排序树

1.左子树上所有节点的值均小于或等于它的根节点的值。

2.右紫薯上所有节点的值均大于或等于它的根节点的值。

3.左右紫薯也分别为二叉排序树。



九、二叉不平衡数



十、平衡二叉（排序）树