学习笔记
五毒神掌： 5-10 分钟读题和思考，如果没有思路，看题解，默写代码 马上自己写，提交LeetCode，多种解法，体会优化 24 小时之后，再重复做题 一周后重复做题 面试前一周恢复性训练
本质是通过在最合适的时间进行多次训练，达到掌握、熟练和融会贯通知识的作用。至于是不是五次，以及具体在哪个时间点回顾来巩固记忆，具体个人会有所区别。老师提供的只是许多前人尝试后根据经验总结推测出的比较好的参数。不过主体思想“过遍数，每遍时间不要太长”是正确的方向。
O(1): Constant Complexity 常数复杂度 O(log n): Logarithmic Complexity 对数复杂度 O(n): Linear Complexity 线性时间复杂度 O(n^2): N square Complexity 平方 O(n^3): N cubic Complexity 立方 O(2^n): Exponential Growth 指数 O(n!): Factorial 阶乘
判断时，只看最高复杂度的运算
比较特别的例子有： 复杂度：O(logN) for(int i=1; i<n; i=i*2){} 和 复杂度：O(k^n) 递归，斐波那契数列Fibonacci sequence
通过重复来减少工作量，而计算机里最基础的重复包括：
一切解题方法都由这三种操作来完成！！！！！！！！！
各种遍历的时间复杂度都是O(n)，因为每个元素都要过一次。（图遍历、二叉树遍历）
但是二分查找的时间复杂度是O(logN)
跳表的查询的时间复杂度是O(logN)。利用多级索引进行了升维，也就是用空间换时间！！！！！！！
跳表的元素必须有序
https://www.bigocheatsheet.com/
值得注意的是哈希表！Hash Table的查询的时间复杂度是O(1)！！！！！！！
数组：在内存中开辟连续的内存地址，存储元素
链表：当前Node对象储存当前节点值与下一节点内存地址
跳表：带有跳表索引的链表，只能用于元素有序的情况下，用来取代平衡树二分查找
| 左append | 右append | 查询 | 插入 | 删除 | |
|---|---|---|---|---|---|
| 数组 | O(1) | O(1) | O(1) | O(n) | O(n) |
| 普通链表 | O(1) | O(1) | O(n) | O(1) | O(1) |
| 跳表 | O(1) | O(1) | O(log n) | O(log n) | O(log n) |
空间复杂度上，数组最少，普通链表第二，跳表最高，但，都是O(n)。
链表应用：LRU Cache
跳表应用：Redis