1

スキップリストの平均予想検索時間を決定するルビ関数を作成しようとしています。私は強い数学のバックグラウンドを持っていないので、この関数から得られる結果は正しくないと思います。

n= リスト内の要素数

base= 昇格確率の分母。つまり、4 つのノードのうちの 1 つが昇格された場合、ベース = 4

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

スキップリストとベースの要素数を取り、平均検索時間を返すRubyの方程式をどのように表現すればよいですか?

4

1 に答える 1

0

スキップリスト検索の複雑さはO(logbase(n/base))なので、これはどうですか？

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

整数除算で終わらないように、基数が浮動小数点数であることを確認してください。

于 2013-05-04T23:13:41.300 に答える