Uprość złożoność n multichoose k

Mam algorytm rekurencyjny o złożoności czasowej równoważnej do wybierania elementów k z powtórzeniem i zastanawiałem się, czy mogę uzyskać bardziej uproszczone wyrażenie big-O. W moim przypadku może być większe niż i rosną one niezależnie. $k$ $n$

W szczególności oczekiwałbym wyraźnego wyrażenia wykładniczego. Najlepsze, jakie do tej pory mogłem znaleźć, to oparte na przybliżeniu Stirlinga , więc mogę z tego skorzystać, ale zastanawiałem się, czy mogę uzyskać coś ładniejszego. $O(n!) \approx O((n/2)^n)$

O ((\binom{n + k - 1}{k})) = O (?)

$O\left({{n+k-1}\choose{k}}\right) = O(?)$

asymptotics combinatorics runtime-analysis yoniLavi
źródło

Nie jest to do końca bardzo pomocne, ale bardzo interesujące przybliżenie czynnikowe Ramanujana

Pratik Deoghare

Dzięki

n! \sim \sqrt{π} {(\frac{n}{e})}^{n} \sqrt[6]{8 n^{3} + 4 n^{2} + n + \frac{1}{30}}

$n! \sim \sqrt{\pi} \left(\frac{n}{e}\right)^n \sqrt[6]{8n^3 + 4n^2 + n + \frac{1}{30}}$ wygląda jak fajne przybliżenie, ale tak naprawdę nie wydaje się, aby to uprościć.

yoniLavi

Odpowiedzi:

Edycja: Ta odpowiedź dotyczy $k<n$ . Bez ograniczenia $k$ pod względem $n$ wyrażenie jest nieograniczone.

Jeśli wówczas wyrażenie staje się . Zauważ, że według wzoru Stirlinga dla dowolnego gdzie jest entropią binarną. W szczególności . Dlatego mamy dla $k=n-1$ $O\left ({{2(n-1)}\choose{n-1}}\right)$ $0<\alpha<1$

(\binom{m}{α m}) = Θ (m^{- 1 / 2} 2^{H (α) m}),

${m \choose {\alpha m}}= \Theta(m^{-{1/2}} 2^{H(\alpha)m}),$

H (q) = - q \log q - (1 - q) \log (1 - q)

$H(q)=-q \log q - (1-q) \log (1-q)$

H (1 / 2) = 1

$H(1/2)=1$

k = n - 1

$k=n-1$

O ((\binom{2 (n - 1)}{n - 1})) = Θ ((2 n - 2)^{- 1 / 2} 2^{2 n - 2}) = Θ (\frac{4^{n}}{\sqrt{n}}) .

$O\left ({{2(n-1)}\choose{n-1}}\right)=\Theta((2n-2)^{-{1/2}} 2^{2n-2})=\Theta\left(\frac{ 4^{n}}{\sqrt{n}}\right).$

Ponieważ górna granica jest najgorszym przypadkiem (pozostawiam to jako ćwiczenie, aby to pokazać), twoje wyrażenie to . $k=n-1$ $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$

A.Schulz
źródło

Dzięki, dokładnie tego szukałem! i to jest kolejna rzecz motywująca mnie do studiowania teorii informacji.

yoniLavi

@ Falcor84: Miałem mniejszą literówkę w ostatnim przejściu. Część pierwiastka kwadratowego musi przejść do mianownika. Dlatego granica jest nieco lepsza niż ta przedstawiona przez Paresha. (W rzeczywistości granica jest asymptotycznie ciasna.)

A.Schulz,

Ja też powinienem był zauważyć ten mały znak minus, dzięki jeszcze raz.

yoniLavi

Twoje stwierdzenie „pozostawione jako ćwiczenie”, że jest najgorszym przypadkiem, jest błędne. Jeśli , wyrażenie to . Nie zawsze jest to mniej niż .

k = n - 1

$k = n-1$

n = 3

$n=3$

(\binom{k + 2}{k}) = (\binom{k + 2}{2}) = \frac{(k + 1) (k + 2)}{2}

${k+2 \choose k} = {k+2 \choose 2} = \frac{(k+1)(k+2)}{2}$

(\binom{4}{2}) = 6

${4 \choose 2} = 6$

Peter Shor,

Ponieważ , problemem jest symetryczne i (który może rosnąć bez związku z moim przypadku ). Dlatego przypuszczam, że dokładniejszą odpowiedzią byłoby zastąpienie n w końcowej części odpowiedzi

(\binom{n + k - 1}{k}) = (\binom{n + k - 1}{n - 1})

${{n+k-1}\choose{k}} = {{n+k-1}\choose{n-1}}$

n

$n$

k

$k$

x := m a x (n, k)

$x := max(n,k)$

yoniLavi

Wolfram mówi Sondow (2005) [1], a Sondow i Zudilin (2006) [2] zauważyli nierówność: dla dodatnia liczba całkowita i liczba rzeczywista.

\frac{1}{4 r m} {[\frac{(r + 1)^{r + 1}}{r^{r}}]}^{m} < (\binom{(r + 1) m}{m}) < {[\frac{(r + 1)^{r + 1}}{r^{r}}]}^{m}

$\frac{1}{4rm}\left[\frac{(r+1)^{r+1}}{r^r}\right]^m < {(r+1)m \choose m} < \left[\frac{(r+1)^{r+1}}{r^r}\right]^m$

m

$m$

r \geq 1

$r\ge 1$

Następnie możemy użyć z i .

(\binom{n + k - 1}{k}) < (\binom{n + k}{k}) = (\binom{(r + 1) m}{m})

${n+k-1\choose k} < {n+k\choose k} = {(r + 1)m \choose m}$

r = \frac{n}{k}

$r = \frac{n}{k}$

m = k

$m = k$

Następnie mamy

(\binom{n + k - 1}{k}) < {[\frac{(r + 1)^{r + 1}}{r^{r}}]}^{m} = {(\frac{n + k}{k})}^{n + k}

${n+k-1\choose k} < \left[\frac{(r+1)^{r+1}}{r^r}\right]^m = \left(\frac{n+k}{k}\right)^{n+k}$

Teraz wyrażenie dwumianowe ma najwyższą wartość w środku trójkąta Pascala. W naszym przypadku lub w . $n+k = 2k$ $k = n$

Podstawiając to w powyższej nierówności, otrzymujemy: .

(\binom{n + k - 1}{k}) < 2^{2 n} = 4^{n}

${n+k-1\choose k} < 2^{2n} = 4^n$

Dlatego ściślejsza granica to .

(\binom{n + k - 1}{k}) = O (4^{n})

${n+k-1\choose k} = O(4^n)$

Możesz również zobaczyć, że dolna granica wartości maksymalnej wynosi

(\binom{n + k - 1}{k}) = Ω (\frac{4^{n}}{n})

${n+k-1\choose k} = \Omega\left(\frac{4^n}{n}\right)$

Odniesienia:
[1] Sondow, J. "Problem 11132." Amer. Matematyka Miesięcznie 112, 180, 2005.
[2] Sondow, J. i Zudilin, W. „Stała Eulera, q-logarytmy i wzory Ramanujana i Gospera” Ramanujan J. 12, 225-244, 2006.

Paresh
źródło