Sederhanakan kompleksitas multichoose k

Saya memiliki algoritma rekursif dengan kompleksitas waktu yang setara dengan memilih elemen k dari n dengan pengulangan, dan saya bertanya-tanya apakah saya bisa mendapatkan ekspresi O-besar yang lebih sederhana. Dalam kasus saya, $k$ mungkin lebih besar dari $n$ dan mereka tumbuh secara mandiri.

Secara khusus, saya mengharapkan beberapa ekspresi eksponensial eksplisit. Yang terbaik yang bisa saya temukan sejauh ini adalah berdasarkan perkiraan Stirling $O(n!) \approx O((n/2)^n)$ , jadi saya bisa menggunakannya, tetapi saya bertanya-tanya apakah saya bisa mendapatkan sesuatu yang lebih baik.

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

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

asymptotics combinatorics runtime-analysis yoniLavi
sumber

Ini tidak persis sangat membantu tetapi sangat menarik perkiraan faktorial Ramanujan

Pratik Deoghare

Terima kasih,

terlihat seperti pendekatan yang keren, tetapi memang sepertinya tidak membantu menyederhanakan ini.

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}}$

yoniLavi

Jawaban:

Sunting: Jawaban ini untuk . Tanpa membatasi dalam hal ekspresi tidak dibatasi. $k<n$ $k$ $n$

Jika maka ekspresi Anda menjadi $k=n-1$ . Perhatikan bahwa dengan rumus Stirling untuk $O\left ({{2(n-1)}\choose{n-1}}\right)$ $0<\alpha<1$ di manaadalah entropi biner. Khususnya. Karenanya kita memiliki untuk

(\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$

HAI ((\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).$

Karena batas atas adalah kasus terburuk (saya biarkan sebagai latihan untuk menunjukkan ini), ekspresi Anda adalah $k=n-1$ . $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$

A.Schulz
sumber

Terima kasih, persis apa yang saya cari! dan itu adalah hal lain yang memotivasi saya untuk mempelajari teori informasi.

yoniLavi

@ Falcor84: Saya mendapat kesalahan ketik yang lebih kecil pada transisi terakhir. Bagian akar kuadrat harus pergi ke penyebut. Karenanya ikatannya sedikit lebih baik daripada yang ditunjukkan oleh Paresh. (Sebenarnya,

ikatannya

Aku juga seharusnya memperhatikan tanda minus kecil itu, terima kasih lagi.

yoniLavi

Pernyataan "kiri sebagai latihan" Anda bahwa

adalah kasus terburuk adalah salah. Jika

, ekspresinya adalah

k = n - 1

$k = n-1$

n = 3

$n=3$

. Ini tidak selalu kurang dari

(\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

Sejak

, masalahnya simetris dalam

dan

(yang dapat tumbuh tanpa hubungan dalam kasus saya). Oleh karena itu, saya kira, jawaban yang lebih akurat adalah mengganti n pada bagian akhir dari jawaban dengan

(\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 berkata Sondow (2005) [1] dan Sondow dan Zudilin (2006) [2] mencatat ketidaksetaraan:

\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$

(\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$

(\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}$

$n+k = 2k$ $k = n$

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

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

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

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

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

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

Referensi:
[1] Sondow, J. "Masalah 11132." Amer. Matematika Bulanan 112, 180, 2005.
[2] Sondow, J. dan Zudilin, W. "Konstanta, q-logaritma Euler, dan formula Ramanujan dan Gosper" Ramanujan J. 12, 225-244, 2006.

Paresh
sumber