Hej.
Dana jest tablica n elementów. Każdy element ma przypisaną jakąś wartość prawdopodobieństwa.
Potrzebuję wydajnego algorytmu wyboru losowego elementu zgodnie z tak określonym rozkladem prawdopodobieństa. Uwaga - pomiędzy losowaniami pewna niewielka liczba elementów (<< n) może zmienić drastycznie wartości swoich prawdopodobieństw. Algorytm powinien mieć jak najniższą złożoność zarówno losowania elementu, jak i aktualizacji stanu swoich struktur w przypadku zmiany żądanego prawdopodobieństwa wylosowania niektórych elementów. Jako złozoność algorytmu przyjmuje się złożoność "gorszej" z tych operacji.
Klasyczny algorytm z konstruowaniem dystrybuanty w tablicy ma złożoność O(n), ze wzgledu na złożoność operacji tworzenia dystrybuanty, mimo że samo losowanie da się zrobić w O(log n). Myślałem o czymś z drzewami, co powinno dać ostatecznie O(log n), ale implementacja nie mieści się w 10 linijkach, a nie mam duzo czasu, ani wysokiego priorytetu na ten algorytm. Zresztą w ostateczności O(n) ujdzie.
Czy istnieje jakiś prosty algorytm o lepszej złożoności, najlepiej wykorzystujący gotowe struktury danych dostępne w Javie? A może jest gdzieś gotowa biblioteka rozwiazująca ten problem?