3

これは、動的計画法について私が取り組んでいる小さな演習です。私は次の機能を持っています:

ここに画像の説明を入力

この関数を 2 つのアプローチ (メモ化によるトップダウンとボトムアップ) でプログラムする必要があります。

ボトムアップのために私が現在行っていることは次のとおりです。

    public static int functionBottomUp (int n){
            int [] array = new int[n+1];
            array[0] = 1;
            for(int i = 1; i < array.length; i++){
                if(i == 1)
                    array[i] = array[i - 1];
                else {
                    for(int p = 0; p < i; p ++)
                        array[i] += array[p];
                }
            }
            return array[n];
   }

そしてメモ化のために：

public static int functionMemoization(int n){
        int[] array = new int[n+1];     
        for(int i = 0; i < n; i++)
            array[i] = 0;
        return compute(array, n);
    }

    private static int compute(int[] array, int n){
        int ans = 0;
        if(array[n] > 0)
            return array[n];
        if(n == 0 || n == 1)
            ans = 1;
        else 
            for(int i = 0; i < n; i++)
                ans += compute(array, i);
        array[n] = ans;
        return array[n];
    }

両方の正しい出力が得られますが、両方の複雑さを計算するのに苦労しています。

最初の複雑さは、呼び出しと呼び出しを行うためです(これはf(n)正式な証明ではないことはわかっていますが、これはアイデアを提供するためのものです)。2^nf(3)7f(0)f(4)15f(0)

しかし今、私は両方の関数の複雑さを計算することに行き詰まっています。

ボトムアップ :

複雑さは O(n) であると言えます ( のためfor(int i = 1; i < array.length; i++)) が、この内部ループがありfor(int p = 0; p < i; p ++)、これが複雑さを変更するかどうかはわかりません。

メモ化 :

配列を初期化する最初のループのため、明らかにこれはほとんどの O(n) です。しかし、計算関数がこの複雑さをどのように変更できるかはわかりません。

誰かが私のためにこれを明確にすることができますか?

4

1 に答える 1

2

あなたの機能を見てみましょう。ボトムアップ DP バージョンは次のとおりです。

public static int functionBottomUp (int n){
        int [] array = new int[n+1];
        array[0] = 1;
        for(int i = 1; i < array.length; i++){
            if(i == 1)
                array[i] = array[i - 1];
            else {
                for(int p = 0; p < i; p ++)
                    array[i] += array[p];
            }
        }
        return array[n];
}

行われている作業を数え上げるには、任意の i に対してループ反復 i を完了するのにどれだけの作業が必要かを調べることができます。i = 1 の場合、行われた作業は O(1) であることに注意してください。それ以外の場合、ループの実行時間は次のこの部分によって占められます。

for(int p = 0; p < i; p ++)
    array[i] += array[p];

このループの時間計算量は i に比例します。これは、ループ反復 i が (多かれ少なかれ) i が機能することを意味します。したがって、行われる総作業量は (概算)

1 + 2 + 3 + ... + n = Θ(n 2 )

したがって、ここでの実行時間は、質問で推測した O(n) ではなくΘ(n 2 ) です。

それでは、トップダウン バージョンを見てみましょう。

public static int functionMemoization(int n){
    int[] array = new int[n+1];     
    for(int i = 0; i < n; i++)
        array[i] = 0;
    return compute(array, n);
}

private static int compute(int[] array, int n){
    int ans = 0;
    if(array[n] > 0)
        return array[n];
    if(n == 0 || n == 1)
        ans = 1;
    else 
        for(int i = 0; i < n; i++)
            ans += compute(array, i);
    array[n] = ans;
    return array[n];
}

最初に Θ(n) を実行して配列をゼロにし、次に を呼び出しcomputeてすべての値を計算します。最終的にはすべてにarray値を入力し、配列要素ごとに 1 回だけ入力することになるため、時間の複雑さを判断する 1 つの方法は、配列エントリごとに、入力に必要な作業量を判断することです。この場合、実行される作業は次の部分によって決定されます。

for(int i = 0; i < n; i++)
    ans += compute(array, i);

値をメモ化しているので、値 n で関数を評価するために必要な作業を決定するときに、各再帰呼び出しに O(1) の時間がかかると仮定できます。実際の作業は、すべての n を合計すると考慮されます。前と同じように、ここで行われる仕事は n に比例します。したがって、n は 1 から n までの範囲なので、行われる作業はおおよそ次のようになります。

1 + 2 + 3 + ... + n = Θ(n 2 )

これもまた、推定 O(n) よりも多くの作業です。

ただし、この再発を評価するはるかに高速な方法があります。f(n) の最初のいくつかの値を見てください。

  • f(0) = 1
  • f(1) = 1
  • f(2) = 2
  • f(3) = 4
  • f(4) = 8
  • f(5) = 16
  • ...
  • f(n) = 2 n-1

したがって、私たちはそれを得る

  • f(0) = 1
  • f(n) = 2 n-1 n > 0の場合

したがって、次の関数はf時間を評価します。

int f(int n) {
    return n == 0? 1 : 1 << (n - 1);
}

固定サイズの整数 (たとえば、32 ビットまたは 64 ビットの整数) を扱っていると仮定すると、これには O(1) の時間がかかります。任意精度の整数で作業している場合、これにはΘ(n) ビットを書き出さずに2 n-1を表すことができないため、時間 Θ(n) がかかりますが、この仮定の下で操作している場合、追加のコストを考慮して、元のコードも調整する必要があります。簡単にするために、私はそれを無視するか、読者への演習として残しておきます。^_^

お役に立てれば！

于 2013-10-21T19:20:29.263 に答える