看到今天 LeetCode 的每日一题有感而发
来复习一下这好久以前学的东西免得忘记
想到什么就写什么，所以废话比较多一点，顺便赚一点p币
有三个有点像的东西
1. Average Case
2. Expected Running Time
3. Amortized Analysis
先讲今天每日一题出现的 amortized analysis
不同于大部分题目都是 offline 叫你一次回传所有结果
今天的题目要求 online ，也就是每次呼叫 next() 你就要回传当下的结果
因此看讨论区才会出现所谓 amortized 是 O(1)
其实不过就是讨论“最差情况”下呼叫 n 次平均要花的时间
因为每个元素只会 push 进和 pop 出来各一次
所以 n 个元素还是最多花 O(n)，除下来就是均摊 O(1)
注意是“最差情况”，和输入无关
当然和真正的每次呼叫都是 O(1) 还是有点差别
就是 latency 会比较高
可能就像是游戏玩一玩突然卡帧，偶尔会花比较多时间
不过我比较想讲的是 average case 和 expected time 的分别
一个算法的 average case 复杂度的意思是：
对给定的长度 n，且输入的分布是在所有长度是 n 的输入中均匀取样的话
平均所花的执行时间
记得以前在上平行课的时候
教授突然点人起来问：“quick sort 复杂度是多少阿？”
被点到的人就回：“O(nlogn)”
教授就问：“你确定吗”
同学想了一下，说 “worst case 是 O(n^2)，但 average case 是 O(nlogn)”
结果教授非常的不满意，说哪有什么 average case，乱来
我那时候一头雾水，毕竟维基百科上就写着 quick sort 的 average case 是 O(nlogn)
不过现在想想的确没错，其实 average case 在这里不太适合
因为要用到 average case 的话，你必须对输入的分布有所假设
均匀分布其实是很强的假设，很多情况下是不适用的
特别是输入是使用者可控的情况就更糟了
有一个很有名的攻击手法，叫做 Hash-Flooding Attack
原理是，我们通常假设 hash map 的存取是 O(1)
但假如今天 hash function 是攻击者可知的
他可以精心设计一组 hash 值全部一模一样的输入
如果 hash table 的底层实作是 linked list 的话
单次存取的复杂度直接掉到 O(n)
n 次存取要花 O(n^2)，很容易就造成 DoS
解法有几种，像是如果 linked list 超过一定长度就改成平衡树，变成 O(logn)
或是用 keyed hash (可以用像是 AES 的来做)，让 hash function 是攻击者不可知的
而 expected time 和前面不同的地方在于
他的随机性是来自算法本身
例如 quick sort，假如先随机洗牌一次再进行排序
在这个情况下，其实不管输入是什么，执行时间的期望值都是一样的
造成不同的地方是在算法内部抽 random number 时产生的随机
所以一个 expected time 是 O(n) 的算法是这样的：
给定 n ，对“任意”长度为 n 的输入，执行时间的期望值都不会超过 T(n)
其中 T(n) = O(n)
至于 average case，其实比较多用的地方是在密码学这一块
因为这个时候立场颠倒，“出题方”是我们
我们想说的是，对任意的算法（攻击者）
我们被攻破的机率非常非常小
这个时候 worst case 反而不能用
因为 worst case 的意思是
对于某个特定的算法，存在一组输入使他算不完
但这跟我们的需求不同，我们要的是
我们出出来的题目（例如两个大质数乘积的因式分解）对所有算法都很难
所以这个时候我们要的反而是 average case ，
用 RSA 的质数因式分解举例，我们希望有的结果就会是：
对于所有多项式时间的随机算法（攻击者），
对足够长的长度 K （常被称为 security parameter）
在长度是 K 的质数中选出 p, q，并计算出 n = pq
攻击者拿到 n 后计算出的答案是 p 或 q 的机率可以忽略不计
至于什么叫可以忽略不计，可以看一些密码学的介绍
当然上面这个叙述是不是真的没人知道
如果你证出来了，可以去领 100 万美金
（这个结论比 P != NP 强，所以如果是否证的话还不能拿一百万）
结论就是，这几个概念虽然有点像，但还是有点差别