[Trdelnik]

Господа и дамы, есть же здесь люди, которые сталкивались с хеш-таблицами...
Вот не могу понять и все тут... Объясните, пожалуйста, элементарщину теории вероятностей, которая не хочет укладываться в голове.
Цитирую Вирта:
"Представим себе, что есть некоторый ключ, который нужно вставить в таблицу размером n, где уже содержится k элементов. Вероятность сразу же попасть на свободное место равна (n - k)/n. Тут все понятно, смотрим дальше... это же и вероятность (p1) того, что нужно всего одно сравнение. Вероятность того, что понадобится точно одна дополнительная попытка, равна вероятности конфликта при первой попытке, умноженная на вероятность попадания в свободное место при второй.
p1 = (n-k)/n
p2 = (k/n)*(n-k)/(n-1)
p3 = (k/n)*(k-1)/(n-1)*(n-k)/(n-2)
...."
А теперь внимание вопрос... Что такое (k/n) мне понятно... но вот почему в вероятности оно учитывается - это для меня остается загадкой.
Вопрос не критичен, мне просто хочется разобраться...
Заранее благодарю...

@темы: Программы

Comments

[Estimada]

То, что мы попадем со второй попытки, вероятно на (n-k)/(n-1), но ведь и сама эта попытка не абсолютно точно нужна будет. Нам нужна вторая попытка с вероятностью k/n. Соответственно, вероятность того, что вторая попытка будет, да ещё и будет удачной - (k/n)*(n-k)/(n-1)

[Trdelnik]

так... тогда тупой вопрос... почему вероятность нужности этой второй попытки k/n?

[Estimada]

Потому что у нас есть два варианта: в первую попытку мы попадем (вторая попытка не нужна) и в первую попытку мы не попадем (вторая попытка нужна) .В сумме вероятности этих двух событий равны 1. Вероятность первого варианта = (n-k)/n. Соответственно, вероятность второго варианта: 1-(n-k)/n=1-n/n+k/n=1-1+k/n=k/n

[Trdelnik]

о... Спасибо!) Огромное спасибо!