Сложность нахождения биномиального коэффициента, равного числу

Предположим, вы получаете число $m$ (используя $O(\log m)$ бит в двоичном кодировании).

Как быстро вы можете найти (или определить, что такое не существует) ?

Например, учитывая вход , можно вывести .$m=8436285$$n=27, k=10$

Наивный алгоритм для задачи будет проходить по всем возможным значениям для и искать значение которое удовлетворяет свойству.$n$$k$

Простое наблюдение состоит в том, что нет необходимости проверять значения меньшие, чем или больше, чем . Однако (даже если бы мы могли проверять только возможных значений на значение ), это приводит к неэффективному алгоритму, который экспоненциально влияет на размер входных данных.$n$$\log m$$O(\sqrt m)$$O(1)$$k$$n$

Альтернативный подход заключается в том, чтобы просмотреть возможные значения (достаточно проверить ) и при каждой проверке на возможные значений. Затем мы можем использовать: $k$$\{2,3,\ldots,2\log m\}$$n$

Таким образом, для данного нам нужно проверить только значений в диапазоне , Делая это с помощью бинарного поиска (когда фиксировано, монотонно возрастает по ), это дает полиномиальный алгоритм, работающий в .$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)$

Это все еще кажется мне неэффективным, и я думаю, что это может быть решено за линейное время (в размере ввода).

Это не правда, что . Например, .$(n-k)^k<{n\choose k}$${9\choose 2} = 36 < 49 = (9-2)^2$

Я (пока) не нашел тонкого решения с использованием арифметических свойств биномиальных коэффициентов, однако могу предложить несколько грубых, если это поможет :-)

Для каждого вы можете решить для , взяв начальное предположение (скажем, ) и используя аналитический метод, такой как Ньютон-Рафсон. Вы хотите решить . Производная левой части по имеет вид где - функция дигаммы, которую легко вычислить ,$k$$n$$\sqrt[k]{k!\cdot m}$${n\choose k} - m = 0$$n$$(\psi(n+1)-\psi(n-k+1)){n\choose k}$$\psi$

Сложность поиска Ньютона-Рафсона зависит только от сложности вычисления функции и ее производной, а также от количества цифр, необходимых для решения (в нашем случае нам просто нужно ближайшее целое число).

Таким образом, в целом для каждого поиск должен быть (при условии, что, как вы, кажется, и сделали, вычисление биномиального коэффициента занимает постоянное время), следовательно, общая сложность алгоритма, использующего ваши оценки для , будет .$k$$O(1)$$k$$O(\log(m))$