geometry - 帕斯卡三角优势

Question

帕斯卡三角形可用于使用以下递归公式计算组合数：-

(n k) = (n-1 k-1) + (n-1 k)

这可以用来代替 (nk) 的形式展开来计算组合的数量。但两者都在 O(n) 时间内执行。使用帕斯卡三角法有什么优点？

Answer 1

主要优势在于您可以在所有时间和(ni ki)地点预先计算。ni < nki <= kO(n^2)

因此，如果您有可能需要查询帕斯卡三角形中的不同值的问题，使用递归公式方法并存储所有子结果将意味着您的预处理时间是O(n^2)，但您的查询是O(1).

另一方面，(n k)在同一应用程序中使用公式意味着O(n)如果您期望的不仅仅是n查询，则每个查询都不如前一种方法。

Answer 2

如果您需要计算 和 的所有值(n k)，帕斯卡三角形非常有吸引力，因为它只涉及每个元素的一个加法。n<=N0<=k<=N

但是，如果您只需要一个 fixed 的值N，那么使用这个其他递归可能是有利的：

(n k) = (n k-1).(n+1-k)/k