алгоритм для определения того, что он делает

Question

У меня есть алгоритм, и я и не знаю, что он делает, и в чем его сложность, может ли кто-нибудь мне помочь?

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; 

} 

Answer 1

Этот код вычисляет минимальное значение, присутствующее в подпоследовательности последовательности 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 

Answer 2

Рассчитать минимальное значение для данного массива в течение заданного интервала.

Answer 3

Мне кажется, что часть подачи вперед neual network. проверьте его wiki для получения дополнительной информации.