Vereinfachen Sie die Komplexität von n Multichoose k

Ich habe einen rekursiven Algorithmus mit einer zeitlichen Komplexität, die der Auswahl von k Elementen aus n mit Wiederholung entspricht, und ich habe mich gefragt, ob ich einen vereinfachten Big-O-Ausdruck erhalten könnte. In meinem Fall kann $k$ größer als $n$ und sie wachsen unabhängig voneinander.

Insbesondere würde ich einen expliziten Exponentialausdruck erwarten. Das Beste, was ich bisher finden konnte, ist das basierend auf Stirlings Näherung $O(n!) \approx O((n/2)^n)$ , also kann ich das verwenden, aber ich habe mich gefragt, ob ich etwas Schöneres bekommen könnte.

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

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

asymptotics combinatorics runtime-analysis yoniLavi
quelle

Dies ist nicht gerade sehr hilfreich, aber sehr interessant Ramanujans faktorielle Annäherung

Pratik Deoghare

Danke,

sieht nach einer coolen Annäherung aus, scheint aber in der Tat nicht zu helfen, dies zu vereinfachen.

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

Antworten:

Bearbeiten: Diese Antwort ist für . Ohne in Bezug auf begrenzen, ist der Ausdruck unbegrenzt. $k<n$ $k$ $n$

Wenn ist, wird Ihr Ausdruck zu $k=n-1$ . Beachten Sie, dass nach Stirlings Formel für jede $O\left ({{2(n-1)}\choose{n-1}}\right)$ $0<\alpha<1$ wobeiist die binäre Entropie. Insbesondere. Deshalb haben wir für

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

Da die Obergrenze der schlechteste Fall ist (ich lasse es als Übung, um dies zu zeigen), ist Ihr Ausdruck $k=n-1$ . $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$

A.Schulz
quelle

Danke, genau das, wonach ich gesucht habe! und es ist noch eine andere Sache, die mich motiviert, Informationstheorie zu studieren.

YoniLavi

@ Falcor84: Ich hatte im letzten Übergang einen kleineren Tippfehler. Der Quadratwurzelteil muss zum Nenner gehen. Daher ist die Grenze etwas besser als die von Paresh. (Eigentlich ist die Grenze asymptotisch eng.)

A.Schulz

Ich hätte auch dieses kleine Minuszeichen bemerken sollen, nochmals vielen Dank.

YoniLavi

Ihre Aussage "Links als Übung", dass

der schlimmste Fall ist, ist falsch. Wenn

, lautet der Ausdruck

k = n - 1

$k = n-1$

n = 3

$n=3$

. Dies ist nicht immer weniger als

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

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

${{n+k-1}\choose{k}} = {{n+k-1}\choose{n-1}}$ ist das Problem in symmetrisch

n

$n$ and

k

$k$ (which can grow without relation in my case). Therefore, I suppose, the more accurate answer would be to replace n in the final part of the answer with

x := m a x (n, k)

$x := max(n,k)$

yoniLavi

Wolfram says Sondow (2005)[1] and Sondow and Zudilin (2006)[2] noted the inequality:

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

m

$m$ a positive integer and

r \geq 1

$r\ge 1$ a real number.

We can then use

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

r = \frac{n}{k}

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

m = k

$m = k$ .

Then we have

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

Now, the binomial expression has the highest value at the middle of the Pascal's triangle. So, in our case, $n+k = 2k$ or at $k = n$ .

Substituting that in the above inequality, we get:

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

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

Therefore, a tighter bound is

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

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

You can also see that the lower bound for the maximum value is

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

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

References:
[1] Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.
[2] Sondow, J. and Zudilin, W. "Euler’s constant, q-logarithms, and formulas of Ramanujan and Gosper" Ramanujan J. 12, 225-244, 2006.

Paresh
quelle