On 30.09.2014 11:27, bartekltg wrote:
>
> T[L] = 1+sum(i=1,L-1) ro(i,L) [T[i] (i)/L + T[L-i]*(L-i)/L]


Zupełnie już na boku, asymptotycznie to zawsze będzie logarytm.
Przynajmniej jeśli rozkład, z którego
losujemy nie zmienia się, a jedynie go skalujemy.

Wszystkie równania na oczekiwany czas sprowadzają się do postaci

T[L] = \sum_{j=1}^{L-1} w_L[j] T[j] /(L-1)

gdzie wagi (dla każdego L oczywiście inny zestaw)
sumują się do 1. I to jest najistotniejsze tu założenie.
Tak jest w obu przypadkach z poprzednich postów.


W przypadku asymptotycznym sumę zastępujemy całką i mamy

T[L] = 1/L int_0^L w(x/L) T[x] dx
w to waga, zdefiniowana na [0,1]

x=L*y


T[L] = int_0^L w(y) T[y*L] dy

podstawiając za rozwiązanie T[.]=log[.]+C1

int_0^L w(y) (log[y*L] + C1) dy =

int_0^L w(y) log[L] dy + int_0^L w(y) log[y] dy + C2 =
log[L] + C1+C2

No to w domu, bo stałą możemy tak dobrać, by C0 == C1[C0] + C2


pzdr
bartekltg