0

私は試験のために勉強していて、対処する必要があるいくつかの問題に出くわしました - ベースケースの扱い:

コードから繰り返し関係に変換していますが、その逆ではありません

例 1:

 if(n==1) return 0;

そのコード片に対する再帰関係は次のようになります: T(1) = 0

どうやってそれを手に入れたのですか？n==1 を見ると、これは値 > 0 との比較であることがわかります。これは何らかの形式の作業を行っているため、「T(1)」と戻り値 0 を設定します。何もしていないので、「=0」とします

 => T(1) = 0;

例 2:

 if(n==0) return n+1*2;

分析: n==0 は、何の作業も行っていないことを意味するため、T(0) を返しますが、n+1*2 を返します。仕事をしているので「=1」

 => T(0) = 1;

私が知りたいのは、これが再帰関係の基本ケースを考え出すためにそのようなコードを分析する正しい方法であるかどうかです?

ベースケースの可能性を使い果たすために自分で思いついたこれらについては確信が持てません：

Example 3: if(n==m-2) return n-1; //answer: T(1) = 1; ?
Example 4: if(n!=2) return n;     //answer: T(1) = 1; ?
Example 5: if(n/2==0) return 1;   //answer: T(1) = 1; ?
Example 6: if(n<2) return;        //answer: T(1) = 0; ?
4

1 に答える 1

3

コードのコンテキスト外で基本ケースを分析するのは難しいため、関数全体を投稿すると役立つ場合があります。ただし、 T(n) は常に「仕事」を表すという仮定から混乱が生じていると思います。あなたは複雑さのクラスを受講していて、再帰関数の複雑さを表現する方法として再帰関係について学んだと思います。

T(n) は単なる関数です。数値 n (通常は正の整数) を代入すると、数値 T(n) が得られます。他の関数と同様に、T(n) はそれ自体では何の意味もありません。ただし、T(n) という表記の関数を使用して、サイズ n の入力に対してアルゴリズムを実行するのに必要な時間を表すことがよくあります。これらは 2 つの別個の概念です。(1) 関数 T(n) とそれを表現するさまざまな方法 (再帰関係など)、および (2) アルゴリズムを実行するために必要な操作の数。

例を挙げましょう。

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

コードの出力を表す関数 F(n) を記述できるかどうか見てみましょう。さて、F(n) = n*F(n-1) で、F(0) = 1 です。なぜですか? コードから明らかなように、F(0) の結果は 1 です。その他の n の値の場合、結果は F(n) = n*F(n-1) になります。この再帰関係は、再帰関数の出力を表現する非常に便利な方法です。もちろん、F(n) = n と簡単に言えます。(階乗演算子)、これも正しいです。それは同じ関数の非再帰式です。アルゴリズムの実行時間や、アルゴリズムが実行している「作業」の量については何も述べていないことに注意してください。コードが出力するものの数式を書いているだけです。

関数の実行時間の処理は、「作業」または「操作」が何を意味するかを決定する必要があるため、少し注意が必要です。「return」は演算として数えませんが、乗算は演算として数え、条件 (if ステートメント) は演算として数えます。これらの仮定の下で、入力 n が関数に与えられたときにどれだけの作業が行われるかを記述する関数 T(n) の再帰関係を書くことができます。(後で、これがよくない質問である理由についてコメントします。) n = 0 の場合、条件 (if ステートメント) と return があり、他には何もありません。したがって、T(0) = 1 です。その他の n > 0 については、条件付きの乗算がありますが、T(n-1) を計算するには多くの演算が必要です。したがって、n の合計は次のようになります。

T(n) = 1 (conditional) + 1 (multiply) + T(n-1) = 2 + T(n-1),
T(0) = 1.

T(n) を再帰関係として書くことができます: T(n) = 2 + T(n-1), T(0) = 1. もちろん、これは関数 T(n) = 1 + 2n でもあります。 . 繰り返しますが、これらは 2 つの非常に異なる機能であることを強調したいと思います。F(n) は、n が入力の場合の関数の出力を記述しています。T(n) は、n が入力の場合にどれだけの作業が行われたかを表しています。

さて、先ほど説明した T(n) は、複雑性理論の観点からは良くありません。その理由は、複雑性理論は、単一の整数のみを引数として取る関数を計算するために必要な作業量を説明するものではないからです。言い換えれば、F(n) の形式の関数に必要な作業を見ていないということです。サイズ n の入力に対してアルゴリズムを実行するのにどれだけの作業が必要かという、より一般的なものが必要です。たとえば、MergeSort は、オブジェクトのリストを並べ替えるためのアルゴリズムです。n 個の項目のリストに対して MergeSort を実行するには、およそ nlog(n) 回の操作が必要です。MergeSort は数値 n に対して何もしていないことに注意してください。むしろ、サイズのリストで動作します。n. 対照的に、階乗関数 F(n) はサイズ n の入力では動作しません。おそらく n は整数型なので、その値に関係なく、おそらく 32 ビットか 64 ビットか何かです。または、そのサイズがそれを表す最小ビット数であると言うことができます。いずれにせよ、n は入力であり、入力のサイズではありません。

これらの質問に答えるときは、関数の出力を記述する再帰関係が必要なのか、関数の実行時間を記述する再帰関係が必要なのかを明確にすることが重要です。

于 2013-09-13T06:56:02.357 に答える