随机算法

Las Vegasi:算法准确性 ok，但是运算时间不固定。代表：快排。
Monte Carlo:运行时间 ok，但是准确性不保证。
主要介绍一下蒙特卡洛方法的例子：

1. Freivalds' algo

https://blog.csdn.net/out_of_memory_error/article/details/83692642

2.全局最小割的 karger's algorithm

https://www.cnblogs.com/demoZ/p/4295440.html

Streaming algo

根据 markov 不等式和 chebyshev 不等式。
证明在一定误差范围内，可以将数据记录的尺寸从 logn(2 进制计数) 压缩到 loglogn.

然后介绍了 Distinct elements 问题的 Idealized algorithm 方法，并进行了推导。
最后介绍了 02 年的一个近似方法。

Hash

推导存在全域哈希。
全域哈希和完美哈希可以参考：
https://blog.csdn.net/lzq20115395/article/details/80517225
完美 hash 在 key 不变的时候可以使用，会变化的话，慎用。

CS170 总算扫完了。准备扫操作系统了，需要做 HOMEWORK，认真做了。