1.数据结构、大O表示法

算法的评估：正确性、可读性、健壮性（对不合理输入的处理能力）

时间复杂度：估算程序指令执行的次数

空间复杂度：估算所需要占用的存储空间

2^3 = 8
2^4 = 16
3 = log2(8)
4 = log2(16)
while((n = n / 5) > 0) // 时间复杂度 log5(n)
if(i == 1,i < n, i * 2) // 时间复杂度 log2(n)

平方阶、立方阶、指数阶 的时间复杂度都不可取

均摊复杂度：比如动态数组的add操作，复杂度是O(1)，到扩容节点复杂度为O(n),均摊下来为O(2)，add函数的均摊复杂度为O(1)

复杂度震荡：不合理的设计可能造成复杂度震荡，比如add和remove设置的节点乘积为1，那么对某个函数的增删操作会造成扩容或缩容的操作，复杂度都为O(n)，解决方法为设置add、remove函数的不同扩容、缩容节点

数据结构

• 线性结构

  • 线性表（数组、链表、栈、队列、哈希表）
  • 有N个相同类型元素的有限序列
  • 索引、首节点（首元素）、尾结点（尾元素）

  数组是一种顺序存储的线性表，所有元素的内存地址是连续的

  动态数组（可变数组）存储对象时，数组内存储的是对象的地址，可以避免空间的浪费。

• 树形结构

  • 二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树

• 图形结构

  • 邻接矩阵、邻接表

数组，在内存中固定长度，元素在内存中是连续的。

动态数组，可以自动扩容、缩容的数组，数组元素添加增删操作

链表，链式存储的线性表，所有元素的内存地址不一定是连续的，可以解决动态数组内存空间浪费的问题，需要多少内存就申请多少内存。

数据结构的选择

动态数组：开辟、销毁内存空间次数较少，但可能造成内存浪费

双向链表：开辟、销毁内存空间的次数较多，但不会造成内存浪费

如果频繁在尾部进行添加、删除操作，选择动态数组、双向链表

如果频繁在头部进行添加、删除操作，用双向链表

如果频繁的在任意位置进行添加、删除操作，用双向链表

如果频繁的进行查询操作，用动态数组

循环链表

两种不同的情况：链表中只有一个元素，和链表中有多个元素

特点：链表中的最后一个元素与第一个元素相连，形成闭环

验证：快慢指针的方式来验证链表是否有环，慢指针指到nil，那么确定无环

约瑟夫问题：在一个环中，每前进固定位数后移除当前元素。

循环链表类要考虑设置一个成员变量，三个方法

current，用于记录指向某个节点

void reset：current指向first

void next：current往后一步

void remove：删除current指向节点，删除成功后current 后移

静态链表

通过两个数组来实现链表功能，一个数组保存元素，另一个数组保存对应下一个元素在元素数组内的下标。

动态数组优化

可通过添加一个成员变量first来记录第一个元素的位置，比如移除下标为0的元素，那么first = 1,数组的第一个元素就从下标1开始。在下标为0的元素前插入数据，数组尾部如果还有空位，将新元素写到尾部元素，first = 最后一个下标，形成循环。