1、注意双向链表的操作中 只要默认已经访问了链表上的第k个元素，则其他operation就都是θ(1)*
2、注意单向链表 替换第k个元素 是θ(1)*
Quiz1：
1、别忘了数组扩容是2的n次方
2、逆波兰就是 从左往右顺序
922 关于递归&时间复杂度的分析方法
脑子乱了一天了，一直算不出来T(n) 先在网上看到面试题：
递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数
但是还没算出来（😵）
924
递归方程的一些解法已经掌握（如更换变量（联想一下 2的k次方，直接展开等）
另外可以领用wolfram在线直接计算
另外那个double-hash中的i实际上对应的是每一个key,也就是说每一次i都是从0开始的！
927第二次小测
错误百出！！！！！！！！！！！！！！
1、关于O的传递，quiz2的第一道判断题就错了，一定要注意把极限式子列好列完整，
如f(n) = O(g(n)),f(n) = O(h(n)), 你不可能直接判断f(n)和g(n)h(n）的关系啊！
习题课谈到一点特别好：没有特殊说明，谁知道他们一定是无穷大呢？
例如1/n = O(1/n)有什么问题吗？
2.哈希碰撞的原因：首先是哈希表的大小（一共就十个可放的地方不冲突才怪）
再就是哈希函数了
另外别忘了数据本身的因素！你要存的数据要是趋向性太强（如一堆差不多一样大的数字），不碰才怪！
3、关于渐进分析的术语：
asymptotically tight bound 渐进紧确界 是Θ
区分：渐进上界 asymptotically upper bound是大O
算法导论中特别提到，由大O记号提供的渐进上界 可能是也可能不是渐进紧确的
如2n^2 = O(n^2) 是渐进紧确上界 这是没错的
这也就是quiz中谈到的 asymptotically upper tight bound
渐进下界aymptotically lower bound 是大Ω
非渐进紧确的下界是ω，非渐进紧确的上界是小o
4、关于double hashing和quadratic probing的定量方程记不住！必须记住！
二次探查quadratic probing:
h(k,i) = (h'(k) + c1*i + c2*i^2) mod m
双重散列 double hashing
h(k,i) = (h1(k) + i*h2(k)) mod m
其实关键就是注意double hashing里面的h2那个辅助散列函数(auxiliary hash function)是直接和i相乘的，这也是quiz2最后一道判断题做错了的原因！！！！！！！！！！！！！
5、最后一个小知识点：分块算法（竞赛常用，优雅的暴力）
其实是一种常见的时间复杂度带根号的算法
https://blog.csdn.net/pengwill97/article/details/80900930
这也对应了我们quiz的最后一题，T(n) = B^2 + n^2/B^2
这种形式一下子就得想到基本不等式啊（三个月不碰数学就废了是吧）
一列答案不就出来了！