algorithm - 递归关系与 n 成反比

Question

我最近学会了通过矩阵求幂找出第 n 个斐波那契数列。但我被困在两个关系上：

1) F(n) = F(n−1) + n            
2) F(n) = F(n−1) + 1/n    

有没有像我们有矩阵博览会一样在 O(logn) 时间内解决这些问题的有效方法。斐波那契数列？

Answer 1

第一个显然等于：

F(n) = F(0) + n*(n+1)/2

并且可以在 O(1) 时间内计算出来。第二个，看这里。

---

假设你想用矩阵求幂来计算第一个，就像你对斐波那契数列所做的那样，这里是你应该使用的矩阵：

    | 1 1 0 |
A = | 0 1 1 |
    | 0 0 1 |

如果您考虑以下等式，则矩阵的选择是显而易见的：

| F(n+1) |   | 1 1 0 |   | F(n) |
|  n+1   | = | 0 1 1 | * |  n   |
|   1    |   | 0 0 1 |   |  1   |

当然，起始向量必须是：(F(0), 0, 1)。

对于第二个系列，这并不容易，因为您希望逐渐计算 value 1/n，而不能以这种方式线性计算。我想这是做不到的，但我不会试图证明这一点。

Answer 2

第一个可以计算出来，O(1)因为这是一个算术级数，总和是n*(n-1)/2。

第二个是谐波级数，无法有效计算，但您可以将其近似为O(1)：

其中第一个是0.57721566490153286060，第二个是大约1/(2k)