Re: [問題] 雜湊函數、cpu執行速度等問題
※ 引述《fzrmitsul (我的妹妹很可愛)》之銘言：
: 1.假設有一程式在某台電腦中執行需要100秒，其中乘法指令共花掉80秒。若想縮短
: 執行時間，前提是只增加乘法器的速度，試問該乘法器至少需提升幾時間，才能
: 將執行時間從100秒縮短為25秒?
: (a)4倍 (b)5倍 (c)12倍 (d)16倍
: 不知這題該怎麼算。
乘法指令80秒 => 其他指令20秒
∴TOTAL 100秒->25秒 => 乘法指令80秒->5秒
1/5 ÷1/80 = 16倍
答案為D
: 2.若以函數f(關鍵值)=(關鍵值+i*5) mod 23建立hashing table，其中i代表碰撞發生
: 次數。當關鍵值分別為43,20,66,23,91的資料依序被存在原先為空的雜湊表中
: 則全部儲存完後，下面哪個位址尚未儲存關鍵值?
: (a)0 (b)7 (c)20 (d)21
: 我算的結果是f(43)=x..餘20
: f(20)=x..餘20..發生碰撞(那是要把這個關鍵值存在哪呢?21嗎?)
: f(66)=x...餘2
: f(23)=x...餘0
: f(91)=x...餘22
: 為什麼答案會是d呢??那為什麼不是b呢??
: 可能觀念有錯。請各位先進糾正..
f(20)為25
∵f(43) = 20
f(20) = 20 發生碰撞 => i = 1 => f(20) = (20+1*5)%23 = 2
f(66) = 20 發生碰撞 => i = 2 => f(66) = (66+2*5)%23 = 7
f(23) = 0
f(91) = 22
所以答案當然為D
如果只是依照公式來算，A也是考量答案
所以我認為題目沒有寫清楚
正確的函數表示應該是：
f(關鍵值) = 關鍵值 % 23 = A => 當之前沒有出現過A的結果
f(關鍵值) = (關鍵值+iA*5) % 23 => 當A之前已經出現過
iA = A累積出現的次數 = 發生碰撞的次數
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.92.133
推
06/08 08:31, , 1F
06/08 08:31, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：