作业 -08- 数据结构与算法

算法的复杂度：时间复杂度、空间复杂度。

时间复杂度：

并不是计算程序具体的运行时间，而是算法执行语句的次数

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

O(1)，O(log(n))，O(n^a)多项式时间复杂度

O(a^n)和O(n!)多项式时间复杂度

空间复杂度：

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

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



NP问题

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

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

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

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



数据结构：

数组：

创建数组必须要内存中一块连续的空间。

数组中必须存放相同的数据类型

随机快速读写是数组的一个重要特性，根据数组的下标访问数据，时间复杂度为O(1)



链表：

链表可以使用零散的内存空间存储数据

所以链表中的每个数据元素都必须包含一个纸箱下一个数据元素的内存地址指针

要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度为O(n)

所以链表查询效率比数组低，但是增删数据效率比数组高

数组链表结合，可以实现快速查找和快速增删，Hash表结合了链表和数组的有点



Hash表：

通过计算key的hashcode，然后对hashcode对数据长度取模，计算出对应的hash索引，来实现快速访问数据，又可以快速增删数据

如果hash表的key冲突，则在key所在的hash表索引处，增加链表



栈：

数组和链表都被称为线性表

栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即“先进后出”。

线程调用栈如下图所示：