Complejidad de encontrar coeficiente binomial que es igual a un número

Suponga que está obteniendo un número $m$ (usando bits $O(\log m)$ en codificación binaria).

¿Qué tan rápido puede encontrar (o determinar que tal no existe) ?

n, k \in N, 1 < k \leq \frac{n}{2} : (\binom{n}{k}) = m

$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$

Por ejemplo, dada la entrada , uno puede generar . $m=8436285$ $n=27, k=10$

Un algoritmo ingenuo para el problema revisaría todos los valores posibles para , y buscaría un valor de que satisfaga la propiedad. $n$ $k$

Una observación simple es que no es necesario verificar valores de menores que mayores que . Sin embargo (incluso si pudiéramos verificar solo posibles valores por valor) esto termina en un algoritmo ineficiente que es exponencial en el tamaño de entrada. $n$ $\log m$ $O(\sqrt m)$ $O(1)$ $k$ $n$

Un enfoque alternativo sería repasar los posibles valores de (es suficiente para verificar ) y para cada verificación de posibles valores. Entonces podemos usar: $k$ $\{2,3,\ldots,2\log m\}$ $n$

{(\frac{n}{k})}^{k} < (\binom{n}{k}) < \frac{n^{k}}{k!}

$\left(\frac{n}{k}\right)^k<{n\choose k}< \frac{n^k}{k!}$

Entonces, para una dada solo necesitamos verificar valores en el rango , al hacerlo mediante la búsqueda binaria (cuando es fijo, aumenta monotónicamente en ), esto da un algoritmo polinomial que se ejecuta en . $k$ $n$ $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$ $k$ $n \choose k$ $n$ $O(\log^2m)$

Esto todavía me parece ineficiente y supongo que esto podría resolverse en tiempo lineal (en el tamaño de entrada).

algorithms combinatorics RB
fuente

¿Qué has intentado hasta ahora? Sugerencia: Suponga que

n

$n$ se dio. ¿Podrías resolver esto entonces? ¿Cuál es el rango de valores posibles para

n

$n$ ? O suponga que se le dio

k

$k$ ; ¿podrías resolverlo en ese caso? ¿Cuál es el rango de valores posibles para

k

$k$ ?

Respuestas:

No es cierto que $(n-k)^k<{n\choose k}$ . Por ejemplo, ${9\choose 2} = 36 < 49 = (9-2)^2$ .

No he encontrado (todavía) una solución sutil utilizando las propiedades aritméticas de los coeficientes binomiales, sin embargo, puedo sugerir una fuerza bruta si eso ayuda :-)

Podría, para cada , resolver tomando una conjetura inicial (por ejemplo, ) y utilizando un método analítico como Newton-Raphson. Desea resolver . La derivada del lado izquierdo con respecto a es donde es la función digamma, que es fácil de calcular . $k$ $n$ $\sqrt[k]{k!\cdot m}$ ${n\choose k} - m = 0$ $n$ $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ $\psi$

La complejidad de una búsqueda de Newton-Raphson solo depende de la complejidad de calcular la función y su derivada, y el número de dígitos necesarios para la solución (en nuestro caso solo necesitamos el número entero más cercano).

Entonces, en general, para cada la búsqueda debería ser (suponiendo, como parece haberlo hecho, que calcular un coeficiente binomial toma tiempo constante), por lo tanto, la complejidad total para el algoritmo que usa sus límites para sería . $k$ $O(1)$ $k$ $O(\log(m))$

David Durrleman
fuente

Si bien estoy de acuerdo en que los límites estaban desactivados (ver edición, gracias por eso), ¿puedes explicar por qué la búsqueda, dado que toma ?

k

$k$

O (1)

$O(1)$