-8

私はアルゴリズムを持っていますが、それが何をするのか、そしてその複雑さは何なのかわかりませんが、誰かが私を助けることができますか？

PUZZLE (A:int[], L:int, R:int)
{

// Assume L, R >0 and L <= R

If( L = R) Then

  return A[L];

double Temp1 :=PUZZLE(A,L, (L+R)/2);

double Temp2 :=PUZZLE(A, 1 + (L+R)/2,R);

If(Temp1 < Temp2) Then

return Temp1;

else Then

return Temp2;

}
4

3 に答える 3

1

指定された間隔内の指定された配列の最小値を計算します。

于 2013-02-23T15:47:25.783 に答える
0

このコードは、シーケンスAのサブシーケンスに存在する最小値を計算します。サブシーケンスはインデックスiで始まり、インデックスjで終わります。あなたのアルゴリズムは英語で次のように翻訳できます：

puzzle(A, i, j) :
  if the subsequence has only one element :
    return this element
  min-left is the minimum value present at the first half of the subsequence(it's computed recursively)
  min-right is the minimum value present at the second half of the subsequence(it's computed recursively)
  return the minimum of min-left, min-right

このアルゴリズムの複雑さは明らかにlineral（O（N））です。しかし、あなたが私を信じていないのなら、私はあなたのためにマスター定理（http://en.wikipedia.org/wiki/Master_theorem）を使ってそれを証明します。

T（N）をアルゴリズムの繰り返しとします。それで：

T(N) = 2T(N/2) =>
T(N) = 2T(N/2) + Theta(1) =>
T(N) = Theta(N) (from the first case of the master theorem, which states
that if f(N) = O(N^logb a-e), for e>0, then the complexity is Theta(N^logb a),
where a=2, b=2, f(N)=Theta(1), and e=1
于 2013-02-23T16:19:27.910 に答える
0

私には、フィードフォワードネットワークの一部のようです。詳細については、そのwikiを確認してください

于 2013-02-23T15:48:34.977 に答える