1

Topcoder アルゴリズムの問​​題を解決し始めたばかりで、Java で SRM 466 Div 2 LotteryTicket 問題用にこのアルゴリズムを作成しました。

私は時間の複雑さが苦手なので、誰かがこのアルゴリズムの時間の複雑さを段階的に計算する方法を説明できれば.

public static String buy1(int price,int...b){
    int sum=0; String stat="IMPOSSIBLE";

    for(int i=0;i<b.length;i++)
        sum=sum+b[i];

    if(sum==price)
        return "POSSIBLE";

    if(b.length>1){
        stat=buy1(price,Arrays.copyOfRange(b,0,b.length-1));
        stat=buy1(price,Arrays.copyOfRange(b,1,b.length));
    }

    return stat;
}
4

3 に答える 3

5

あなたの場合、再帰関係は（b.length（）をbnにする）です

                     ___________buy1(p,bn-1) (as (b,0,b.length-1) equivalent is bn-1 in number )
                    /
    buy1(p,bn) ____/
                   \
                    \___________ buy1(p,bn-1)  (as (b,1,b.length) equivalent is bn-1 in number )

したがって、n = n-1 の 2 つのサブ問題に対する私たちの問題したがって、時間関数 T(n) は次のようになります。

   T(n)=2T(n-1)+c (For convenience lets eliminate c as it is very less compared to T(n) for this instance )
   T(n)=2[2(T(n-2))]
   T(n)=2{2[2(T(n-3))]} ===> 2poweri(T(n-i))  -------- equation(1)

繰り返しは基本条件を満たした時点で終了します。T(0)=c(be base condition) としましょう。これは、基本条件の t(ni)=t(0) .so i=n を意味します。

式 (1) に i 値を代入すると、2power(n){t(0)} が得られます。

したがって、Time 関数の値は 2power(n) になり、プログラムの複雑さは bigoh(2power(n)) に等しくなります。

于 2012-09-12T12:29:49.763 に答える
2

興味深い質問です。正しく計算してみましょう ;) そこで、条件 (合計 == 価格) が決して現れない最悪の状況を調べます。

最初に、b.length = 1 の場合の完全性を確認しましょう。次に、サイクル内で "=" 操作を 1 つだけ使用する必要があります。

for(int i=0;i<b.length;i++)

そして 2 内部の初期化:

int sum=0; String stat="IMPOSSIBLE";

次のステップ。このタスクを N について計算してみましょう。最初に、最初のサイクル内で N 個の "=" 操作、初期化内で 2 回、if 内で 2 回の操作を行う必要があります。

    stat=buy1(price,Arrays.copyOfRange(b,0,b.length-1));
    stat=buy1(price,Arrays.copyOfRange(b,1,b.length));

別の操作は、再帰ステップ内で行われます。したがって、この状況では再帰式を使用できます。これは次のようになります。

f(n) = 4 + n + 2*f(n-1)、f(1) = 3

この方程式の解: f(n) = -6+5 * 2^nn

したがって、アルゴリズムの複雑さは指数関数的です。O(2^n) 漸近的な複雑さを変更しないため、「=」以外のすべての操作を無視します。

于 2012-09-12T11:20:49.543 に答える
2

再帰ツリー法とマスター法を使用して複雑さを見つけることができます。

この問題にアプローチする方法についてのアイデアについては、こちらをご覧ください。

追加の演習として、これを使用してマージソートの複雑さを計算してみてください。

于 2012-09-12T07:06:26.397 に答える