Вставка 3 ключей подряд в хеш с линейным зондом, какова вероятность того, что 4-й элемент требует 3 зондов? Я получаю 12/n ^ 3, потому что после вставки 1-го элемента есть 3 места, которые вы можете вставить для 2-го элемента ( слева от 1-го элемента, 1-го элемента, справа от 1-го элемента), то есть 3/n. и 3-й элемент, у вас есть 4 места для вставки, чтобы сделать их последовательными, поэтому 4/n и последний 4-й элемент должны быть вставлены в хэш 1-го элемента, поэтому 1/n. Вероятность 3/n * 4/n * 1/n = 12/n ^ 3 или просто 12/n ^ 2?
Вставка 3 ключей подряд в хэш с помощью линейного зонда, какова вероятность 4-го элемента, для которого требуется 3 зонда
Ответы (1)
Я думаю, вы пропустили (пару) случаев, когда первые два элемента не являются смежными, а третий элемент заполняет пробел. Математика аналогична, хотя 3/n*4/n + 2/n*2/n = 16/n^2, чтобы получить три соседних, а затем 1/n шансов попасть в первый, чтобы дать 16/n^3.
person
DrC
schedule
09.03.2013
