сложность вычисления биномиального коэффициента

[Батороев]

А мне вот интересно, можно ли делать как-то так:
Возвести в степень число $1000...0001$, а затем собирать биномиальные коэффициенты в различных разрядах?

Например, при $n=10$:
$1001^{10}= 1,010,045,120,210,252,210,120,045,010,001$ (запятые ввел для удобства).

[maxal]

Батороев в сообщении #292687 писал(а):

А мне вот интересно, можно ли делать как-то так:
Возвести в степень число $1000...0001$, а затем собирать биномиальные коэффициенты в различных разрядах?

Сделать-то можно (причем лучше работать с двоичной системой счисления), вот только будет ли от этого прок. Прикинуть сложность можно так:
Для простоты оценим биномиальные коэффициенты $\binom{n}{k}$ величиной $2^n$. Тогда число которое нам нужно возводить в степень $n$ нужно брать равным $2^n+1$. Сложность его возведения в степень $n$ можно оценить сложностью $O(\log n)$ умножений $n^2$-битных чисел, что суммарно дает сложность $O(n^2\log^2 n)$, что хуже чем у метода, основанного на рекуррентной формуле.

[Профессор Снэйп]

Всё-таки я так и не понял из этого обсуждения, какой наиболее быстрый алгоритм вычисления $\binom{n}{k}$ при неограниченной памяти.

-- Сб фев 27, 2010 00:17:31 --

Умножение $n \cdot k$, по видимому, следует трактовать как $\log_2 k$ сложений чисел длины $\log_2 k + \log_2 n$. Сложение же чисел $n + k$ требует $O(\max\{ \log_2 n, \log_2 k \})$ времени.

[maxal]

Профессор Снэйп в сообщении #292744 писал(а):

Всё-таки я так и не понял из этого обсуждения, какой наиболее быстрый алгоритм вычисления $\binom{n}{k}$ при неограниченной памяти.

Зависит от соотношения $n$ и $k$.

Профессор Снэйп в сообщении #292744 писал(а):

Умножение $n \cdot k$, по видимому, следует трактовать как $\log_2 k$ сложений чисел длины $\log_2 k + \log_2 n$.

Мы считали $n$ и $k$ "одноячеечными" числами (например, $<2^{31}$ на 32-битной архитектуре), для практических применений вряд ли нужны большие. А для таких чисел, умножение и сложение можно считать атомарными операциями, требующими константное время.

[Профессор Снэйп]

Кстати, а сколько тактов работы процессора занимают сложение и умножение? Или я отстал от жизни и сейчас всё это уже не в тактах меряется?

[venco]

Единицы тактов. Однозначно сказать нельзя, т.к. исполнение инструкций может перекрываться.
Из арифметических операций только деление осталось медленным.