4

私はMaster Theoremを少し更新していますn.2つのサイズのサブ問題を再帰的に解決n-1し、ソリューションを一定時間で結合することにより、サイズの問題を解決するアルゴリズムの実行時間を把握しようとしています.
式は次のとおりです。
T(N) = 2T(N - 1) + O(1)
しかし、マスター定理の条件をどのように定式化できるかわかりません。つまり、この場合のマスター定理の式は
ありませんか? はいの場合、明らかにそれ以降であり、これをどのように理解できるかのベースはどこにありますか? 私がこれまでのところ正しいと仮定しますか？T(N/b)bb=N/(N-1)
a > b^kk=0O(N^z)z=log2(N/N-1)

4

4 に答える 4

3

ああ、ヒントで十分です。解決策は実際には非常に簡単です。両側を z 変換し、項をグループ化し、逆 z 変換して解を取得します。

まず、次のように問題を見てください。

    x[n] = a x[n-1] + c

両側に z 変換を適用します (ROC に関してはいくつかの専門的事項がありますが、今は無視しましょう)

    X(z) = (a X(z) / z) + (c z / (z-1))

X(z) を解いて取得する

    X(z) = c z^2 / [(z - 1) * (z-a)]

この式は次のように書き直すことができます。

    X(z) = r z / (z-1) + s z / (z-a)

ここで、r = c/(1-a) および s = - ac / (1-a)

さらに、次のことに注意してください。

    X(z) = P(z) + Q(z)

ここで、P(z) = rz / (z-1) = r / (1 - (1/z))、および Q(z) = sz / (za) = s / (1 - a (1/z))

それを得るために逆 z 変換を適用します。

    p[n] = r u[n]

と

    q[n] = s exp(log(a)n) u[n]

ここで、log は自然対数を表し、u[n] は単位 (ヘビサイド) ステップ関数です (つまり、n>=0 の場合は u[n]=1、n<0 の場合は u[n]=0)。

最後に、z 変換の線形性によって:

    x[n] = (r + s exp(log(a) n))u[n]

ここで、r と s は上で定義したとおりです。

元の問題にラベルを付け直して

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

それから

    T(n) = (c/(a-1))(-1+a exp(log(a) n))u[n]

ここで、exp(x) = e^x、log(x) は x の自然対数、u[n] は単位ステップ関数です。

これはあなたに何を伝えますか？

私が間違いを犯さない限り、T は n に対して指数関数的に増加します。これは、a > 1 という合理的な仮定の下では、実質的に指数関数的に増加する関数です。指数は、a (より具体的には、a の自然対数) によって支配されます。

もう 1 つ単純化すると、exp(log(a) n) = exp(log(a))^n = a^n であることに注意してください。

    T(n) = (c/(a-1))(-1+a^(n+1))u[n]

だから O(a^n) をビッグオー記法で。

そして今、ここに簡単な方法があります：

T（0）= 1を置く

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

    T(1) = a * T(0) + c = a + c
    T(2) = a * T(1) + c = a*a + a * c + c
    T(3) = a * T(2) + c = a*a*a + a * a * c + a * c + c
    ....

これによりパターンが作成されることに注意してください。具体的には：

    T(n) = sum(a^j c^(n-j), j=0,...,n)

put c = 1 を与える

    T(n) = sum(a^j, j=0,...,n)

これは幾何級数であり、次のように評価されます。

    T(n) = (1-a^(n+1))/(1-a)
         = (1/(1-a)) - (1/(1-a)) a^n
         = (1/(a-1))(-1 + a^(n+1))

n>=0 の場合。

この式は、z 変換法を使用して c=1 に対して上記で与えられたものと同じであることに注意してください。繰り返しますが、O(a^n)。

于 2013-01-20T12:18:56.270 に答える
1

マスターの定理についても考えないでください。一般形式 T(n) = aT(n/b) + f(n) から b > 1 のときにマスターの定理が与えられた場合にのみ、マスターの定理を使用できます。

代わりに、このように考えてください。再帰呼び出しごとに入力 n のサイズを 1 ずつ減らす再帰呼び出しがあります。また、再帰呼び出しごとに、コストは定数 O(1) です。入力サイズは 1 に達するまで減少します。その後、再帰呼び出しを行うために使用したすべてのコストを合計します。いくつだ？n. したがって、これには O(2^n) かかります。

于 2013-01-20T12:01:30.100 に答える
0

マスター定理の観点からこの問題を定式化できないようです。

再帰ツリーを描いてパターンを理解し、代入法でそれを証明することから始めるのが良いでしょう。数式を数回展開して、どこにつながるかを確認することもできます。

代わりに2つのサブ問題を解決するこの質問も参照してくださいa: 一定の組み合わせ時間を持つ再帰アルゴリズムの制限時間

于 2013-01-20T11:44:31.313 に答える
0

このように考えてよいのではないでしょうか

いつ

n = 1, T(1) = 1
n = 2, T(2) = 2
n = 3, T(3) = 4
n = 4, T(4) = 8
n = 5, T(5) = 16

これが等比級数1 + 2+ 4+ 8 + 16...であり、その和が第 1 項であることは容易にわかり(ratio^n - 1)/(ratio - 1)ます。このシリーズの場合は

1 * (2^n - 1)/(2 - 1) = 2^n - 1.

ここで支配的な用語は2^nであるため、関数は に属しTheta(2^n)ます。あなたはそれを行うことによってそれを確認することができますlim(n->inf) [2^n / (2^n - 1)] = +ve constant.

したがって、関数はに属しますBig Theta (2^n)

于 2013-01-27T01:14:33.730 に答える