分析ランタイムが

Question

Iは、次のコードが与えられました：

public class alg 
{ 
    public static int hmm (int x) 
    { 
     if (x == 1) 
     { 
      return 2; 
     } 
     return 2*x + hmm(x-1); 
    } 

    public static void main (String[] args) 
    { 
     int x = Integer.parseInt(args[0]); 
     System.out.println(hmm(x)); 
    } 
} 

だから、最初の質問は、このアルゴリズムは何を数えるのでしょうか？ 私はちょうどタイプして、 日食でそれをrunnedしたので、私はそれが何をよりよく見ることができます（それは前に擬似コードでした、私はコードを入力したのでここにそれを入力できませんでした）。私はこのアルゴリズムが次のことを認識しています：それは入力を受け取り、次の数でそれを掛けます。 だから例として：

input = 3, output = 12 because 3*4 = 12. 
Or Input = 6, output 42 because 6*7 = 42. 

さてさて、次の質問は私の問題です。私はこのアルゴリズムのランタイムを分析するように求められますが、どこから始めたらいいかわかりません。 私は最初に、xを定義するとき、すでに持っていると言うでしょう。time = 1 ifループはtime = 1も与えます。 最後の部分は、return 2x + alg(x-1)は "something^x"または..？ だから私たちは+ 2 "^ X何か" のようなものを持って最後に、私はthatsの権利を疑う：/

編集を、あまりにも擬似コードを入力するために管理:)

Input: Integer x with x > 1 
if x = 1 then 
    return 2; 
end if 
return 2x + hmm(x-1); 

Answer 1

問題が発生した場合は、（小さな）番号のコードを歩いてみてください。

これは何を計算しますか？

1. 3 != 1ので、私たちは2 * 3 + hmm(3-1)を計算する：

   はのは、一例としてhmm(3)を見てみましょう。再帰レベルを下げる。

2. 2 != 1ですので、2 * 2 + hmm(2-1)と計算されます。再帰レベルを下げる。
3. 1 == 1ですので、2を返します。したがって、再帰はありません。したがって、hmm(2-1) == hmm(1) == 2。
4. 1つの再帰レベルをバックアップすると、2 * 2 + hmm(1) = 2 * 2 + 2 = 4 + 2 = 6となります。よく見るとこのようにhmm(2) = 6
5. バックアップ別のレベル、我々は2 * 3 + hmm(2) = 6 + 6 = 12

を取得し、アルゴリズムは計算：

2*x + ... + 4 + 2

私たちは、これを逆にして、2を考慮し、

を得ることができます

2 * (1 + 2 + ... + x)。私たちは、よく知られた式を有しているためarithmetic progressionある

、（すなわちx² + x）

はどのくらい時間がかかりますか？

漸近実行時間はO(n)です。

ループがないため、再帰の回数を数えればよいだけです。計算の個々のステップを数えるように誘惑されるかもしれませんが、それらのステップはすべてのステップで一定です。したがって、通常はそれらを定数因子kに結合します。

O(n)とは何ですか？

うーん...私たちはx == 1に到達するまで、すべての段階で1によってxの減少、x - 1再帰ステップを作ります。 x = nからx = 1には、n - 1のこのようなステップがある。したがって、k * (n - 1)操作が必要です。

もしnが非常に大きいと思うなら、- 1は無視できるので、それを削除します。 nの場合は、O(nk)とO(n)のどちらもそれほど大きくはないので、一定の要因も削除します。

Answer 2

機能は

f(x) = 2(x + x-1 + x-2 + ... + 1) 

を算出し、

O(x)で実行されます。すなわち、x回が一定時間O(1)と呼ばれます。