算法的评估：正确性、可读性、健壮性（对不合理输入的处理能力）
时间复杂度：估算程序指令执行的次数
空间复杂度：估算所需要占用的存储空间
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 = 最后一个下标，形成循环。
网友评论