-3

質問 01: アルゴリズムの複雑さを測定するとき、T (1) を見つけるにはどうすればよいですか?

たとえば、私はこのアルゴリズムを持っています

Int Max1 (int *X, int N)
{
  int a ;
  if (N==1) return X[0] ;
  a = Max1 (X, N‐1);
  if (a > X[N‐1]) return a;
  else return X[N‐1];
}

T(1) を見つけるにはどうすればよいですか?

質問2 ： 

T(n)= T(n-1) + 1 ==> O(n)

この式の「1」の意味は何ですか

心から

4

3 に答える 3

1

Max1(X,N-1)実際のアルゴリズムですか？残りはいくつかのチェックでありO(1) 、入力に関係なく、かかる時間は同じになります。

Max1私が想定できる関数は、配列内で配列の最大数を見つけることです。これは、O(n)入力nの数に比例して時間とともに増加するためです。

また、私が知る限り、ほとんどのアルゴリズムで1は1を表します。つまり、文字がどのように取得されたかを意味する場合、文字だけが可変の意味を持ちます。

T(n-1) + 1にO(n)、それはあなたが係数と低次の項を無視するという事実によるので、1は両方の場合を無視して作成しますO(n)

于 2013-01-03T15:52:21.253 に答える
1

T( n ) は「 nの関数」と呼ばれるものです。つまり、nは「変数」(その場所に異なる値を代入できることを意味します)であり、nの各特定の (有効な) 値によって決定されます。 T( n ) の対応する値。したがって、T(1) は単に「nが 1のときの T( n ) の値」を意味します。

問題は、入力値が 1 の場合のアルゴリズムの実行時間はどれくらいかということです。

于 2013-01-03T18:17:43.197 に答える
1

回答 1. 複雑さを探しています。必要なケースの複雑さ (最良、最悪、または平均) を決定する必要があります。選択した内容に応じて、さまざまな方法で T(1) を見つけます。

  • 最適: アルゴリズムが取得できる長さ 1 の最も簡単な入力を考えてください。リスト内の要素を検索する場合、その要素がリストの最初にある場合が最適であり、T(1) = 1 にすることができます。
  • 最悪: アルゴリズムが取得できる長さ 1 の最も難しい入力を考えてください。おそらく、線形探索アルゴリズムは長さ 1 のほとんどの入力に対して 1 つの命令を実行しますが、リスト [77] では 100 ステップを実行します (この例は少し不自然ですが、アルゴリズムが状況に応じて多かれ少なかれステップを取ることは完全に可能です)。入力の「サイズ」とは無関係の入力のプロパティ)。この場合、T(1) = 100 です。
  • 平均: アルゴリズムが取得できる長さ 1 のすべての入力を考えてください。これらの入力に確率を割り当てます。次に、すべての可能性の平均 T(1) を計算して、平均ケース T(1) を取得します。

あなたの場合、長さ1の入力の場合、常に返すので、 T(n) = O(1) (実際の数は命令のカウント方法によって異なります)。

回答 2. このコンテキストの「1」は、命令カウントのシステムでの正確な命令数を示します。O(1) は、入力に依存しない (変化、傾向など) 任意の数 (または数) を意味する可能性があるという点で、O(1) とは区別されます。あなたの方程式は、「サイズ n の入力で関数を評価するのにかかる時間は、サイズ n - 1 の入力で関数を評価するのにかかる時間に、正確に 1 つの追加命令を加えたものに等しい」と述べています。

于 2013-01-03T17:20:44.880 に答える