[閒聊] Average, Expected, Amortized

[fxfxxxfxx (愛麗絲)]

看到今天 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 強，所以如果是否證的話還不能拿一百萬）


結論就是，這幾個概念雖然有點像，但還是有點差別

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667968659.A.FC0.html
推 hduek153: 懂了
推 oooptt: 所以教授要的答案是什麼@@
推 Rushia: 大師 你標題可以放LEETCODE嗎 我方便搜尋
推 pandix: 大師
※ 編輯: fxfxxxfxx (140.112.16.175 臺灣), 11/09/2022 13:01:29