問題一:
設一表格長度為n,表格內第i項目之取用機率為Pi，
查詢表內第i項目比較之次數為Ci，請寫出平均查詢長度之公式!
答案:ΣCiPi+1
這題我認為答案是ΣCiPi，不知道為什麼會多加1
問題二:
如果hash table有m個位置，現在有n個資料要 依序插入，
請計算整個插入過程中，平均會有幾次碰撞?
這題我的計算是:
(0+1+2+....+n-1)/n
但是答案卻是:
(0+1+2+....+n-1)/m
這是我搞錯還是答案錯了阿??
不是要除以資料數才對嗎?
麻煩知道的大大為我解答一下，感謝><
--
設一表格長度為n,表格內第i項目之取用機率為Pi，
查詢表內第i項目比較之次數為Ci，請寫出平均查詢長度之公式!
答案:ΣCiPi+1
這題我認為答案是ΣCiPi，不知道為什麼會多加1
問題二:
如果hash table有m個位置，現在有n個資料要 依序插入，
請計算整個插入過程中，平均會有幾次碰撞?
這題我的計算是:
(0+1+2+....+n-1)/n
但是答案卻是:
(0+1+2+....+n-1)/m
這是我搞錯還是答案錯了阿??
不是要除以資料數才對嗎?
麻煩知道的大大為我解答一下，感謝><
--
All Comments