-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

这个算法的复杂度显然是线性的(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 回答