Ruby函數來計算跳過列表的平均搜索時間

我正在嘗試編寫一個ruby函數來確定跳過列表的平均預期搜索時間。我沒有很強的數學背景，我相信我從這個函數中得到的結果是不正確的。Ruby函數來計算跳過列表的平均搜索時間

n =在列表

base促進概率=分母元素的個數。即，如果4個節點的1被提升基座= 4

def lookup_eficiency(n, base) 
    return (Math.log(n, base)*(base/2.0)) 
end

我怎樣表達在紅寶石的等式將帶元件在跳過列表和數目的基礎，並返回平均搜索時間？

來源

2013-05-04 dan_paul

那又如何？你的問題是什麼？ – sawa 2013-05-04 20:22:17

對不起，我認爲這是隱含的，但我只是編輯了這個問題，以明確它。 – 2013-05-04 20:26:34

如果你想測量函數的速度，你可以使用模塊'Benchmark' http://www.ruby-doc.org/stdlib-1.9.3/libdoc/benchmark/rdoc/Benchmark.html。這是否回答你的問題的一部分？ – Rots 2013-05-04 20:33:18

由於跳過列表查找的複雜度是O（logbase（n/base）），所以呢？

def lookup_efficiency(n, base) 
    Math.log(n/base)/Math.log(base) 
end

確保你的基地是一個浮動，所以你不會最終與整數除法！

來源

2013-05-04 23:13:41 SudoGuru

爲什麼不直接調用'base.to_f'？如果你已經有一個浮動，它將是一個無操作。 – 2013-05-04 23:39:23

你其實是對的。我只是認爲不要使用比OP所需的基本功能更多的代碼來代替它。 – SudoGuru 2013-05-04 23:41:20

謝謝，但是當我測試你的功能時，我得到的結果看起來不對。例如，對於具有1000個元素的跳躍列表和1/10的提升概率（'n = 1000'和'base = 10'），該函數返回'2.0'。如果'base = 20'，函數返回'1.306 ...'。我認爲這是不正確的，因爲在任何列表中，如果'n> base'，搜索操作平均需要單獨訪問大約'base/2'節點。 – 2013-05-05 12:08:08

Ruby函數來計算跳過列表的平均搜索時間

回答

相關問題