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]。

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