Złożoność znalezienia współczynnika dwumianowego równego liczbie

Załóżmy, że otrzymujesz liczbę $m$ (używając $O(\log m)$ bitów w kodowaniu binarnym).

Jak szybko można znaleźć (lub stwierdzić, że takie nie istnieje) ?

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$

Na przykład, biorąc pod uwagę wejście , można wyprowadzić . $m=8436285$ $n=27, k=10$

Naiwny algorytm dla problemu przekroczyłby wszystkie możliwe wartości dla i szukałby wartości która spełnia tę właściwość. $n$ $k$

Prostą obserwacją jest to, że nie trzeba sprawdzać wartości mniejszych niż lub większych niż . Jednak (nawet gdybyśmy mogli sprawdzić tylko możliwe wartości na wartości) to kończy się to nieefektywnym algorytmem, który ma charakter wykładniczy w wielkości wejściowej. $n$ $\log m$ $O(\sqrt m)$ $O(1)$ $k$ $n$

Alternatywnym podejściem byłoby przekroczenie możliwych wartości (wystarczy sprawdzić ) i dla każdego sprawdzenia możliwych wartości. Następnie możemy użyć: $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!}$

Więc dla danego musimy tylko sprawdzić wartości z zakresu , w ten sposób za pomocą przeszukiwanie binarne (gdy jest stałą, jest monotonicznie rosnącą w ), co daje wielomian algorytm działa w . $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)$

Nadal wydaje mi się to nieefektywne i myślę, że można to rozwiązać w czasie liniowym (w wielkości wejściowej).

algorithms combinatorics RB
źródło

Czego spróbowałeś do tej pory? Wskazówka: Załóżmy, że podano również . Czy mógłbyś to rozwiązać? Jaki jest zakres możliwych wartości dla ? Lub załóżmy, że podano ; czy możesz to rozwiązać w takim przypadku? Jaki jest zakres możliwych wartości dla ?

n

$n$

n

$n$

k

$k$

k

$k$

Odpowiedzi:

Nie jest prawdą, że . Na przykład . $(n-k)^k<{n\choose k}$ ${9\choose 2} = 36 < 49 = (9-2)^2$

Nie znalazłem (jeszcze) subtelnego rozwiązania wykorzystującego właściwości arytmetyczne współczynników dwumianowych, jednak mogę zasugerować nieco brutalny, jeśli to pomoże :-)

Możesz dla każdego rozwiązać dla , przyjmując początkowe domysły (powiedz ) i stosując metodę analityczną, taką jak Newton-Raphson. Chcesz rozwiązać . Pochodną lewej strony w odniesieniu do jest gdzie jest funkcją digamma, którą łatwo obliczyć . $k$ $n$ $\sqrt[k]{k!\cdot m}$ ${n\choose k} - m = 0$ $n$ $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ $\psi$

Złożoność wyszukiwania Newtona-Raphsona zależy tylko od złożoności obliczenia funkcji i jej pochodnej oraz liczby cyfr wymaganych do rozwiązania (w naszym przypadku potrzebujemy tylko najbliższej liczby całkowitej).

Tak więc ogólnie dla każdego wyszukiwanie powinno być (zakładając, jak się wydaje, że obliczenie współczynnika dwumianowego zajmuje stały czas), stąd całkowita złożoność algorytmu wykorzystującego twoje granice dla byłaby . $k$ $O(1)$ $k$ $O(\log(m))$

David Durrleman
źródło

Chociaż zgadzam się, że granice były wyłączone (patrz edycja, dzięki za to), czy możesz wyjaśnić, dlaczego wyszukiwanie, biorąc pod uwagę bierze ?

k

$k$

O (1)

$O(1)$