9
Ben yolu bu sorunu overthinking gibi hissediyorum, ama burada Beklenen sayısı
ben iç dizide M yuvaları bir karma tablo var ... Neyse gider. N elementini hash tablosuna eklemem gerekiyor. Her bir slot için eşit olasılıklı bir yuvaya rastgele bir eleman ekleyen bir karma fonksiyona sahip olduğumu varsayarsak, karma çarpışmaların toplam sayısının beklenen değeri nedir?(Bunun bir programlama sorusundan daha fazla bir matematik sorusu olduğu için üzgünüz).
Düzeltme: İşte bazı kodlar Python kullanarak simüle etmek zorundayım. Sayısal cevaplar alıyorum, ancak bunu bir formüle genellemek ve açıklamakta sorun yaşıyorum.
import random
import pdb
N = 5
M = 8
NUM_ITER = 100000
def get_collisions(table):
col = 0
for item in table:
if item > 1:
col += (item-1)
return col
def run():
table = [0 for x in range(M)]
for i in range(N):
table[int(random.random() * M)] += 1
#print table
return get_collisions(table)
# Main
total = 0
for i in range(NUM_ITER):
total += run()
print float(total)/NUM_ITER
"Üçlü" çarpışmalarını nasıl ölçmek istersiniz? – wildplasser
Her ne pahasına olursa olsun sanırım. Böylece iki çarpışma olarak sayıyorum (ilk öğeden sonra yeni eleman başına bir tane eklenir) – numegil
En iyi ölçü, tüm öğeleri almak için işin miktarı olarak görünür, yani SUM (x * (x + 1)/2) 'X ile bir kovadaki öğelerin sayısı ve toplamı tüm kovaların üzerindedir. Bir kaynağa başvurmak için – wildplasser