Как написать рекуррентное отношение псевдокода?

Question

Foo(A,f,l) 
**Precondition: A[f ...l] is an array of integers, f,l are two naturals ≥ 1 with f ≤ l. 
if (f = l) then 
    return A[f] 
else 
    m ← floor of((f+l)/2) 
    return min(Foo(A,f,m), Foo(A,m + 1,l)) 
end if 

Исправьте меня, если я ошибаюсь, но я думаю, что этот код возвращает наименьшее целое число массива. Но как я могу выяснить, какое отношение рецидивов описывает сложность времени в терминах массива A? Не могли бы вы направить меня на решение, чтобы я мог понять? Я даже не знаю, с чего начать.

Answer 1

Рекуррентное соотношение, которое мы можем восстановить из структуры псевдокода. Мы можем позволить T(n) представить время, затраченное алгоритмом в зависимости от размера ввода. Для n = 1 время постоянное, скажем T(1) = a. Наш вопрос сейчас для больших n, как мы можем выразить T(n)?

Мы будем в пункте else за n > 1. Мы делаем некоторую дополнительную работу - давайте назовем его b - а затем вызвать функцию дважды, один раз для ввода размера floor(n/2) и один раз для ввода размера ceiling(n/2). Поэтому мы можем записать эту часть рекурсии как T(n) = b + T(floor(n/2)) + T(ceiling(n/2)). Теперь мы можем выписать некоторые термины.

n T(n) 
1 a 
2 b + a + a = b + 2a 
3 b + b + 2a + a = 2b + 3a 
4 b + b + 2a + b + 2a = 3b + 4a 
5 b + b + 2a + 2b + 3a = 4b + 5a 
... ... 
k = (k-1)b + (k)a = kb - b + ka = k(a + b) - b 

Мы находим предположение, что T(n) = (a + b)n - b для некоторых констант a и b, которые зависят от стоимости объемов работ мы можем взять в качестве постоянной (заметим, что вычисление (f + l)/2 на самом деле не постоянны в терминах n, но это будет не меняйте наш анализ). Мы можем доказать это с использованием математической индукции:

1. T(1) = a = (a + b)(1) - b имеет право;
2. Предположим, что T(n) = (a + b)n - b для всех n <= k.
3. ли T(k + 1) = (a + b)(k + 1) - b держать? Помните, что T(k + 1) = b + T(floor((k+1)/2)) + T(ceiling((k+1)/2). Допустим, k+1 и m = (k+1)/2. Тогда T (k + 1) = b + 2T (m) = b + 2 [(a + b) (m) - b] = b + 2 (m) (a + b) - 2b = (2m) (a + b) - b = (k + 1) (a + b) - b , as required. The case where k + 1` нечетно остается в качестве упражнения.

Это линейный.

Answer 2

Вы правы. Он возвращает наименьшее целое число массива.

И сложность

O(nlog(n)); n = size of the array 

Explanation: В каждом вызове, вы нарушаете массив на две равные части, в которой содержится призыв к f=l. Он вызывает функцию O(log(n)) раз для каждого числа в массиве. Таким образом, общая сложность составляет O(nlog(n))