Complexidade de encontrar o coeficiente binomial igual a um número

Suponha que você esteja obtendo um número $m$ (usando $O(\log m)$ bits na codificação binária).

Quão rápido você pode encontrar (ou determinar que isso não 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 exemplo, dada a entrada $m=8436285$ , pode-se produzir $n=27, k=10$ .

Um algoritmo ingênuo para o problema examinaria todos os valores possíveis para $n$ e procuraria um valor de $k$ que satisfaça a propriedade.

Uma observação simples é que não há necessidade de verificar valores $n$ menores que $\log m$ ou maiores que $O(\sqrt m)$ . No entanto (mesmo se pudéssemos verificar apenas $O(1)$ possíveis valores de $k$ por $n$ valor), isso termina em um algoritmo ineficiente que é exponencial no tamanho da entrada.

Uma abordagem alternativa seria revisar os possíveis valores de $k$ (basta verificar $\{2,3,\ldots,2\log m\}$ ) e, para cada verificação, os possíveis $n$ valores. Podemos então usar:

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

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

Portanto, para um determinado $k$ , precisamos apenas verificar $n$ valores no intervalo $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$ , ao fazer isso usando a pesquisa binária (quando $k$ é corrigido, $n \choose k$ está aumentando monotonicamente em $n$ ), isso fornece um algoritmo polinomial em execução em $O(\log^2m)$ .

Isso ainda me parece ineficiente e acho que isso poderia ser resolvido em tempo linear (no tamanho da entrada).

algorithms combinatorics RB
fonte

O que você tentou até agora? Dica: suponha que

n

$n$ foi fornecido. Você poderia resolver isso então? Qual é o intervalo de valores possíveis para

n

$n$ ? Ou, suponha que

k

$k$ foi dado; você poderia resolvê-lo nesse caso? Qual é o intervalo de valores possíveis para

k

$k$ ?

Respostas:

Não é verdade que $(n-k)^k<{n\choose k}$ . Por exemplo ${9\choose 2} = 36 < 49 = (9-2)^2$ .

Ainda não encontrei uma solução sutil usando propriedades aritméticas dos coeficientes binomiais, no entanto, posso sugerir uma força bruta, se isso ajudar :-)

Você pode, para cada , resolver adotando uma estimativa inicial (por exemplo, ) e usando um método analítico como Newton-Raphson. Você deseja resolver . A derivada do lado esquerdo em relação a é que é a função digamma, 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$

A complexidade de uma pesquisa de Newton-Raphson depende apenas da complexidade da computação da função e de sua derivada e do número de dígitos necessários para a solução (no nosso caso, apenas precisamos do número inteiro mais próximo).

Portanto, para cada a pesquisa deve ser (assumindo, como você parece ter feito, que calcular um coeficiente binomial leva tempo constante); portanto, a complexidade total do algoritmo que usa seus limites para seria . $k$ $O(1)$ $k$ $O(\log(m))$

David Durrleman
fonte

Embora eu concorde que os limites estejam desativados (consulte editar, obrigado por isso), você pode explicar por que a pesquisa, dado leva ?

k

$k$

O (1)

$O(1)$