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

· Биномиальные коэффициенты могут быть вычислены с помощью формулы , если на каждом шаге хранить значения при . Этот алгоритм особенно эффективен, если нужно получить все значения при фиксированном n. Алгоритм требует O(n) памяти (O(n²) при вычислении всей таблицы биномиальных коэффициентов) и O(n²) времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

· Второй способ основан на тождестве . Он позволяет вычислить значения при фиксированном k. Алгоритм требует O(1) памяти (O(l) если нужно посчитать l последовательных коэффициентов с фиксированным k) и O(k) времени.