伪代码的递归关系怎么写？

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

如果我错了请纠正我，但我认为这段代码 returns 是数组的最小整数。但是我如何找出用数组 A 描述时间复杂度的递推关系呢？您能否指导我找到解决方案以便我理解？我什至不知道从哪里开始。

Answer 1

你是对的。它returns数组的最小整数。

复杂度为

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

Explanation: 在每次调用中，您将数组分成两个相等的部分，最多调用 f=l。它为数组中的每个数字调用函数 O(log(n)) 次。因此，总复杂度为 O(nlog(n))

Answer 2

我们可以从伪代码的结构中恢复递归关系。我们可以让 T(n) 表示算法花费的时间作为输入大小的函数。对于n = 1，时间是常数，比如说T(1) = a。我们现在的问题是对于更大的n，我们如何表达T(n)？

我们将在 n > 1 的 else 子句中。我们做了一些额外的工作——我们称它为 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 方面并不是真正不变的，但它不会改变我们的分析）。我们可以用数学归纳法证明这一点：

T(1) = a = (a + b)(1) - b是对的；
假设 T(n) = (a + b)n - b 对于所有 n <= k。
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 wherek + 1` 是奇数留作练习。

这是线性的。

伪代码的递归关系怎么写？

How to write the recurrence relation of a pseudocode?

algorithm

math

recursion

big-o

time-complexity