ruby - 用于计算跳过列表的平均搜索时间的 Ruby 函数

Question

我正在尝试编写一个 ruby​​ 函数来确定跳过列表的平均预期搜索时间。我没有很强的数学背景，我相信我从这个函数得到的结果是不正确的。

n= 列表中的元素数

base=晋升概率的分母。即如果提升 4 个节点中的 1 个，则 base = 4

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

如何在 Ruby 中表达一个方程，该方程将采用跳过列表和基数中的元素数量并返回平均搜索时间？

Answer 1

由于跳过列表查找的复杂性是 O(logbase(n/base))，那么这个怎么样？

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

确保你的基数是一个浮点数，这样你就不会以整数除法结束！