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

[sng1]

Дано n, k - типа integer (занимает одну ячейку памяти). Надо вычислить $n \choose k$ в двоичном виде. Какой из известных алгоритмов, использующих не более n ячеек памяти, имеет наименьшую сложность?

[maxal]

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

[sng1]

Сам коэффициент - достаточно большой и его двоичная запись занимает (грубо) не более n бит. Ячейкой памяти будем считать 32 или 64 битное слово. Целочисленные операции: сложение, умножение, деление, остаток от деления (все как в 32 или 64 битном процессоре). Можно учитывать чтение и запись в память, и приписать операциям время в тактах, но можно не входить в такие подробности, а сказать, что вычисление требует столько-то операций, или столько-то операций сложения, столько-то умножения. Интересен также тот же самый вопрос, когда n не помещается в ячейку памяти, а занимает m бит.

[sng1]

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

[незваный гость]

sng1 писал(а):

Какой из известных алгоритмов, использующих не более $n$ ячеек памяти, имеет наименьшую сложность?

Вы имеете в виду линейную память? или что у Вас ровно столько памяти, сколько нужно для хранения результата?

${n \choose n/2}$ занимает примерно $n$ бит, но это $n/32$ или $n/64$ ячеек. Соответственно, мы можем хранить несколько промежуточных чисел большой точности.

[sng1]

До получения результата свободно n ячеек, после получения результата не менее 31/32 (или 63/64) исходной памяти свободно.

[maxal]

Скорее всего, сравнение надо производить между следующими двумя рекуррентными формулами (или их комбинациями):

Без потери общности можно считать, что $k\leq \frac{n}{2}$, при необходимости заменяя $k$ на $n-k$.

1) Динамическое программирование - вычисление по рекуррентной формуле:

$${n\choose k} = {n-1\choose k-1} + {n-1\choose k}.$$

Лобовая реализация потребует $O(nk)$ сложений $O(n)$-битных чисел с расходом памяти $O(nk).$

2) Явная формула:

$${n\choose k} = \frac{n(n-1)\dots (n-k+1)}{k(k-1)\dots 1}$$

соответствующая ей рекуррентная формула

$${n\choose k}=\frac{n}{k}{n-1\choose k-1}$$

с начальным условием

$${n-k\choose 0}=1.$$

Лобовая реализация потребует $O(k)$ умножений и столько же делений "длинных" ($O(n)$-битных) чисел на "короткие" (одноячеечные).

Возможно, еще как-то можно использовать свертку Вандермонда:

$${n\choose k} = \sum_{j=0}^k {\lfloor n/2\rfloor\choose j} {\lceil n/2\rceil\choose k-j}$$

[sng1]

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

[незваный гость]

Можно начать с факториалов (google -> fast computation of factorials).

Забавно, но заявленная Вами память слегка превышает $n \log_2 n$. Так что, по сути, Вас устраивают алгорифмы такой сложности по памяти.

[sng1]

Все равно не понял, известен ли хоть один алгоритм вычисления биномиального коэффициента, про который бы было сказано, что он быстрый (по некоторому критерию, например по числу сложений, или умножений в ЦПУ) и использующий память (в битах) не более $n \lceil \log_2(n+1) \rceil$ ?

[sng1]

maxal писал(а):

2) Явная формула:

$${n\choose k} = \frac{n(n-1)\dots (n-k+1)}{k(k-1)\dots 1}$$

соответствующая ей рекурентная формула

$${n\choose k}=\frac{n}{k}{n-1\choose k-1}$$

с начальным условием

$${n-k\choose 0}=1.$$

Лобовая реализация потребует $O(k)$ умножений и столько же делений "длинных" ($O(n)$-битных) чисел на "короткие" (одноячеечные).

Краем уха слышал, что можно умножать длинные числа за O(n). Если это так и если делить можно за O(n), тогда сложность O($n^2$). А сколько надо памяти?

[maxal]

Ну да, умножать длинные $n$-битные числа на короткие числа можно за $O(n)$, и делить за такое же время. Расход памяти здесь будет $O(n)$ - на каждом шаге нужно лишь помнить предыдущий вычисленные результат.

[sng1]

Правильно ли я понимаю, что для модели когда n не влезает в ячейку памяти - оценка сложности та же, а память $O(n \log n)$?

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

maxal в сообщении #124810 писал(а):

Динамическое программирование - вычисление по рекуррентной формуле:

$${n\choose k} = {n-1\choose k-1} + {n-1\choose k}.$$

Лобовая реализация потребует $O(nk)$ сложений $O(n)$-битных чисел с расходом памяти $O(nk).$

По моему, здесь расход памяти $O(n)$, а не $O(nk)$. Ведь в треугольнике Паскаля для вычисления $(i+1)$-ой строки достаточно знать лишь $i$-ую строку, остальные можно забыть.

-- Пт фев 26, 2010 19:29:50 --

Или $O(n^2)$? Надо помнить, в худщем случае $2n$ штук $O(n)$-битных чисел.

-- Пт фев 26, 2010 19:33:49 --

Так, $O(nk)$ ведь "меньше", чем $O(n^2)$ (точнее, одного порядка). Откуда оценка $O(nk)$, что-то я запутался совсем?

[maxal]

maxal в сообщении #292625 писал(а):

По моему, здесь расход памяти $O(n)$, а не $O(nk)$. Ведь в треугольнике Паскаля для вычисления $(i+1)$-ой строки достаточно знать лишь $i$-ую строку, остальные можно забыть.

-- Пт фев 26, 2010 19:29:50 --

Или $O(n^2)$? Надо помнить, в худщем случае $2n$ штук $O(n)$-битных чисел.

-- Пт фев 26, 2010 19:33:49 --

Так, $O(nk)$ ведь "меньше", чем $O(n^2)$ (точнее, одного порядка). Откуда оценка $O(nk)$, что-то я запутался совсем?

Надо помнить лишь $k+1$ штук $O(n)$-битных чисел (нижний индекс меняется от 0 до $k$, большие нам не нужны). Вот и получается $O(nk)$ памяти.