algorithm - 上限のより良い推測

Question

《アルゴリズム入門》から出題された問題で、その数は 4.4-5 で、次のように記述されています。

再帰ツリーを使用して、再帰 T(n) = T(n-1) + T(n/2) + n の適切な漸近上限を決定します。代入法を使用して、答えを検証します。

再帰ツリーの再帰を計算するのは難しいことがわかりました。私が出した答え

Math.pow(2,n)

緩すぎるようです.たぶん、より良い推測が存在します.助けてくれてありがとう.

Answer 1

私が間違いを犯さなかったことを願っています:)

しましょうA(n)=T(n/2)+n

0. T(n)=T(n-1)+A(n)=T(n-2)+A(n-1)+A(n)=...=A(1)+A(2)+...+A(n)
   T(n)=sum[1..n]A(n)
   T(n)=sum[i=1..n]T(i/2)+sum[i=1..n]i

を偶数のn/2整数除算と仮定すると、最初の合計は 2 つの等しい半分で構成されます。T(n/2)=T((n+1)/2)nT(1)+T(1)+T(2)+T(2)+...

1. T(n)=2*sum[1..n/2]T(i)+n*(n-1)/2

以来T(n)<=T(m) for every n<=m

2. T(n)<=n*T(n/2)+n*(n-1)/2

以来T(n/2)>=n/2>=(n-1)/2

3. T(n)<=n*T(n/2)+n*T(n/2)=2*n*T(n/2)

は単調なn=2^kので、のみについて考えてみましょう:Tn=2^kU(k)=T(2^k)

4. U(k)<=2*(2^k)*U(k-1)=2^(k+1)*U(k-1)

させてL(k)=log2 U(k)

5. L(k)<=k+1+L(k-1)

step0 と step1 の間で行ったように

6. L(k)<=k*(k-1)/2+k=k*k/2-k/2+k<=k*k

7. U(k)=2^L(k)<=2^squared(k)

8. T(n)=U(log2 n)<=2^squared(log2 n)

Answer 2

再帰関係は、サブ指数関数的で超線形の計算時間を生じさせるように思われます。これは、十分な大きさの が与えられた場合、選択された任意のベースが上限として機能することを意味しますn。

あなたの選択2^nは良い答えであり、おそらく彼らが本で探していたものです. これは、 の値が非常に小さい場合でも有効な単純なソリューションですn。(それでも、T(n)適度に大きなn.

与えられT(1) = 1た (または他の定数) 再帰方程式は、 の最初のいくつかの値について、次のように実行時間を与えますn。

T(1) = 1          n^1 = 2
T(2) = 4          n^2 = 4
T(3) = 11         n^3 = 8
T(4) = 19         n^4 = 16
T(5) = 35         n^5 = 32
T(6) = 52         n^6 = 64
T(7) = 78         n^7 = 128
T(8) = 105        n^8 = 256
T(9) = 149        n^9 = 512

2^n上限としての選択は、すべての値以上に対して有効であることがわかりT(6)ます。

より低い境界が必要な2^n場合は、より低いベースを選択できます (より高い数の場合にのみ有効になるというトレードオフがありますn)。しかし、それは基本的にあなたがすでに持っているものと同じソリューションになることを付け加えなければなりません.

底が 1 よりも大きい場合は何でも構いませんが、もう少し具体的に言うと、たとえば、再帰方程式T(n) = T(n-1) + T(n/2) + nが の方程式によって制限されているT(n) = T(n-1) + T(n-2)ことがわかりn>5ます。

これは、フィボナッチ数列と同じ再帰関係であり、この(1+sqrt(5))/2 = 1,618質問への回答の手順に従うと、黄金比の のべき乗に一致する計算の複雑さが生じnます。

nの値がT(n)によって制限されていることがわかる実際の値をプロットします((1+sqrt(5))/2)^n。図からは値n=13以上のようです。

以上のことから、サブ指数関数を使用して実行時間を概算することについて少し考えてみました。簡単にできるようには見えませんが、私が言ったように、あなたは期待通りの答えを見つけたと思います。