Функция Ruby для вычисления среднего времени поиска для списка пропусков

Question

Я пытаюсь написать рубиновую функцию, чтобы определить среднее ожидаемое время поиска для списка пропусков. У меня нет сильного математического фона, и я считаю, что результаты, которые я получаю от этой функции, неверны.

n = количество элементов в списке

base = знаменатель вероятности продвижения. т.е., если 1 из 4 узлов повышены базовый = 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 

Удостоверьтесь, что ваша база - это поплавок, поэтому вы не получаете целочисленного деления!