当A [i,j] = j*(A [i-1,j + 1] -A [i-1,j])时,找到第i行第一个元素的最有效方法是什么？

Question

当第一行是1,1/2,3/....这是一个支持问题的图像.

是否存在比天真的O(n ^ 2)方法更有效的方法？

我在研究伯努利数时遇到了这个问题,然后又达到了"秋山谷谷算法".

其中一种方法可以是简单地预先计算结果并将它们存储在表格中.由于伯努利数量增长非常快,对于大多数实际目的而言,我们不需要更大的n的伯努利数.考虑伯努利(400) - 它的周围 - (10 ^ 550).

但只是在算法上看它,是否有比O(n ^ 2)更好的方法？

Answer 1

第一个元素形成伯努利数序列。伯努利数的分子和分母分别使用A027641序列和A027642序列找到。这两个序列在​​各自的页面上都有闭合形式的和，可用于计算它们的项。