1

次の再帰関係にバインドされている大きな O を見つけようとしています。

T(n) = T(n-1) + n^c, where c >= 1 is a constant

そこで、反復を使用してこれを解決することにしました。

T(n) = T(n-1) + n^c
T(n-1) = T(n-2) + (n-1)^c
T(n) = T(n-2) + n^c + (n-1)^c
T(n-2) = T(n-3) + (n-2)^c
T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c
T(n) = T(n-k) + n^c + (n-1)^c + .... + (n-k+1)^c

Suppose k = n-1, then:

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

ただし、これが正しいかどうかはわかりません。さらに、これから Big O を導き出す方法について、いくつかのガイダンスをいただければ幸いです。どうもありがとう！

4

6 に答える 6

3

はい。それで合っています：

T(n) = n c + (n-1) c + (n-2) c + … + 3 c + 2 c + 1、

そしてこの合計は

T(n) = O(n c+1 )。たとえば、Faulhaber の公式を参照してください。実際、先頭の項の定数を決定することもできます (アルゴリズムの漸近論と密接に関係していなくても): 合計は n c+1 /(c+1) + O( c ) です。 、たとえば統合を使用します。

于 2010-07-13T03:23:34.053 に答える
2

あなたが持っているものは正しくありませんが、あなたは正しい道を歩んでいました。

あなたが犯した間違い：

T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c    
T(n) = T(n-k) + n^c + (n-1)^c + (n-k+1)^c

1 行目から 2 行目に移動することはできません。

k を大きくすると、右辺の項の数も増えます。

このように書くことを考えると、次のようになります。

T(n) - T(n-1)  = n^c.

T(n-1) - T(n-2) = (n-1)^c
..

T(n-k) - T(n-k-1) = (n-k)^c.

..
T(2) - T(1) = 2^c

これらを合計するとどうなりますか？

それができたら、c=1 と c=2 の答えがわかりますか? そこから最終的な答えのパターンを導き出すことができますか?

于 2010-07-11T23:47:50.447 に答える
0

ここにあります：

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

これは O(n c+1 ) です。

これが合理的な境界であることを示すためにc = 1、

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

これは明らかに Θ(n 2 ) です。

于 2010-07-13T03:38:48.777 に答える
0

これらを把握するには、いくつかの用語を入力してパターンを探します。

T(1) = 0 + 1^c

T(2) = T(1) + 2^c = 0 + 1^c + 2^c

T(3) = T(2) + 3^c = 0 + 1^c + 2^c + 3^c

T(4) = ...

パターンを n で表現すると、答えが得られます。

于 2010-07-13T03:03:51.990 に答える
0

n から下に向かって作業する代わりに、0 から上に向かって作業することから始めてみませんか (再帰は 0 で終了し、そのビットを省略したと仮定します)。不動点 (つまり、すべてのケースで同じパターンが繰り返されるパターン) に気付き始めると、適切な答えの候補が得られます。帰納法などで答えを証明してみてください。

于 2010-07-11T23:47:01.110 に答える
0

n^c は、もちろん n の値に影響されますが、n 対 n + 1 ではこれ以上複雑にならないことを観察することから始めます。その特定の用語の「実行時間」を決定するのは c です。それを考えると、用語の実行時間は一定であると仮定でき（少なくとも私はそう思います）、特定の n に対して再帰が実行される回数を決定すると、境界が得られます。

于 2010-07-11T23:50:07.803 に答える