23

今日のクラスで、私の先生はこの再帰的階乗アルゴリズムを黒板に書きました:

int factorial(int n) {
   if (n == 1) 
       return 1;
   else 
       return n * factorial(n-1);
}

彼女は、それには の費用がかかると言いましたT(n-1) + 1。

それから反復法で彼女は言ったT(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + jので、アルゴリズムはいつ停止するn - j = 1ので、そうj = n - 1です。

その後、彼女は に代入jしT(n-j) + j、 を取得しT(1) + n-1ました。

彼女は、その n-1 = 2 (log 2 n-1)について直接言ったので、アルゴリズムのコストは指数関数的です。

私は本当に最後の 2 つのステップを失いました。誰か説明してくれませんか？

4

1 に答える 1

27

このアルゴリズムの分析から始めましょう。完了した総作業量の再帰関係を書くことができます。基本的なケースとして、アルゴリズムがサイズ 1 の入力で実行されると、1 つの作業単位を実行するため、

T(1) = 1

サイズ n + 1 の入力の場合、アルゴリズムは関数自体の中で 1 単位の作業を行い、サイズ n の入力に対して同じ関数を呼び出します。したがって

T(n + 1) = T(n) + 1

再帰の項を展開すると、次のようになります。

  • T(1) = 1
  • T(2) = T(1) + 1 = 2
  • T(3) = T(2) + 1 = 3
  • T(4) = T(3) + 1 = 4
  • ...
  • T(n) = n

したがって、一般に、このアルゴリズムを完了するには n 単位の作業が必要です (つまり、T(n) = n)。

次に先生が言ったのは、

T(n) = n = 2 log 2 n

累乗と対数は互いに逆演算であるため、ゼロ以外の任意の x に対して2 log 2 x = x であるため、このステートメントは真です。

問題は、これは多項式時間なのか指数時間なのかということです。私はこれを疑似多項式時間と分類します。入力 x を数値として扱う場合、ランタイムは確かに x の多項式です。ただし、アルゴリズムの実行時間は、問題への入力を指定するために使用されるビット数に関して多項式でなければならないというように、多項式時間は形式的に定義されます。ここで、数値 x は Θ(log x) ビットのみで指定できるため、2 log xの実行時間は技術的に指数時間と見なされます。これについては、以前の回答で長さとして書きました。より詳細な説明については、それを参照することをお勧めします。

お役に立てれば！

于 2013-05-04T20:22:39.717 に答える