1

再帰関係によって与えられた実行時間を決定しようとしましたが、私の結果は正しくありません。

再発

T(n) = c + T(n-1) if n >= 1
     = d          if n = 0

私の試み

この再帰ツリーを構築しました：

                   n
                   |
                  n-1
                   |
                  n-2
                   |
                  n-3
                   |
                  n-4
                   |
                  n-5
                   |
                   |
                   |
                   |
                   |
                   |
                Till we get 1

レベルiでは、サブ問題のサイズは、n-i

しかし、最終的にはサイズ 1 の問題が必要です。したがって、最後のレベル n-i=1では、i=n-1.

そのため、木の深さは になりn-1、高さは になりn-1+1= nます。

この再帰を解くのに必要な時間 = ツリーの高さ * 各レベルで必要な時間:

n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+ ...
==> (n+n+n+n+n+ ... )-(1+2+3+4+5+ ... )
==> n - (n(n+1)/2)

ここで、所要時間 = n* ((n-n2)/2) は n 2になる順序を与えるはずですが、それは正しい答えではありません。

4

3 に答える 3

3

レベル i では、サブ問題のサイズは ni

はい、そうです。しかし、実行時間がすべての副問題のサイズの合計に等しいと仮定しています。考えてみてください。すでに最初の 2 つのレベルを合計すると が得られますがn + (n - 1) = 2n - 1、なぜ問題のサイズが大きくなるのでしょうか? 免責事項: 少しわがままで、完全に正確な記述ではありません。

式が実際に言っていること

T(n) = c + T(n-1)

式は、一部の問題を解くには、問題のサイズが 1 小さい問題を解くのに必要な時間と、追加の定数を加えnたものと同じ時間がかかることを示しています。cc + T(n - 1)

上記のステートメントを別の言い方をすると、次のようになります。問題がt特定の問題サイズに時間がかかるとするとt + c、1 だけ大きい問題サイズに時間がかかります。

n = 0問題サイズが の場合、これには時間がかかることがわかっていdます。2 番目のステートメントによると、サイズがもう 1 の場合n = 1、 がかかりd + cます。d + c + cルールをもう一度適用すると、 がかかりますn = 2。結論として、それにはd + n*c時間がかかるに違いありませんn。

これは証明ではありません。これを実際に証明するには、amit で示されている帰納法を使用する必要があります。

正しい再帰ツリー

再帰ツリーには、問題のサイズのみがリストされています。それはほとんど役に立たないです、私は恐れています。代わりに、上記の問題サイズのランタイムをリストする必要があります。

ツリー内のすべてのノードは、特定の問題のサイズに対応しています。そのノードに書き込むのは、問題のサイズにかかる追加の時間です。つまり、ノードのすべての子孫とノード自体を合計して、特定の問題サイズのランタイムを取得します。

このようなツリーをグラフィカルに表現すると、次のようになります。

Tree        Corresponding problem size
c                                    n
|
c                                    n - 1
|
c                                    n - 2
|
c                                    n - 3
.
.
.
|
c                                    2
|
c                                    1
|
d                                    0

形式化:既に述べたように、ノードのラベルは、その問題のサイズとそのすべての子孫を解決するために必要な追加のランタイムです。一番上のノードは の問題サイズを表し、に加えて、 を使用して接続されているためn、ラベルが付いています。cT(n-1)|

数式では、次の関係のみを記述します: T(n) = c + T(n-1). そのツリーを考えると、これがすべての にどのように適用されるかがわかりますn>=1。これを次のように書き留めることができます。

T(n)     = c + T(n - 1) # This means, `c` plus the previous level
T(n - 1) = c + T(n - 2) # i.e. add the runtime of this one to the one above^
T(n - 2) = c + T(n - 3)
...
T(n - (n - 2)) = c + T(1)
T(n - (n - 1)) = c + T(0)
T(0) = d

用語を下から上に展開できるようになりました。

T(n - (n - 1)) = c + T(0)
T(0) = d

T(n - (n - 2)) = c + T(1)
T(n - (n - 1)) = c + d
T(0) = d

T(n - (n - 3)) = c + T(2)
T(n - (n - 2)) = c + (c + d)
T(n - (n - 1)) = c + d
T(0) = d

T(n - (n - 4)) = c + T(3)
T(n - (n - 3)) = c + (2*c + d)
T(n - (n - 2)) = c + (c + d)

...

T(n) = c + T(n - 1)
T(n - 1) = c + ((n-2)c + d)

T(n) = c + (n-1)c + d = n*c + d
T(n - 1) = (n-1)c + d

サミング1 to n

n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+ ...
==> (n+n+n+n+n+ ... )-(1+2+3+4+5+ ... )
==> n - (n(n+1)/2)

1 行目から 2 行目まで、問題を summing から summing に減らし1 to nまし1 to n-1た。同じ問題で立ち往生しているため、これはあまり役に立ちません。

3 行目で何をしたかはわかりませんが、1 行目から 2 行目への移行は基本的に正しいです。

これは正しい式でした。

1 を n に合計するガウスのトリック

于 2012-10-07T12:12:45.020 に答える
2 
T(n) = c + T(n-1) 
     = c + (c + T(n-2)) 
     = ... 
     = c*i + T(n-i) 
     = ...
     = c*n + T(0)
     = c*n + d

c、dが定数であると仮定すると、それが得られますO(n)

数学的に証明するには、数学的帰納法を使用できます

それぞれについて、Base がであるk < nと仮定します。これは n < 1 の場合に正しいですT(n) = c*n + d
T(0) = 0*n + d = d

T(n) = c + T(n-1)               (*)
     = c + (n-1)*c + d 
     = c*n + d

(*) は帰納仮説であり、n-1 < n であるため有効です。

于 2012-10-07T10:31:44.713 に答える
1

複雑さは O(n) になります。

あなたが説明したように、関数は定数演算「c」を使用して、入力 n の問題を (n-1) の問題に変換します。

したがって、再帰ツリーを下に移動すると、合計 n レベルになり、各ステップで一定の操作 'c' が必要になります。

そのため、合計 c*n 操作があり、結果として複雑さ O(n) になります。

于 2012-10-07T11:51:23.247 に答える