[閒聊] Average, Expected, Amortized

看板Marginalman作者fxfxxxfxx (愛麗絲)時間1年前 (2022/11/09 12:37)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串1/1

看到今天 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

11/09 12:41, 1年前 , 1^F

11/09 12:41, 1^F

推

oooptt

11/09 12:43, 1年前 , 2^F

11/09 12:43, 2^F

推

Rushia

11/09 12:47, 1年前 , 3^F

11/09 12:47, 3^F