Simplifica la complejidad de n multichoose k

Tengo un algoritmo recursivo con una complejidad temporal equivalente a elegir k elementos de n con repetición, y me preguntaba si podría obtener una expresión big-O más simplificada. En mi caso, puede ser mayor que crecen independientemente. $k$ $n$

Específicamente, esperaría alguna expresión exponencial explícita. Lo mejor que pude encontrar hasta ahora es que, según la aproximación de Stirling , puedo usar eso, pero me preguntaba si podría obtener algo mejor. $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
fuente

Esto no es exactamente muy útil, pero es muy interesante la aproximación factorial de Ramanujan

Pratik Deoghare

Gracias

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}}$ miradas como una aproximación genial, pero de hecho no parece ayudar a simplificar esto.

yoniLavi

Respuestas:

Editar: Esta respuesta es para $k<n$ . Sin limitar $k$ en términos de $n$ la expresión no tiene límites.

Si entonces su expresión se convierte en . Observe que según la fórmula de Stirling para cualquier donde es la entropía binaria. En particular . Por lo tanto, tenemos para $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).$

Dado que el límite superior es el peor de los casos (lo dejo como un ejercicio para mostrar esto), su expresión es . $k=n-1$ $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$

A.Schulz
fuente

Gracias, exactamente lo que estaba buscando! Y es otra cosa que me motiva a estudiar teoría de la información.

yoniLavi

@ Falcor84: tuve un error tipográfico más pequeño en la última transición. La parte de la raíz cuadrada tiene que ir al denominador. Por lo tanto, el límite es ligeramente mejor que el presentado por Paresh. (En realidad, el límite es asintóticamente apretado.)

A.Schulz

Yo también debería haber notado ese pequeño signo menos, gracias de nuevo.

yoniLavi

Su afirmación de "izquierda como ejercicio" de que es el peor de los casos está mal Si , la expresión es . Esto no siempre es menor que .

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

Desde , el problema es simétrico en y (que puede crecer sin relación en mi caso ) Por lo tanto, supongo, la respuesta más precisa sería reemplazar n en la parte final de la respuesta con

(\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 dice que Sondow (2005) [1] y Sondow y Zudilin (2006) [2] notaron la desigualdad: para un número entero positivo y un número real.

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

Entonces podemos usar con y .

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

Luego tenemos

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

Ahora, la expresión binomial tiene el valor más alto en el medio del triángulo de Pascal. Entonces, en nuestro caso, o en . $n+k = 2k$ $k = n$

Sustituyendo eso en la desigualdad anterior, obtenemos: .

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

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

Por lo tanto, un límite más estricto es .

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

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

También puede ver que el límite inferior para el valor máximo es

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

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

Referencias:
[1] Sondow, J. "Problema 11132." Amer Matemáticas. Mensual 112, 180, 2005.
[2] Sondow, J. y Zudilin, W. "Euler constante, q-logaritmos y fórmulas de Ramanujan y Gosper" Ramanujan J. 12, 225-244, 2006.

Paresh
fuente