algorithm - 为算法的基本操作次数建立递归关系并求解

Question

考虑以下算法

ALGORITHM Find(A[0..n‐1])
    if n ==1 return A[0]
    else temp = Find(A[0..n‐2])
    if temp ≤ A[n‐1] return temp
    else return A[n‐1]

a. What does this algorithm compute?
b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.

此算法是否返回 A[0]、A[0..3]、A[0..5]、A[0.7]、A[0..8]，或许对于 n=9？我走在正确的轨道上吗？

如果有人可以给我，我将不胜感激! 谢谢!

Answer 1

此算法将递归计算给定数组或元素列表的最小值。

对于 n 的每个值。您计算 n 之前所有值的最小值(即 <= n - 1)。如果返回的值小于 value[n]，则返回该值，否则返回 value[n]。

当您只有一个元素时，基本情况是微不足道的。您将该值作为最小值返回。