-7

申し訳ありませんが、ここで長い文脈上の話を書く時間はありません。これは私が現在行っている模擬試験の問題であり、私の大学のすべてのリソースはオフラインです (素晴らしい大学、私は知っています)。これを開始する方法についても完全に困惑しています。誰かが私にそれを説明してもらえますか？私は数学が得意ではありません。

次の再帰的な方法を検討してください。

public static int triple(int x) {
    if (x == 0) return 0;
    else return add(3, triple(decrement(x)));
}

デクリメント メソッドの最悪の場合の時間パフォーマンスが一定であり、add メソッドがその 2 番目のパラメーターで線形であると仮定すると (つまり、add(x,y) の時間は、by+aいくつかの定数bおよびとして表すことができます)、その最小値をa導き出します。big Oは、x に関するトリプル メソッドの最悪の場合の時間パフォーマンスを表します。このメソッドの複雑さを導き出すには、最初のいくつかのメソッド インスタンス (問題サイズ) の再帰関係を決定して展開し、式を一般化して の閉じた形式の方程式を形成しますnth case。あなたの働きを見せてください。

4

4 に答える 4

2

特定の x に対して、triple0、1、2、... x で再帰的に呼び出されます。これらの引数を再帰呼び出しで呼び出しましょうi。引数が の場合、iのadd2 番目の引数は3(i-1)です。つまり、このようなadd呼び出しのコストは線形ですi。したがって、各再帰呼び出しは への引数で線形tripleです。そのxような呼び出しがあるため、算術級数 (0 + 3 + 6 + ...) の合計が得られます。これは O(n 2 ) 時間の計算量です。

このコードで遊ぶことができます：

public class Test
{
  static int time;
  public static int triple(int x) {
    if (x == 0) return 0;
    else return add(3, triple(decrement(x)));
  }
  private static int add(int i, int j) {
    System.out.println("Spending " + j);
    time += j;
    return i + j;
  }
  private static int decrement(int x) { time++; return x-1; }
  public static void main(String[] args) {
    for (int i = 1; i < 100; i+=10) {
      time = 0;
      System.out.format("triple(%d)=%d; time=%d\n", i, triple(i), time);
    }
  }
}
于 2012-06-21T17:22:33.063 に答える
1

x の値をトリプル メソッドの実行回数にマッピングするテーブルを作成します。その後、両者の間に関係を形成します。

x |  executions |              Executions
-------------------------------------
0  | T(0)                     |  0 A(0)
1  | T(1) + A(3,1) + T(0)     |  3 A(1)
2  | T(2) + + A(3,1) + T(1)   |  6 A(2)
3  | T(3) + A(3,1)            |  9 A(3)

   Time Complexity for T= T(n)+T(n-1)+...+T(n-n)
   Number of add calls is linear O(n)   

   nth term for number of executions
   Un = 3+(n-1)d
      = 3+(n-1)3

   the sum of the an arithmetic series making it O(n^2)
于 2012-06-21T16:55:44.403 に答える
1

さて、私が最終的にそれを導き出した方法 (そして、私を動かすために回答を投稿してくれたすべての素敵な人々に感謝します) は、Jochen のアドバイスを受けて、簡単な複雑さのマップを作成することでした。これにより、すべてがはるかに簡単になりました。

まず、この質問では add が O(n) 時間であると規定されていることに注意してください。

次に、基本的な「トリプル」呼び出し階層:

n  |  Time complexity:
------------------------------------------
1  | T(1) + (T(0) = 1   )
2  | T(2) + (T(1) = ... )
3  | T(3) + (T(2) = ... )

明らかにパターンが出現しています...

n  | Time complexity
-------------------------------------------
n  | T(n) + T(n - 1)

したがって、T(n) の時間計算量は、トリプル コールの時間計算量がn * Tどこにあるかのように見えます。T呼び出しの増加の原因が でaddあり、その時間計算add量がO(n)であるとすると、時間計算量はn * nまたはになります。O(n^2)

みんなありがとう、間違った用語や何かを使用した場合はお知らせください。

編集: 一部の追加はオフでしたが、BigO 表記は同じです。

于 2012-06-21T17:25:08.863 に答える
1

まず、特定の x に対してトリプルが再帰的に呼び出される頻度を調べます。上記のようなテーブルを作成します。これにより、一般化された用語の一部が得られます。

次に、トリプルの実行ごとに、最悪の場合の時間計算量はどのくらいになるでしょうか? ヒント、それは add() 関数によって決定されます。

次に一般化します。

于 2012-06-21T17:01:06.363 に答える