我和我的朋友讨论了以下算法问题,
"Describe a recursive algorithm for finding the maximum element in an array A of n
elements. What is your running time and space usage?"
我们得出结论,它有 O(n) 的时间使用。根据此语句,F(n) =compare A[n] 与 F(n-1),在递归的基本情况下,它比较 A[0] 和 A[1],然后返回更大的一个,它将与A2]。随着递归的进行,最终,它将返回数组中的最大元素。
每 n 次递归,它只比较一次,所以最后我们猜测它有 O(n) 的时间使用。我的问题是我们不确定我们的解决方案,所以我们想要关于这个算法和我们的解决方案的任何其他评论。谢谢你。