5

Cormen の Introduction to Algorithm の本で、私は次の問題に取り組もうとしています。

再帰関係 T(n) = T(n-1) + n の解が O(n2 ) であることを代入を使って示せ

(与えられた初期条件はありませんでした。これは問題の全文です)

しかし、私は正しいプロセスを見つけることができないようです。教科書では簡単に触れているだけで、私が検索したほとんどのサイトは、私がすでにその方法を知っていると想定しているようです。誰かが簡単なステップバイステップのガイド、またはそのガイドへのリンクを教えてくれれば幸いです。

キックのために、これまでの私の試みは次のとおりです。

T(n) <= c(n^2)
       <= c(n-1)^2 + n
       <= c(n^2 -2n +1) + n (これは < c( ではないと確信しています) n^2))

再度、感謝します。

更新：混乱を避けるために、私が達成しようとしている方法の例を次に示します。

解が O(nlog(n))
T(n) = 2T([n/2]) + n
であることを証明してください定数 c > 0. この境界がすべての正の m < n に対して成り立つと仮定します。ここで、m = [n/2] であり、T([n/2]) <= c[n/2]*lg([n/2] が得られます。 ）。これを繰り返しに代入すると、次のようになります:
T(n) <= 2(c[n/2]*lg([n/2])) + n
       <= cn*lg(n/2) + n
       = cn* lg(n) - cn*lg(2) + n
       = cn*lg(n) - cn + n
       <= cn*lg(n)
ここで、c >= 1 である限り最後のステップが保持されます

。問題はありませんが、上記の問題の手順を繰り返そうとすると行き詰まります。

4

2 に答える 2

13

私はこれが誘導であることになっていると思いますか？

したがって、基本ケース n=1 は自明です。誘導の場合、n>1 と仮定します。(*) T(n-1) を O((n-1) 2 )=O(n 2 ) とする。T(n) も O(n 2 ) であることを示します。

 T(n) = T(n-1) + n
      < c (n-1)^2 + n,  assume c>1 wlog
      < c n^2 - 2cn + c + n
      < c n^2 - (2c - 1)n + c
      < c n^2

n > 1、c > 1 の場合。

ここにブレイクアウトがあります：

最初に、c > 1、2c - 1 > c の場合、次のようになることに注意してください。

      < c n^2 - (2c - 1)n + c
      < c n^2 - (c)n + c

次に、n > 1 の場合、-(c)n+c = (1-n) c < 0 なので、

      < c n^2 - (c)n + c
      < c n^2

T(n) < cn^2 となる定数 c があるため、明らかに T(n) は O(n 2 ) です。

それは大まかにあなたが望むものに沿っていますか？エッジケースを修正するために、何度も編集する必要がありました。

于 2013-01-28T22:03:13.400 に答える
10

それは純粋な数学の問題ですか？

T(n) = T(n-1) + n から、次のようになります。

T(n)   - T(n-1) = n
T(n-1) - T(n-2) = n-1
T(n-2) - T(n-3) = n-2
...
...
T(2)   - T(1)   = 2
T(1)   - T(0)   = 1

上記の方程式をすべて合計すると、次のようになります。

T(n) - T(0) = 1 + 2 + ... + (n-1) + n = n * (n+1) / 2 = O(n ^ 2)

終わったね。

更新（OPが必要なため、これが置換と呼ばれるかどうかはわかりません）：

T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
= ... 
= T(1) + (2 + 3 + ... + n)
= T(0) + (1 + 2 + ... + n)
= T(0) +  n * (n+1) / 2
= O(n ^ 2)
于 2013-01-26T03:00:37.280 に答える