Komplexität der Ermittlung des Binomialkoeffizienten, der einer Zahl entspricht

Angenommen, Sie erhalten eine Zahl $m$ (unter Verwendung von $O(\log m)$ Bits ( log m ) in binärer Codierung).

Wie schnell können Sie finden (oder feststellen, dass es solche nicht gibt) ?

Beispielsweise kann man bei der Eingabe ausgeben .$m=8436285$$n=27, k=10$

Ein naiver Algorithmus für das Problem würde alle möglichen Werte für durchgehen und nach einem Wert von suchen, der die Eigenschaft erfüllt.$n$$k$

Eine einfache Beobachtung ist, dass es nicht notwendig ist, Werte von kleiner als oder größer als zu überprüfen . Dies führt jedoch (selbst wenn wir nur mögliche Werte pro Wert prüfen könnten ) zu einem ineffizienten Algorithmus, der in der Eingangsgröße exponentiell ist.$n$$\log m$$O(\sqrt m)$$O(1)$$k$$n$

Ein alternativer Ansatz wäre, die möglichen Werte von zu überprüfen (es ist ausreichend, zu überprüfen) und bei jeder Überprüfung nach möglichen Werten zu suchen. Wir können dann verwenden: $k$$\{2,3,\ldots,2\log m\}$$n$

Für ein gegebenes wir also nur n Werte im Bereich [\ sqrt [\ leftroot {-2} \ uproot {2} k] {m \ cdot k!}, \ Sqrt [\ leftroot {-2} \ prüfen. Entwurzeln {2} k] {m} \ cdot {k}] , Verwenden Sie dazu die Binärsuche (wenn k festgelegt ist, erhöht sich n \ choose k monoton in n ), um einen Polynomalgorithmus zu erhalten, der in O (\ log ^) ausgeführt wird 2m) .n [ k$k$$n$k ($[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$$k$ nO(log2m$n \choose k$$n$$O(\log^2m)$

Dies scheint mir immer noch ineffizient zu sein und ich vermute, dass dies in linearer Zeit (in der Eingabegröße) gelöst werden könnte.

Es ist nicht wahr, dass . Zum Beispiel .($(n-k)^k<{n\choose k}$${9\choose 2} = 36 < 49 = (9-2)^2$

Ich habe (noch) keine subtile Lösung gefunden, die die arithmetischen Eigenschaften der Binomialkoeffizienten verwendet, aber ich kann eine etwas bruteforce vorschlagen, wenn das hilft :-)

Sie können für jedes nach , indem Sie eine anfängliche Vermutung anstellen (sagen Sie ) und eine analytische Methode wie Newton-Raphson verwenden. Sie möchten lösen . Die Ableitung der linken Seite in Bezug auf ist wobei die Digammafunktion ist, die leicht zu berechnen ist .n k $k$$n$($\sqrt[k]{k!\cdot m}$n(ψ(n+1)-ψ(n-k+1)) (${n\choose k} - m = 0$$n$$(\psi(n+1)-\psi(n-k+1)){n\choose k}$$\psi$

Die Komplexität einer Newton-Raphson-Suche hängt nur von der Komplexität der Berechnung der Funktion und ihrer Ableitung sowie von der Anzahl der für die Lösung erforderlichen Ziffern ab (in unserem Fall benötigen wir nur die nächste Ganzzahl).

Insgesamt sollte die Suche für jedes also (unter der Annahme, dass die Berechnung eines Binomialkoeffizienten eine konstante Zeit in Anspruch nimmt), daher wäre die Gesamtkomplexität für den Algorithmus, der Ihre Grenzen für , .O ( 1 ) k O ( log ( m ) $k$$O(1)$$k$$O(\log(m))$