Complexité de la recherche d'un coefficient binomial égal à un nombre

Supposons que vous obtenez un nombre (en utilisant bits dans le codage binaire). $m$ $O(\log m)$

À quelle vitesse pouvez-vous trouver (ou déterminer qu'il n'existe pas)

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

Par exemple, étant donné l'entrée $m=8436285$ , on peut sortir $n=27, k=10$ .

Un algorithme naïf pour le problème passerait en revue toutes les valeurs possibles de $n$ et rechercherait une valeur de $k$ qui satisfasse la propriété.

Une observation simple est qu'il n'est pas nécessaire de vérifier des valeurs de $n$ inférieures à $\log m$ ou supérieures à $O(\sqrt m)$ . Cependant (même si nous ne pouvions vérifier que valeurs $O(1)$ possibles par valeur ), cela aboutit à un algorithme inefficace qui est exponentiel dans la taille d'entrée. $k$ $n$

Une approche alternative serait de passer en revue les valeurs possibles de $k$ (il suffit de vérifier $\{2,3,\ldots,2\log m\}$ ) et pour chaque vérification des $n$ valeurs possibles . On peut alors utiliser:

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

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

Donc, pour un donné, $k$ il suffit de vérifier $n$ valeurs dans la plage $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$ , en utilisant la recherche binaire (lorsque $k$ est fixe, $n \choose k$ augmente de façon monotone dans $n$ ), cela donne un algorithme polynomial fonctionnant en $O(\log^2m)$ .

Cela me semble toujours inefficace et je suppose que cela pourrait être résolu en temps linéaire (dans la taille d'entrée).

algorithms combinatorics RB
la source

Qu'avez-vous essayé jusqu'à présent? Astuce: Supposons que

n

$n$ été donné. Pourriez-vous résoudre ce problème alors? Quelle est la plage de valeurs possibles pour

n

$n$ ? Ou, supposons que

k

$k$ été donné; pourriez-vous le résoudre dans ce cas? Quelle est la plage de valeurs possibles pour

k

$k$ ?

Réponses:

Il n'est pas vrai que $(n-k)^k<{n\choose k}$ . Par exemple ${9\choose 2} = 36 < 49 = (9-2)^2$ .

Je n'ai pas (encore) trouvé de solution subtile utilisant les propriétés arithmétiques des coefficients binomiaux, mais je peux suggérer une solution quelque peu bruteforce si cela aide :-)

Vous pouvez, pour chaque , résoudre pour en faisant une supposition initiale (par exemple ) et en utilisant une méthode analytique telle que Newton-Raphson. Vous voulez résoudre . La dérivée du côté gauche par rapport à est où est la fonction digamma, qui est facile à calculer . $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 complexité d'une recherche de Newton-Raphson dépend uniquement de la complexité du calcul de la fonction et de sa dérivée, et du nombre de chiffres requis pour la solution (dans notre cas, nous avons juste besoin de l'entier le plus proche).

Donc, globalement, pour chaque la recherche devrait être (en supposant, comme vous semblez l'avoir fait, que le calcul d'un coefficient binomial prend un temps constant), la complexité totale de l'algorithme utilisant vos bornes pour serait donc . $k$ $O(1)$ $k$ $O(\log(m))$

David Durrleman
la source

Bien que je sois d'accord que les limites étaient éteintes (voir modifier, merci pour cela), pouvez-vous expliquer pourquoi la recherche, étant donné que prend ?

k

$k$

O (1)

$O(1)$