algorithm - recurrence relation dependent inversly on n

Question

I recently learnt to find out nth number fibonacci series by matrix exponentiation. but i am stuck on two relations :

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

Is there any efficient way to solve these in O(logn) time like we have matrix expo. for fibonacci series ?

Answer 1

最初のものは明らかに等しい：

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

O(1) 時間で計算できます。2 つ目については、こちらをご覧ください。

---

フィボナッチ数列で行ったのと同じ方法で、行列累乗を使用して最初のものを計算すると仮定すると、使用する行列は次のとおりです。

    | 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)。

2 番目のシリーズの場合、これはそれほど簡単ではありませ1/nん。この方法では線形に計算できない値 を徐々に計算する必要があるからです。できないとは思いますが、証明しようとはしません。

Answer 2

O(1)最初のものは、これが等差数列であり、合計が であるという理由だけで で計算できますn*(n-1)/2。

2 つ目は調和級数であり、効率的に計算することはできませんが、次のように近似できますO(1)。

ここで、最初のものは0.57721566490153286060で、2 番目のものはおよそ1/(2k)