c++ - 2 つの再帰呼び出しを伴うアルゴリズムの複雑さ

Question

再帰的に2回呼び出されるよりも奇妙なアルゴリズムがあります。これは

int alg(int n)
   loop body = Θ(3n+1)
   alg(n-1);
   alg(n-2)

どういうわけか、このアルゴリズムの複雑さを見つける必要があります。上記の方程式の特性多項式を使用してそれを見つけようとしましたが、結果システムは解決するのが難しすぎるので、他のストレートな方法があるかどうか疑問に思っていました..

Answer 1

複雑さ: alg(n) = Θ(φ^n)φ = 黄金比 =(1 + sqrt(5)) / 2

最初は正式に証明できませんが、夜の仕事で、不足している部分を見つけます-下位項を減算する置換法. 証明の表現が下手ですみません(∵下手な英語)。

---

させてloop body = Θ(3n+1) ≦ tn

仮定する (推測するcφ^n ≦ alg(n) ≦ dφ^n - 2tn)n (n ≧ 4)

考慮してくださいalg(n+1)：

Θ(n) + alg(n) + alg(n-1) ≦ alg(n+1) ≦ Θ(n) + alg(n) + alg(n-1)
    c * φ^n + c * φ^(n-1) ≦ alg(n+1) ≦ tn + dφ^n - 2tn + dφ^(n-1) - 2t(n-1)
              c * φ^(n+1) ≦ alg(n+1) ≦ tn + d * φ^(n+1) - 4tn + 2
              c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 3tn + 2
              c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 2t(n+1) (∵ n ≧ 4)

ですので、正解ですn + 1。数学的帰納法により、すべての に対して正しいことがわかりますn。

それでcφ^n ≦ alg(n) ≦ dφ^n - 2tn、そしてalg(n) = Θ(φ^n)。

Answer 2

johnchen902は正しいです:

alg(n)=Θ(φ^n)どこφ = Golden ratio = (1 + sqrt(5)) / 2

しかし、彼の議論はあまりにも手の込んだものなので、厳密にしましょう。彼の元の議論は不完全だったので、私は私の議論を追加しましたが、今彼は議論を完了しました.

---

loop body = Θ(3n+1)

n引数のループ本体のコストを で表しましょうg(n)。それg(n) ∈ Θ(n)以来Θ(n) = Θ(3n+1)。

さらに、T(n)の合計コストを とalg(n)しn >= 0ます。次に、n >= 2再発があるため

T(n) = T(n-1) + T(n-2) + g(n)

の場合n >= 3、適用される繰り返しをT(n-1)それに挿入できます。

T(n) = 2*T(n-2) + T(n-3) + g(n) + g(n-1)

と についてn > 3は、繰り返しを に適用して続行できT(n-2)ます。nしたがって、 が十分に大きい場合、次のようになります。

T(n) = 3*T(n-3) + 2*T(n-4) + g(n) + g(n-1) + 2*g(n-2)
     = 5*T(n-4) + 3*T(n-5) + g(n) + g(n-1) + 2*g(n-2) + 3*g(n-3)
     ...
                                       k-1
     = F(k)*T(n+1-k) + F(k-1)*T(n-k) +  ∑ F(j)*g(n+1-j)
                                       j=1

                                 n-1
     = F(n)*T(1) + F(n-1)*T(0) +  ∑ F(j)*g(n+1-j)
                                 j=1

フィボナッチ数F(n)[ F(0) = 0, F(1) = F(2) = 1]。

T(0)とT(1)はいくつかの定数なので、最初の部分は明らかにΘ(F(n))です。合計を調査することは残っています。

からg(n) ∈ Θ(n)、調査するだけで済みます

       n-1
A(n) =  ∑ F(j)*(n+1-j)
       j=1

今、

                 n-1
A(n+1) - A(n) =   ∑ F(j) + (((n+1)+1) - ((n+1)-1))*F((n+1)-1)
                 j=1

                n-1
              =  ∑ F(j)  + 2*F(n)
                j=1

              = F(n+1) - 1 + 2*F(n)
              = F(n+2) + F(n) - 1

から始めてA(2) = 2 = F(5) + F(3) - 5、それを合計すると、

A(n) = F(n+3) + F(n+1) - (n+3)

したがって、

c*n <= g(n) <= d*n

見積もり

F(n)*T(1) + F(n-1)*T(0) + c*A(n) <= T(n) <= F(n)*T(1) + F(n-1)*T(0) + d*A(n)

のためにn >= 2。であるため、不等式の左右の部分にF(n+1) <= A(n) < F(n+4)依存するすべての項は、qednΘ(φ^n)

Answer 3

関数の本体には時間がかかりますΘ(n)。関数は 2 回再帰的に呼び出されます。

与えられた関数の複雑さは、

     T(n) = T(n-1) + T(n-2) + cn        -----  1
     T(n-1) = T(n-2) + T(n-3) + c(n-1)  -----  2

1-2 ->   T(n) = 2T(n-1) - T(n-3) + c        -----  3

3 -->    T(n-1) = 2T(n-2) + T(n-4) + c      -----  4

3-4 ->   T(n) = 3T(n-1) - 2T(n-2) - T(n-3) - T(n-4) ----- 5

させてg(n) = 3g(n-1)

そこで、近似することができますT(n) = O(g(n))

g(n) はΘ(3 ⁿ )

T(n) = O(3 ⁿ )の場合